Yuval Rabani

Find my publications at:


  1. •dblp.uni-trier.de

  2. •scholar.google.com

  3. •aminer.org

Yuval Rabani

Some of my coauthors:

Sanjeev Arora

Yonatan Aumann

Noa Avigdor-Elgrabli

Yair Bartal

Allan Borodin

Sébastien Bubeck

Gruia Calinescu

Julia Chuzhoy

Amos Fiat

Howard Karloff

Subhash Khot

Jon Kleinberg

Robert Krauthgamer

Jian Li

Claire Matthieu

Assaf Naor

Rafail Ostrovsky

Yuri Rabinovich

Leonard Schulman

Alistair Sinclair

Chaitanya Swamy

Éva Tardos


Past students:

Amjad Aboud (M.Sc. 2008)

Guy Adini (M.Sc. 2012)

Omer Barkol (M.Sc. 2000)

Julia Chuzhoy (M.Sc. 2000)

Yohai Devir (M.Sc. 2009)

Yona Dolev (M.Sc. 2017)

Noa Elgrabli (Ph.D. 2014)

Anna Gringauze (M.Sc. 1998)

Koby Marom (M.Sc. 2017)

Anna Moss (Ph.D. 2001)

Gabi Scalosub (M.Sc. 2003)

On-Line Publications

    Recent
  • Proportional dynamics in exchange economies. Proc. of the 22nd ACM Conf. on Economics and Computation, to appear. (with Simina Brânzei and Nikhil Devanur) pdf
  • Source identification for mixtures of product distributions. Proc. of the 34th Ann. Conf. on Learning Theory, to appear. (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, and Leonard J. Schulman) 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 and Mark Sellke) 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 and 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 A. Naor, A. 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
    Approximation Algorithms
  • 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 and 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 and 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 and 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)
  • 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
    Data Analysis
  • Source identification for mixtures of product distributions. Proc. of the 34th Ann. Conf. on Learning Theory, to appear. (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, and 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 and 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, and 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 and Chaitanya Swamy) pdf
  • Explicit dimension reduction and its applications. SIAM J. Comput., 41(1):219-249, February 2012. (with Zohar Karnin and 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, and 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
    Online Computing
  • 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 and 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, and 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
    Dynamics and Interaction in Computation, Optimization, Biology, and Economics
  • Proportional dynamics in exchange economies. Proc. of the 22nd ACM Conf. on Economics and Computation, to appear. (with Simina Brânzei and Nikhil Devanur) pdf
  • Strictly balancing matrices in polynomial time using Osbornes iteration. To appear in Proc. of the 45th Int’l Colloq. on Automata, Languages, and Programming, July 2018. (with Rafail Ostrovsky and 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 and 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 and Leonard Schulman) pdf talk
  • The invisible hand of Laplace: the role of market structure in price convergence and oscillation. (with Leonard 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, and 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
  • Minimizing the share size in robust secret sharing. 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, and Rafail Ostrovsky) pdf
  • Explicit dimension reduction and its applications. SIAM J. Comput., 41(1):219-249, February 2012. (with Zohar Karnin and 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, and 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
  • 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, Eva Tardos) pdf
  • Allocating bandwidth for bursty connections. SIAM J. Comput., 30(1):191-217, 2000. (with Jon M. Kleinberg, Eva Tardos) pdf
  • Universal O(congestion + dilation + log1+epsilonN) 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