Publications
Probabilistic Analysis of Partitioning Algorithms for the Traveling-salesman Problem in the Plane.
Mathematics of Operations Research. 2(3), 209-224.
(1977). Randomized Rumor Spreading.
Proceedings of the IEEE 41st Annual Symposium on Foundations of Computer Science (FOCS 2000). 565-574.
(2000). 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). An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs.
SIAM Journal on Computing. 2(4), 225-231.
(1973).
(2010). On Linear Characterizations of Combinatorial Optimization Problems.
SIAM Journal on Computing. 11(4), 620-632.
(1982). The Complexity of Parallel Search.
Journal of Computer and System Sciences. 36,
(1988).
(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). An Introduction to Randomized Algorithms.
Discrete Applied Mathematics. 34,
(1991). 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). Near-optimal Solutions to a 2-dimensional Placement Problem.
SIAM Journal on Computing. 4(3), 271-286.
(1975).
(1993).
(1996).
(1995).
(1989).
(1993).
(1992).
(1989).
(1993).
(1994).
(1991).