Publications
The complexity of parallel computation.
Proceedings of the Fourth MIT Conference on Advanced Resarch in VLSI.
(1986). Randomized Rumor Spreading.
Proceedings of the IEEE 41st Annual Symposium on Foundations of Computer Science (FOCS 2000). 565-574.
(2000). An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs.
SIAM Journal on Computing. 2(4), 225-231.
(1973). A Simple Algorithm for Finding Frequent Elements in Streams and Bags.
ACM Transactions on Database Systems. 28(1), 51-55.
(2003). A Simple Algorithm for Finding Frequent Elements in Streams and Bags.
ACM Transactions on Database Systems. 28(1), 51-55.
(2003).
(2010). The Complexity of Parallel Search.
Journal of Computer and System Sciences. 36,
(1988). On Linear Characterizations of Combinatorial Optimization Problems.
SIAM Journal on Computing. 11(4), 620-632.
(1982). An Introduction to Randomized Algorithms.
Discrete Applied Mathematics. 34,
(1991).
(1990). Probabilistic analysis of network flow algorithms.
Mathematics of Operations Research. 18(1), 71-97.
(1993). A Patching Algorithm for the Nonsymmetric Traveling-salesman Problem.
SIAM Journal on Computing. 8(4), 561-573.
(1979). Near-optimal Solutions to a 2-dimensional Placement Problem.
SIAM Journal on Computing. 4(3), 271-286.
(1975). Monte-Carlo Algorithms for the Planar Multiterminal Network Reliability Problem.
Journal of Complexity. 1,
(1985). On-line algorithms versus off-line algorithms: how much is it worth to know the future?.
Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture - Information Processing '92. 416-429.
(1992).
(1993).
(1996).
(1995).
(1992).
(1993).
(1989).
(1993).
(1989).
(1994).
(1991).