# Yuval Rabani

According to our database

Collaborative distances:

^{1}, Yuval Rabani authored at least 84 papers between 1990 and 2018.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepages:

#### On csauthors.net:

## Bibliography

2018

Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration.

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Convergence of Incentive-Driven Dynamics in Fisher Markets.

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low Dimensional Spaces.

Proceedings of the Approximation, 2017

2016

Editorial to the Special Issue on SODA'12.

ACM Trans. Algorithms, 2016

2015

Learning Arbitrary Statistical Mixtures of Discrete Distributions.

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs.

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Learning mixtures of arbitrary distributions over large discrete domains.

Proceedings of the Innovations in Theoretical Computer Science, 2014

2013

A Constant Factor Approximation Algorithm for Reordering Buffer Management.

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

An optimal randomized online algorithm for reordering buffer management.

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Learning Mixtures of Distributions over Large Discrete Domains.

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

Unconditionally-Secure Robust Secret Sharing with Compact Shares.

Proceedings of the Advances in Cryptology - EUROCRYPT 2012, 2012

2011

An improved approximation algorithm for resource allocation.

ACM Trans. Algorithms, 2011

On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data.

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Explicit Dimension Reduction and Its Applications.

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010

Monotonicity in Bargaining Networks.

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

An Improved Competitive Algorithm for Reordering Buffer Management.

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

Improved Lower Bounds for Embeddings intoL

_{1}$.
SIAM J. Comput., 2009

Explicit construction of a small epsilon-net for linear threshold functions.

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

2008

Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem.

Proceedings of the Algorithm Theory, 2008

Approximation algorithms for labeling hierarchical taxonomies.

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

2007

Linear Programming.

Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007

Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems.

SIAM J. Comput., 2007

2006

On earthmover distance, metric labeling, and 0-extension.

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Local versus global properties of metric spaces.

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

The Effectiveness of Lloyd-Type Methods for the k-Means Problem.

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Approximation Algorithms for Graph Homomorphism Problems.

Proceedings of the Approximation, 2006

2005

On earthmover distance, metric labeling, and 0-extension

Electronic Colloquium on Computational Complexity (ECCC), 2005

Low distortion embeddings for edit distance.

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Approximating k-median with non-uniform capacities.

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Error-Correcting Codes for Automatic Control.

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

On the Hardness of Approximating Multicut and Sparsest-Cut.

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

Low distortion maps between point sets.

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

2003

Approximation schemes for clustering problems.

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Cell-probe lower bounds for the partial match problem.

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002

Tighter Lower Bounds for Nearest Neighbor Search and Related Problems in the Cell Probe Model.

J. Comput. Syst. Sci., 2002

Polynomial-time approximation schemes for geometric min-sum median clustering.

J. ACM, 2002

Polynomial Time Approximation Schemes for Metric Min-Sum Clustering

Electronic Colloquium on Computational Complexity (ECCC), 2002

Improved Approximation Algorithms for Resource Allocation.

Proceedings of the Integer Programming and Combinatorial Optimization, 2002

Search and Classification of High Dimensional Data.

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2002

2001

Approximation algorithms for constrained for constrained node weighted steiner tree problems.

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Tree packing and approximating k-cuts.

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Approximation algorithms for the 0-extension problem.

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Stability preserving transformations: packet routing networks with edge capacities and speeds.

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems.

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Approximating Directed Multicuts.

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems.

SIAM J. Comput., 2000

Tighter bounds for nearest neighbor search and related problems in the cell probe model.

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Polynomial Time Approximation Schemes for Geometric k-Clustering.

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999

Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces.

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems.

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Fairness in Routing and Load Balancing.

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

Competitive Algorithms for Layered Graph Traversal.

SIAM J. Comput., 1998

SIAM J. Comput., 1998

Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing.

J. Algorithms, 1998

Fairness in Scheduling

J. Algorithms, 1998

Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces.

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

An Improved Approximation Algorithm for Multiway Cut.

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Local Divergence of Markov Chains and the Analysis of Iterative Load Balancing Schemes.

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997

Deterministic Many-to-Many Hot Potato Routing.

IEEE Trans. Parallel Distrib. Syst., 1997

Universal

*O*(Congestion + Dilation + log^{1+epsilon}*N*) Local Control Packet Switching Algorithms.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Allocating Bandwidth for Bursty Connections.

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996

On the Value of Coordination in Distributed Decision Making.

SIAM J. Comput., 1996

Distributed Packet Switching in Arbitrary Networks.

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing (Preliminary Version).

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Path Coloring on the Mesh.

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

Competitive Algorithms for Distributed Data Management.

J. Comput. Syst. Sci., 1995

A computational view of population genetics.

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Improved Bounds for All Optical Routing.

Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Fairness in Scheduling.

Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

1994

Lower Bounds for Randomized k-Server and Motion-Planning Algorithms.

SIAM J. Comput., 1994

Competitive k-Server Algorithms.

J. Comput. Syst. Sci., 1994

A Better Lower Bound for On-Line Scheduling.

Inf. Process. Lett., 1994

A Deterministic O(k³)-Competitive k-Server Algorithm for the Circle.

Algorithmica, 1994

Simulating quadratic dynamical systems is PSPACE-complete (preliminary version).

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

On-line Admission Control and Circuit Routing for High Performance Computing and Communication

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

On the Value of Information in Coordination Games (preliminary version)

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

On the Space Complexity of Some Algorithms for Sequence Comparison.

Theor. Comput. Sci., 1992

Competitive Algorithms for Distributed Data Management (Extended Abstract)

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

A Decomposition Theorem and Bounds for Randomized Server Problems

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991

Lower Bounds for Randomized k-Server and Motion Planning Algorithms

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Competitive Algorithms for Layered Graph Traversal

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990

Competitive k-Server Algorithms (Extended Abstract)

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990