Yuval Rabani

According to our database1, Yuval Rabani authored at least 120 papers between 1990 and 2019.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Proportional Dynamics in Exchange Economies.
CoRR, 2019

Parametrized Metrical Task Systems.
CoRR, 2019

2018
Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017
Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low-Dimensional Spaces.
CoRR, 2017

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

Matrix Balancing in Lp Norms: Bounding the Convergence Rate of Osborne's Iteration.
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

Matrix Balancing in Lp Norms: A New Analysis of Osborne's Iteration.
CoRR, 2016

Market Dynamics of Best-Response with Lookahead.
CoRR, 2016

2015
An Improved Competitive Algorithm for Reordering Buffer Management.
ACM Trans. Algorithms, 2015

Learning Arbitrary Statistical Mixtures of Discrete Distributions.
CoRR, 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
Convergence of Tâtonnement in Fisher Markets.
CoRR, 2014

Learning mixtures of arbitrary distributions over large discrete domains.
Proceedings of the Innovations in Theoretical Computer Science, 2014

2013
An Optimal Randomized Online Algorithm for Reordering Buffer Management
CoRR, 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
Explicit Dimension Reduction and Its Applications.
SIAM J. Comput., 2012

Local Versus Global Properties of Metric Spaces.
SIAM J. Comput., 2012

The effectiveness of lloyd-type methods for the k-means problem.
J. ACM, 2012

Learning Mixtures of Arbitrary Distributions over Large Discrete Domains
CoRR, 2012

A Constant Factor Approximation Algorithm for Reordering Buffer Management
CoRR, 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
CoRR, 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
Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions.
SIAM J. Comput., 2010

Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform
CoRR, 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
Error-correcting codes for automatic control.
IEEE Trans. Information Theory, 2009

Bicriteria approximation tradeoff for the node-cost budget problem.
ACM Trans. Algorithms, 2009

Improved Lower Bounds for Embeddings intoL1$.
SIAM J. Comput., 2009

Low Distortion Maps Between Point Sets.
SIAM J. Comput., 2009

On Earthmover Distance, Metric Labeling, and 0-Extension.
SIAM J. Comput., 2009

Explicit Dimension Reduction and Its Applications.
Electronic Colloquium on Computational Complexity (ECCC), 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

Low distortion embeddings for edit distance.
J. ACM, 2007

2006
Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems.
Math. Oper. Res., 2006

On the Hardness of Approximating Multicut and Sparsest-Cut.
Computational Complexity, 2006

On earthmover distance, metric labeling, and 0-extension.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Improved lower bounds for embeddings into L1.
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

Approximating Directed Multicuts.
Combinatorica, 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
Approximation Algorithms for the 0-Extension Problem.
SIAM J. Comput., 2004

Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces.
Machine Learning, 2004

Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds.
Journal of Interconnection Networks, 2004

Cell-probe lower bounds for the partial match problem.
J. Comput. Syst. Sci., 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
Fairness in Routing and Load Balancing.
J. Comput. Syst. Sci., 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
Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces.
SIAM J. Comput., 2000

Allocating Bandwidth for Bursty Connections.
SIAM J. Comput., 2000

A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems.
SIAM J. Comput., 2000

An Improved Approximation Algorithm for MULTIWAY CUT.
J. Comput. Syst. Sci., 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

An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm.
SIAM J. Comput., 1998

A computational view of population genetics.
Random Struct. Algorithms, 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 + log1+epsilonN) 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


  Loading...