Recent

Causal Discovery under Latent Class Confounding. (with Spencer Gordon, Bijan Mazaheri, Leonard J. Schulman) pdf

Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity. (with Spencer Gordon, Erik Jahn, Bijan Mazaheri, Leonard J. Schulman) pdf

The randomized k-server conjecture is false! In Proc. of the 55th Ann. ACM Symp. on Theory of Computing, pages 581–594, June 2023. (with Sébastien Bubeck, Christian Coester) pdf  Quanta Magazine article

Causal Inference Despite Limited Global Confounding via Mixture Models. In Proc. of the 2nd Conf. on Causal Learning and Reasoning, PMLR 213:574–601, April 2023. (with Spencer Gordon, Bijan Mazaheri, Leonard J. Schulman) pdf

Online Computing

Shortetst pahs wihout a map, but wih an entropic regularizer. In Proc. of the 63rd Ann. IEEE Symp. on Foundations of Com- puter Science, pages 1102–1113, October 2022  (with Sébastien Bubeck, Christian Coester) pdf

Online multiserver convex chasing and optimization. In Proc. of the 32nd Ann. ACM-SIAM Symp. on Discrete Algorithms, January 2021, pages 2093-2104. (with Sébastien Bubeck, Mark Sellke) pdf

Parametrized metrical task systems. In Proc. of APPROX/RANDOM 2020, 54:1-54:14, August 2020. (with Sébastien Bubeck) pdf

On the randomized competitive ratio of reordering buffer management with non-uniform costs. In Proc. of the 42nd Int'l Colloq. on Automata, Languages, and Programming, July 2015. (with Noa Avigdor-Elgrabli, Sungjin Im, Ben Moseley) Springer Link

An optimal randomized online algorithm for reordering buffer management. In Proc. of the 54th Ann. IEEE Symp. on Foundations of Computer Science, October 2013, pages 1-10. (with Noa Avigdor-Elgrabli) pdf

An improved competitive algorithm for reordering buffer management. In Proc. of the 21st Ann. ACM-SIAM Symp. on Discrete Algorithms, January 2010. (with Noa Avigdor-Elgrabli) pdf

A decomposition theorem for task systems and bounds for randomized server problems. SIAM J. Comput., 30(5):1624-1661, 2000. (with Avrim Blum, Howard J. Karloff, Michael E. Saks) pdf

Competitive algorithms for layered graph traversal. SIAM J. Comput., 28(2):447-462, 1998. (with Amos Fiat, Dean P. Foster, Howard J. Karloff, Yiftach Ravid, Sundar Vishwanathan) pdf

Competitive algorithms for distributed data management. J. Comput. Syst. Sci., 51(3):341-358, 1995. (with Yair Bartal, Amos Fiat) pdf

On-line admission control and circuit routing for high performance computing and communication. In Proc. of the 35th Ann. IEEE Symp. on Foundations of Computer Science. November 1994, pages 412-423. (with Baruch Awerbuch, Rainer Gawlick, Frank Thomson Leighton) pdf

A deterministic O(k3)-competitive k-server algorithm for the circle. Algorithmica, 11(6):572-578, 1994. (with Amos Fiat, Yiftach Ravid, Baruch Schieber) pdf

Lower bounds for randomized k-server and motion-planning algorithms. SIAM J. Comput., 23(2):293-312, 1994. (with Howard J. Karloff, Yiftach Ravid) pdf

Competitive k-server algorithms. J. Comput. Syst. Sci., 48(3):410-428, 1994. (with Amos Fiat, Yiftach Ravid) pdf

A better lower bound for online scheduling. Inf. Process. Lett., 50(3):113-116, 1994. (with Yair Baratl, Howard J. Karloff) Elsevier Link

Unsupervised Learning, Data Analysis, Causality

A refined approximation for Euclidean k-means. Inf. Process. Lett. 176:106251.   (with Fabrizio Grandoni, Rafail Ostrovsky, Leonard J. Schulman, Rakesh Venkat) pdf

Min-sum clustering (with outliers). In Proc. of APPROX/RANDOM 2021, 16:1-16:16. (with Sandip Banerjee, Rafail Ostrovsky) pdf

Source identification for mixtures of product distributions. Proc. of the 34th Ann. Conf. on Learning Theory, pages 2193–2216, August 2021. (with Spencer Gordon, Bijan Mazaheri, and Leonard J. Schulman) pdf

The sparse Hausdorff moment problem, with application to topic models. (with Spencer Gordon, Bijan Mazaheri, Leonard J. Schulman) pdf

Approximation algorithms for clustering with dynamic points. In Proc. of the 28th Ann. European Symp. on Algorithms, 37:1-37:15, September 2020. (with Shichuan Deng, Jian Li) pdf

Learning arbitrary statistical mixtures of discrete distributions. In Proc. of the 47th Ann. ACM Symp. on Theory of Computing, June 2015. (with Jian Li, Leonard J. Schulman, Chaitanya Swamy) pdf talk

Learning mixtures of arbitrary distributions over large discrete domains. In Proc. of the 5th Conf. on Innovations in Theoretical Computer Science, January 2014, pages 207-224.  (with Leonard J. Schulman, Chaitanya Swamy) pdf

Explicit dimension reduction and its applications. SIAM J. Comput., 41(1):219-249, February 2012. (with Zohar Karnin, Amir Shpilka) pdf

On parsimonious explanations for 2-D tree- and linearly-ordered data. In Proc. of the 28th Int'l Symp. on Theoretical Aspects of Computer Science, March 2011. (with Howard Karloff, Flip Korn, Konstantin Makarychev) pdf

Explicit construction of a small epsilon-net for linear threshold functions. SIAM J. Comput., 39(8):3501-3520, August 2010. (with Amir Shpilka) pdf talk

The effectiveness of Lloyd-type methods for the k-means problem. In Proc. of the 47th Ann. IEEE Symp. on Foundations of Computer Science. , October 2006, pages 165-176. (with Rafail Ostrovsky, Leonard J. Schulman, Chaitanya Swamy) pdf talk

Low distortion embeddings for edit distance. J. Assoc. Comput. Mach., 54(5) article 23, October 2007. (with Rafail Ostrovsky) pdf talk

Low distortion maps between point sets. In Proc. of the 36th Ann. ACM Symp. on Theory of Computing. , June 2004, pages 272-280. (with Claire Kenyon, Alistair Sinclair) pdf

Cell-probe lower bounds for the partial match problem. J. Comput. Syst. Sci. , 69(3):435-447, 2004. (with T. S. Jayram, Subhash Khot, Ravi Kumar) pdf

Subquadratic approximation algorithms for clustering problems in high dimensional spaces. Machine Learning, 56(1-3):153-167, 2004. (with Allan Borodin, Rafail Ostrovsky) pdf

Approximation schemes for clustering problems. In Proc. of the 35th Ann. ACM Symp. on Theory of Computing. , June 2003, pages 50-58. (with Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon) pdf

Lower bounds for high dimensional nearest neighbor search and related problems. In Discrete and Computational Geometry - The Goodman-Pollack Festschrift. Springer. , August 2003, pages 255-276. (with Allan Borodin, Rafail Ostrovsky) pdf

Polynomial-time approximation schemes for geometric min-sum median clustering. J. ACM, 49(2):139-156, 2002. (with Rafail Ostrovsky)

Tighter lower bounds for nearest neighbor search and related problems in the cell probe model. J. Comput. Syst. Sci. , 64(4):873-896, 2002. (with Omer Barkol) pdf

Efficient search for approximate nearest neighbor in high dimensional spaces. SIAM J. Comput., 30(2):457-474, 2000. (with Eyal Kushilevitz, Rafail Ostrovsky) pdf

Approximation Algorithms

Generalized unrelated machine scheduling problem. In Proc. of the 34th Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 2898–2916, January 2023 (with Shichuan Deng, Jian Li) pdf

Min-sum clustering (with outliers). In Proc. of APPROX/RANDOM 2021, 16:1-16:16. (with Sandip Banerjee, Rafail Ostrovsky) pdf

A refined approximation for Euclidean k-means. Inf. Process. Lett. 176:106251.   (with Fabrizio Grandoni, Rafail Ostrovsky, Leonard J. Schulman, Rakesh Venkat) pdf

Approximation algorithms for clustering with dynamic points. In Proc. of the 28th Ann. European Symp. on Algorithms, 37:1-37:15, September 2020. (with Shichuan Deng, Jian Li) pdf

Approximating sparsest cut in low rank graphs via embeddings from approximately low dimensional spaces. In Proc. of the 20th Int’l Workshop on Approximation Algorithms for Combinatorial Optimization Problems, August 2017. (with Rakesh Venkat) pdf

A constant-factor approximation algorithm for reordering buffer management. In Proc. of the 24th Ann. ACM-SIAM Symp. on Discrete Algorithms, January 2013. (with Noa Avigdor-Elgrabli) pdf

Labeling hierarchical taxonomies. In Proc. of the 19th Ann. ACM-SIAM Symp. on Discrete Algorithms, January 2008. (with Leonard Schulman, Chaitanya Swamy) pdf talk

Approximation algorithms for graph homomorphism problems. In Proc. of the 9th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems,  August 2006. (with Michael Langberg, Chaitanya Swamy) ps

On earthmover distance, metric labeling, and 0-extension. In Proc. of the 38th Ann. ACM Symp. on Theory of Computing , May 2006, pages 547-556. (with Howard J. Karloff, Subhash Khot, Aranyak Mehta) pdf

Improved lower bounds for embeddings into L1. In Proc. of the 17th Ann. ACM-SIAM Symp. on Discrete Algorithms. , January 2006, pages 1010-1017. (with Robert Krauthgamer) pdf

On the hardness of approximating multicut and sparsest-cut. Computational Complexity, 15(2):94-114, 2006. (with Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, D. Sivakumar) pdf

Approximation algorithms for the job interval selection problem and related scheduling problems. Math. Oper. Res., 31(4):730-738, 2006. (with Julia Chuzhoy, Rafail Ostrovsky) pdf

Approximating k-median with non-uniform capacities. In Proc. of the 16th Ann. ACM-SIAM Symp. on Discrete Algorithms. , January 2005, pages 952-958. (with Julia Chuzhoy) pdf

Approximating directed multicuts. Combinatorica, 25(3):251-269, 2005. (with Joseph Cheriyan, Howard J. Karloff) pdf

Approximation algorithms for the 0-extension problem. SIAM J. Comput., 34(2):358-372, 2004. (with Gruia Calinescu, Howard J. Karloff) pdf

Approximation schemes for clustering problems. In Proc. of the 35th Ann. ACM Symp. on Theory of Computing. , June 2003, pages 50-58. (with Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon) pdf

Improved approximation algorithms for resource allocation. In Proc. of the 9th Int'l Conf. on Integer Programming and Combinatorial Optimization. Springer. , May 2002, pages 401-414. (with Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff) pdf     

Approximation algorithms for constrained node weighted Steiner tree problems. SIAM J. Comput., 37(2):460-481, 2007. (with Anna Moss) pdf

Notice: The proof of the main result of this paper, an approximation algorithm for the node weighted prize collecting Steiner tree problem, is fatally flawed. The reductions from the quota and budget problems to the prize collecting problem are correct. The mistake was noted and corrected, via a completely different proof, in a paper by Konemann, Sadeghian, and Sanita (FOCS '13) that can be found here.

Polynomial-time approximation schemes for geometric min-sum median clustering. J. ACM, 49(2):139-156, 2002. (with Rafail Ostrovsky) pdf

An improved approximation algorithm for MULTIWAY CUT. J. Comput. Syst. Sci. , 60(3):564-574, 2000. (with Gruia Calinescu, Howard J. Karloff) pdf

An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput., 27(1):291-301, 1998. (with Yonatan Aumann) pdf

Metric Geometry

On Lipschitz extension from finite subsets. Israel Journal of Mathematics, 219(1):115-161, April 2017. (with Assaf Naor) pdf

Labeling hierarchical taxonomies. In Proc. of the 19th Ann. ACM-SIAM Symp. on Discrete Algorithms, January 2008. (with Leonard Schulman, Chaitanya Swamy) pdf talk

Low distortion embeddings for edit distance. J. Assoc. Comput. Mach., 54(5) article 23, October 2007. (with Rafail Ostrovsky) pdf talk

On earthmover distance, metric labeling, and 0-extension. In Proc. of the 38th Ann. ACM Symp. on Theory of Computing. , May 2006, pages 547-556. (with Howard J. Karloff, Subhash Khot, Aranyak Mehta) pdf

Improved lower bounds for embeddings into L1. In Proc. of the 17th Ann. ACM-SIAM Symp. on Discrete Algorithms. , January 2006, pages 1010-1017. (with Robert Krauthgamer) pdf

Local versus global properties of metric spaces. In Proc. of the 17th Ann. ACM-SIAM Symp. on Discrete Algorithms. , January 2006, pages 41-50. (with Sanjeev Arora, Laszlo Lovasz, Ilan Newman, Yuri Rabinovich, Santosh Vempala) pdf

Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs. Journal of Functional Analysis, 227(2):273--303, October 2005.  (with Assaf Naor, Alistair Sinclair) pdf

Low distortion maps between point sets. In Proc. of the 36th Ann. ACM Symp. on Theory of Computing. , June 2004, pages 272-280. (with Claire Kenyon, Alistair Sinclair) pdf

Approximation algorithms for the 0-extension problem. SIAM J. Comput., 34(2):358-372, 2004. (with Gruia Calinescu, Howard J. Karloff) pdf

A decomposition theorem for task systems and bounds for randomized server problems. SIAM J. Comput., 30(5):1624-1661, 2000. (with Avrim Blum, Howard J. Karloff, Michael E. Saks) pdf

An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput., 27(1):291-301, 1998. (with Yonatan Aumann) pdf

Lower bounds for randomized k-server and motion-planning algorithms. SIAM J. Comput., 23(2):293-312, 1994. (with Howard J. Karloff, Yiftach Ravid) pdf

Dynamics and Interaction in Computation, Biology, and Economics

Proportional dynamics in exchange economies. In Proc. of the 22nd ACM Conf. on Economics and Computation, July 2021, pages 180-201. (with Simina Brânzei, Nikhil Devanur) pdf

Strictly balancing matrices in polynomial time using Osbornes iteration. In Proc. of the 45th Int’l Colloq. on Automata, Languages, and Programming, July 2018. (with Rafail Ostrovsky, Arman Yousefi) pdf

Matrix balancing in Lp norms: bounding the convergence rate of Osborne's iteration. In Proc. of the 28th Ann. ACM-SIAM Symp. on Discrete Algorithms, January 2017. (with Rafail Ostrovsky, Arman Yousefi) pdf talk

Convergence of incentive-driven dynamics in Fisher markets. In Proc. of the 28th Ann. ACM-SIAM Symp. on Discrete Algorithms, January 2017. (with Krishnamurthy Dvijotham, Leonard J. Schulman) pdf talk

The invisible hand of Laplace: the role of market structure in price convergence and oscillation. (with Leonard J. Schulman) pdf

Monotonicity in bargaining networks. In Proc. of the 21st Ann. ACM-SIAM Symp. on Discrete Algorithms, January 2010. (with Yossi Azar, Nikhil Devanur, Kamal Jain) pdf talk

Local divergence of Markov chains and the analysis of iterative load balancing schemes. In Proc. of the 39th Ann. IEEE Symp. on Foundations of Computer Science. , November 1998, pages 694-705. (with Alistair Sinclair, Rolf Wanka) pdf

Biased random walks, Lyapunov functions, and stochastic analysis of best fit bin packing. J. Algorithms, 27(2):218-235, 1998. (with Claire Kenyon, Alistair Sinclair) pdf

Fairness in scheduling. J. Algorithms, 29(2):306-357, 1998. (with Miklos Ajtai, James Aspnes, Moni Naor, Leonard J. Schulman, Orli Waarts) pdf

A computational view of population genetics. Random Struct. Algorithms, 12(4):313-334, 1998. (with Yuri Rabinovich, Alistair Sinclair) pdf

On the value of coordination in distributed decision making. SIAM J. Comput., 25(3):498-519, 1996. (with Sandy Irani) pdf

Simulating quadratic dynamical systems is PSPACE-complete. In Proc. of the 26th Ann. ACM Symp. on Theory of Computing. , May 1994, pages 459-467. (with Sanjeev Arora, Umesh V. Vazirani) pdf

Pseudorandomness, Coding, Compression

Uncondittionally-secure robust secret sharing with compact shares. In Proc. of the 31st Ann. Int'l Conf. on the Theory and Applications of Cryptographic Techniques (Eurocrypt), April 2012. (with Alfonso Cevallos, Serge Fehr, Rafail Ostrovsky) pdf

Explicit dimension reduction and its applications. SIAM J. Comput., 41(1):219-249, February 2012. (with Zohar Karnin, Amir Shpilka) pdf

On parsimonious explanations for 2-D tree- and linearly-ordered data. In Proc. of the 28th Int'l Symp. on Theoretical Aspects of Computer Science, March 2011. (with Howard Karloff, Flip Korn, Konstantin Makarychev) pdf

Explicit construction of a small epsilon-net for linear threshold functions. SIAM J. Comput., 39(8):3501-3520, August 2010. (with Amir Shpilka) pdf talk corrigendum

Error-correcting codes for automatic control. In Proc. of the 46th Ann. IEEE Symp. on Foundations of Computer Science. , October 2005, pages 309-316. (with Rafail Ostrovsky, Leonard J. Schulman) pdf

Admission Control, Routing, and Flow Control

Stability preserving transformations: packet routing networks with edge capacities and speeds. Journal of Interconnection Networks, 5(1):1-12, 2004. (with Allan Borodin, Rafail Ostrovsky) pdf

Fairness in routing and load balancing. J. Comput. Syst. Sci. , 63(1):2-20, 2001.  (with Jon M. Kleinberg, Éva Tardos) pdf

Allocating bandwidth for bursty connections. SIAM J. Comput., 30(1):191-217, 2000.  (with Jon M. Kleinberg, Éva Tardos) pdf

Universal O(congestion + dilation + log1+ε N) local control packet switching algorithms. In Proc. of the 29th Ann. ACM Symp. on Theory of Computing. , May 1997, pages 644-653. (with Rafail Ostrovsky) pdf

Deterministic many-to-many hot potato routing. IEEE Trans. Parallel Distrib. Syst., 8(6):587-596, 1997. (with Allan Borodin, Baruch Schieber) pdf

Path coloring on the mesh. In Proc. of the 37th Ann. IEEE Symp. on Foundations of Computer Science. , October 1996, pages 400-409. pdf

Distributed packet switching in arbitrary networks. In Proc. of the 28th Ann. ACM Symp. on Theory of Computing. , May 1996, pages 366-375. (with Eva Tardos) pdf

Improved bounds for all optical routing. In Proc. of the 6th Ann. ACM-SIAM Symp. on Discrete Algorithms. , January 1995, pages 567-576. (with Yonatan Aumann) pdf

On-line admission control and circuit routing for high performance computing and communication. In Proc. of the 35th Ann. IEEE Symp. on Foundations of Computer Science, November 1994, pages 412-423. (with Baruch Awerbuch, Rainer Gawlick, Frank Thomson Leighton) pdf