Selected Publications

    Distributed Computing

  1. ``Byzantine agreement with a Strong Adversary in Polynomial Expected Time" (brief announcement of STOC 2013 to appear) with Jared Saia. Please contact me if you would like a copy of the STOC paper.
  2. ``Breaking the O(n^2) Barrier: calable byzantine agreement with an adaptive adversary" extended version Jared Saia (PODC 2010), winner of best paper award, PODC 2010
  3. ``Fast Asychnronous Byzantine Agreement and Leader Election with Full Information'' with Bruce Kapron, David Kempe, Jared Saia, and Vishal Sanwalani (SODA 2008), journal version to appear in ALG-Best SODA 2008 papers
  4. ``Towards Secure and Scalable Computation in Peer-to-Peer Networks'' with J.Saia, V. Sanw alani, E. Vee (FOCS 2006).
  5. ``Lower Bounds for Scalable Leader Election" with D. Holtby and B. Kapron (ACM PODC 2006).
  6. ``Scalable Leader Election," with J. Saia, V. Sanwalani, E. Vee. (SODA 2006).

    Social Networks

  7. ``Guanxi in the Chinese Web" with Louis Yu and Yan Zhuang. Winner of best paper in IEEE SocialCom 2009. Poster version winner of best poster in WWW 2008.

    Networks, Computational Biology, and other Applications

  8. ``Choosing a Random Peer in Chord" with S. Lewis, J. Saia, and M. Young. To appear in Algorithmica.
  9. ``Choosing a Random Peer," with J.Saia. (PODC'04).
  10. ``Connectivity in Wireless Sensor Networks," with Sarah Carruthers. (ADHOC-NOW'04).
  11. ``On the Complexity of Distance-based Evolutionary Tree Reconstruction," with L. Zhang and Y. Zhou. (SODA'03).
  12. "On the complexity of Parity Word Automata" with O. Kupferman and M. Vardi. (FOSSACS'01).
  13. ``Constructing a Tree from Homeomorphic Subtrees with Applications to Computational Biology,'' with M. Henzinger and T. Warnow. (SODA'96); also in Algorithmica, vol. 24, no.1 (1999) pp.1-13.

    Dynamic Graph Algorithms

  14. ``Dynamic Graph Connectivity in polylogarithmic worst case time,'' (slides) with Bruce Kapron and Ben Mounjoy (SODA'13).
  15. ``Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure,'' (FOCS'99).
  16. . "A Fully Dynamic Algorithm for Maintaining the Transitive Closure," with G. Sagert. Journal of Systems Science (2000). Preliminary version in (STOC'99).
  17. ``Fully Dynamic 2-Edge Connectivity in Polylogarithmic Time per Operation,'' DEC SERC Technical Report (1997).
  18. "Maintaining Minimum Spanning Trees in Dynamic Graphs," with M. Henzinger (ICALP'97), also in SIAM Journal on Computing 31(2), pp.364-374 (2001).
  19. "A Fully Dynamic Connectivity Algorithm for Fixed Genus Graphs" with M. Henzinger and L. Ibarra. U.Victoria Technical Report (1999).
  20. "Randomized Dynamic Graph Algorithms with Polylogarithmic Time per Operation" with M. Henzinger, (STOC'95). Journal of the ACM, Vol. 46 No. 4 (1999) pp.502-516.
  21. "Fully Dynamic Biconnectivity and Transitive Closure," with M. Henzinger. (FOCS 1995)

    Maximum Flow Problem

  22. "A Faster Deterministic Maximum Flow Algorithm" with S. Rao and R. Tarjan, Journal of Algorithms, vol. 17. no. 3 (1994) pp.447-474. Also in (SODA'92).

    Parallel Complexity

  23. ``Limits on the power of parallel random access machines with weak forms of write conflict resolution'' with F. Fich, R. Impagliazzo, B. Kapron and M. Kutylowski. Journal of Computer and System Sciences} (1997). Preliminary version appeared in Proceedings of the 10th Symposium on Theoretical Aspects of Computer Science (STACS 1993)}.

    Set Maxima Problem and Verification

  24. "An Optimal EREW PRAM Algorithm For Minimum Spanning Tree Verification" with C.K. Poon, V. Ramachandran, S. Sinha. Information Processing Letters, vol. 62 (1997) pp.153-159.
  25. "A Simpler Linear Time Algorithm for Minimum Spanning Tree Verification." Algorithmica, 18 (1997) pp. 263-270. Preliminary version appeared in (WADS'95).
  26. Optimal Randomized Algorithms for Local Sorting and Set-Maxima (with Wayne Goddard, Claire Kenyon and Leonard Schulman), SIAM Journal of Computing, vol. 22 no. 2 (1993), pp.272-285. Preliminary versions also in (STOC'90) and (STOC'89).

    Boolean Decision Trees

  27. "Boolean Functions with Noisy Nodes," with C. Kenyon, Random Structures and Algorithms, vol. 5, no. 3 (1994), pp.453-464. Preliminary version appeared in Proceedings of the Israel Symposium on Theory of Computing and Systems, Springer-Verlag Lecture Notes in Computer Science, No. 601, (May 1992), pp.24-31.
  28. "An Omega(n^{5/4) Lower Bound on the Randomized Complexity of Graph Properties", in Combinatorica, 11(1) (1991), pp. 23-32. Also in (STOC'88).
  29. "A Lower Bound for the Recognition of Digraph Properties", Combinatorica 10 (1) pp. 53-59, 1990. Also in (STOC'88).
  30. My Ph.D.

Dynamic graph algorithms

Dynamic graph algorithms are algorithms that maintain information about properties of a graph, while the graph is changing.

The paper "Randomized Dynamic Graph Algorithms with Polylogarithmic Time per Operation" presents a fully dynamic connectivity algorithm, i.e. a data structure is maintained so that queries of the form "Is node i connected to node j?" can be answered quickly, without having to recompute connectivity for the whole graph after each update of the graph. The Las Vegas algorithm requires no more than logarithmic time for queries and polylogarithmic amortized expected time per update. The best previously known algorithm due to G. Fredrickson (1985), as improved by D. Eppstein, Z. Galil, G. Italiano, and A. Nissenzweig (1992) were much more costly per update ( O(n^{1/2}), where n=number of nodes in the graph) and more difficult to implement. This was joint work with M. Henzinger.

As a consequence of our connectivity algorithm, we are able to solve several other dynamic graph problems with polylogarithmic update time and polylogarithmic query time, including bipartiteness, approximate minimum spanning tree, and the k-edge witness problem. Using similar techniques we have developed polylogarithmic algorithms for biconnectivity with bounded degree (FOCS '95) and 2-edge connectivity ``Fully Dynamic 2-Edge Connectivity in Polylogarithmic Time per Operation'' . No previous polylogarithmic time algorithms were known for these problems.

We also developed a fully dynamic method of maintaining the minimum spanning trees deterministically which is simple and runs faster than previously known algorithms (O(n^{1/3}) amortized update time) ("Maintaining Minimum Spanning Trees in Dynamic Graphs" ) .

For directed graphs, in 1995, using different randomized techniques, we developed the first fully dynamic Monte Carlo algorithm which does better than recomputation from scratch for answering queries as to whether there's a directed path from one vertex to another (FOCS'95) (i.e. maintaining the transitive closure). However, query costs were expensive (O(n/log n).

Revisiting this problem in 1999, in "A Fully Dynamic Algorithm for Maintaining the Transitive Closure," G. Sagert and I presented the first fully dynamic Monte Carlo algorithm for maintaining the transtive closure with constant query time. The update time is O(n^(2+a)) where a=min {maximimum size of a strongly connected component, .25...). In ``Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure,'' , I presented the first fully dynamic algorithm for maintaining all-pairs shortest paths in directed graphs, and well as a deterministic dynamic transitive closure algorithm. Approximately shortest paths and also transitive closure can be maintained in O(n log n) time per update.

My Ph.D. student Lou Ibarra , is working on dynamic graph properties for chordal and interval graphs.

Computational biology

(A) Biologists need to measure distances between evolutionary trees, when comparing different biological theories. In 1978, two prominent computational biologists, T. Smith and M. Waterman, defined a measure of distance between two trees known as the nni distance or the number of ``nearest neighbor interchanges'' which turns out to have an essentially equivalent formulation in computer science as the number of tree rotations needed to turn one parenthesized arithmetic expression into another.

No way to effectively compute this distance is known, yet several approximation methods methods (Smith-Waterman, Brown-Day) were believed effective. My work with T. Warnow, presented at a DIMACS workshop shows a family of pairs of trees for which these methods give an asymptotically higher estimate than the actual distance.

(B) Given a set of evolutionary trees whose leaves are labelled with a subset of possible species, the tree consensus problem is to determine if a consensus tree exists which is homeomorphic to the given trees and if so, construct it. The consensus tree problem first arose in computer science in work by A. Aho, et. al. because of its applications to the theory of relational data bases.

We devised a method of speeding up the Aho algorithm using a novel dynamic graph data structures to the problem (``Constructing a Tree from Homeomorphic Subtrees with Applications to Computational Biology'' ).

Lower bounds in parallel machines

Paper ``Limits on the power of parallel random access machines with weak forms of write conflict resolution'' proves lower bounds in a very weak model for a parallel machine with random access shared memory in which any number of processors may read from and write to the same cell in a single step (CRCW PRAM). In this model, the adversary may arbitrarily fix the contents of the cell when more than one processor writes to it. We also show a randomized algorithm that achieves expected times which are asymptotically smaller than our deterministic lower bounds.

Set-maxima problem and the verification of partial orders and minimum spanning trees

The ``set-maxima'' problem, was stated in a paper by R. Graham, A. Yao, and F. Yao, in a section attributed to Fredman in 1980. (The problem didn't have a name at the time.) The set-maxima problem was given as a example of a problem with a ``weak'' information theory lower bound. Given a collection of (possibly overlapping) sets whose elements are drawn from a total order, the problem is to determine the aximum element in each set, where cost is measured by the number of comparisons between elements needed by an adaptive strategy. No known method other than the trivial one of finding each maximum element from each separately was known until the randomized algorithm of Kenyon and mysel f in a paper in STOC'89. In that paper, we were solving the set-maxima problem in an attempt to verify a partial order, a problem raised by A. Yao. Paper Optimal Randomized Algorithms for Local Sorting and Set-Maxima" improves that result, giving a randomized algorithm for set-maxima, whose expected cost matched the information theory bounds for the problem.

A special case of the set-maxima problem occurs in the problem of of determining whether a given spanning tree is a minimal spanning tree. In 1984, J. Komlos gave a deterministic algorithm which uses a linear number of comparisons, though no data structure to allow a linear time implementation of his method was known. In my paper "A Simpler Linear Time Algorithm for Minimum Spanning Tree Verification" I simplify his algorithm and give a linear time (determinisitic) implementation in the unit cost RAM model. This technique is simpler and more constructive than the previous linear time technique of M. Henzinger.

This minimum spanning tree algorithm is a subroutine in the first linear expected time algorithm for computing the minimum spanning tree, due to D. Karger, P. Klein an d R. Tarjan.

Maximum flow problem

The maximum flow problem was done while at NEC Research Institute, with S. Rao and R. Tarjan. Our paper "A Faster Deterministic Maximum Flow Algorithm" gives what is the best to my knowledge the asymptotically fastest deterministic algorithm for the maximum flow problem. This paper appeared in a special issue of outstanding papers of SODA 92 in the Journal of Algorithms. The paper derandomizes a technique of Cheriyan, Hagerup, and Mehlhorn.

Boolean decision trees

My thesis, and papers "An Omega(n^{5/4) Lower Bound on the Randomized Complexity of Graph Properties", A Lower Bound for the Recognition of Digraph Properties, "Boolean Functions with Noisy Nodes" concern the Boolean decision tree model. In that model, the cost of evaluating a function is measured by the number of bits of input which must be examined to determine its value, in the worst case, with an adaptive strategy. This model provides a simple context in which to study the effects of randomization, "noisy" information, and other aspects of computation. A lower bound in this simple model provides lower bounds for more sophisticated models of computation.

This area of study was motivated by the problem of proving lower bounds for graph problems when the graph is given as an adjacency matrix. The 1973 Aanderaa-Rosenberg Conjecture postulated a certain lower bound on the number of queries to the adjacency matrix of a graph required to determine if the graph had any given monotone graph property. This conjecture sparked a number of papers in the area. A brief survey of work in this area can be found in the Handbook of Theoretical Computer Science, pp.532-536.

My thesis work extended the techniques of Kahn, Saks, and Sturtevant to improve the deterministic lower bound for directed graphs. It also substantially improved the known lower bound for the randomized complexity of monotone graph properties, a problem posed by A. Yao. A third chapter, never published, extended these results to the case where error is allowed.

Some years later, I revisited this area with C. Kenyon, of the Ecole Normale Superior in Lyon, and looked at computation where queries were assumed to be ``noisy,'' meaning faulty with some fixed probability. My work was inspired by a paper by U. Feige, D. Peleg, P. Raghavan and E. Upfal who had shown that the problem of designing tournaments to determine the best basketball team was an interesting problem when one could only assume that the better team would win with some fixed probability greater than $1/2$. This lead to our development of an algorithm to evaluate any Boolean function when each reading of an input bit has a fixed probability of error.