Yuval Rabani

According to our database, Yuval Rabani authored at least 100 papers between 1990 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

Causal Discovery under Latent Class Confounding.

Bijan Mazaheri, Spencer Gordon, Yuval Rabani, Leonard J. Schulman

CoRR, 2023

Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity.

Spencer L. Gordon, Erik Jahn, Bijan Mazaheri, Yuval Rabani, Leonard J. Schulman

CoRR, 2023

The Randomized k-Server Conjecture Is False!

Sébastien Bubeck, Christian Coester, Yuval Rabani

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Generalized Unrelated Machine Scheduling Problem.

Shichuan Deng, Jian Li, Yuval Rabani

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Causal Inference Despite Limited Global Confounding via Mixture Models.

Spencer L. Gordon, Bijan Mazaheri, Yuval Rabani, Leonard J. Schulman

Proceedings of the Conference on Causal Learning and Reasoning, 2023

2022

Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions.

Yuval Rabani, Amir Shpilka

SIAM J. Comput., December, 2022

Approximation algorithms for clustering with dynamic points.

Shichuan Deng, Jian Li, Yuval Rabani

J. Comput. Syst. Sci., 2022

A refined approximation for Euclidean k-means.

Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Rakesh Venkat

Inf. Process. Lett., 2022

Convergence of incentive-driven dynamics in Fisher markets.

Krishnamurthy Dvijotham, Yuval Rabani, Leonard J. Schulman

Games Econ. Behav., 2022

Shortest Paths without a Map, but with an Entropic Regularizer.

Sébastien Bubeck, Christian Coester, Yuval Rabani

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Identifying Mixtures of Bayesian Network Distributions.

Spencer L. Gordon, Bijan Mazaheri, Yuval Rabani, Leonard J. Schulman

CoRR, 2021

Online Multiserver Convex Chasing and Optimization.

Sébastien Bubeck, Yuval Rabani, Mark Sellke

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Proportional Dynamics in Exchange Economies.

Simina Brânzei, Nikhil R. Devanur, Yuval Rabani

Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

Source Identification for Mixtures of Product Distributions.

Spencer Gordon, Bijan H. Mazaheri, Yuval Rabani, Leonard J. Schulman

Proceedings of the Conference on Learning Theory, 2021

Min-Sum Clustering (With Outliers).

Sandip Banerjee, Rafail Ostrovsky, Yuval Rabani

Proceedings of the Approximation, 2021

2020

The Sparse Hausdorff Moment Problem, with Application to Topic Models.

Spencer Gordon, Bijan Mazaheri, Leonard J. Schulman, Yuval Rabani

CoRR, 2020

Parametrized Metrical Task Systems.

Sébastien Bubeck, Yuval Rabani

Proceedings of the Approximation, 2020

2018

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

Rafail Ostrovsky, Yuval Rabani, Arman Yousefi

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

2017

Matrix Balancing in <i>L</i>_p Norms: Bounding the Convergence Rate of Osborne's Iteration.

Rafail Ostrovsky, Yuval Rabani, Arman Yousefi

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.

Yuval Rabani, Rakesh Venkat

Proceedings of the Approximation, 2017

2016

Editorial to the Special Issue on SODA'12.

Yuval Rabani, Andréa W. Richa, Jared Saia, David P. Woodruff

ACM Trans. Algorithms, 2016

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

Rafail Ostrovsky, Yuval Rabani, Arman Yousefi

CoRR, 2016

Market Dynamics of Best-Response with Lookahead.

Krishnamurthy Dvijotham, Yuval Rabani, Leonard J. Schulman

CoRR, 2016

2015

An Improved Competitive Algorithm for Reordering Buffer Management.

Noa Avigdor-Elgrabli, Yuval Rabani

ACM Trans. Algorithms, 2015

Learning Arbitrary Statistical Mixtures of Discrete Distributions.

Jian Li, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy

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.

Noa Avigdor-Elgrabli, Sungjin Im, Benjamin Moseley, Yuval Rabani

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

2014

Convergence of Tâtonnement in Fisher Markets.

Noa Avigdor-Elgrabli, Yuval Rabani

CoRR, 2014

Learning mixtures of arbitrary distributions over large discrete domains.

Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy

Proceedings of the Innovations in Theoretical Computer Science, 2014

2013

A Constant Factor Approximation Algorithm for Reordering Buffer Management.

Noa Avigdor-Elgrabli, Yuval Rabani

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

An optimal randomized online algorithm for reordering buffer management.

Noa Avigdor-Elgrabli, Yuval Rabani

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

2012

Local Versus Global Properties of Metric Spaces.

Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh S. Vempala

SIAM J. Comput., 2012

The effectiveness of lloyd-type methods for the k-means problem.

Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy

J. ACM, 2012

Learning Mixtures of Distributions over Large Discrete Domains.

Yuval Rabani

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

Unconditionally-Secure Robust Secret Sharing with Compact Shares.

Alfonso Cevallos, Serge Fehr, Rafail Ostrovsky, Yuval Rabani

Proceedings of the Advances in Cryptology - EUROCRYPT 2012, 2012

2011

An improved approximation algorithm for resource allocation.

Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, Yuval Rabani

ACM Trans. Algorithms, 2011

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

Howard J. Karloff, Flip Korn, Konstantin Makarychev, Yuval Rabani

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

2010

Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions.

Yuval Rabani, Amir Shpilka

SIAM J. Comput., 2010

Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform

Vladimir Braverman, Rafail Ostrovsky, Yuval Rabani

CoRR, 2010

Monotonicity in Bargaining Networks.

Yossi Azar, Nikhil R. Devanur, Kamal Jain, Yuval Rabani

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

2009

Error-correcting codes for automatic control.

Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman

IEEE Trans. Inf. Theory, 2009

Bicriteria approximation tradeoff for the node-cost budget problem.

Yuval Rabani, Gabriel Scalosub

ACM Trans. Algorithms, 2009

Improved Lower Bounds for Embeddings intoL₁$.

Robert Krauthgamer, Yuval Rabani

SIAM J. Comput., 2009

Low Distortion Maps Between Point Sets.

Claire Kenyon, Yuval Rabani, Alistair Sinclair

SIAM J. Comput., 2009

Explicit Dimension Reduction and Its Applications.

Zohar Shay Karnin, Yuval Rabani, Amir Shpilka

Electron. Colloquium Comput. Complex., 2009

2008

Approximation algorithms for labeling hierarchical taxonomies.

Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy

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

2007

Linear Programming.

Yuval Rabani

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

Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems.

Anna Moss, Yuval Rabani

SIAM J. Comput., 2007

Low distortion embeddings for edit distance.

Rafail Ostrovsky, Yuval Rabani

J. ACM, 2007

2006

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

Julia Chuzhoy, Rafail Ostrovsky, Yuval Rabani

Math. Oper. Res., 2006

On the Hardness of Approximating Multicut and Sparsest-Cut.

Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar

Comput. Complex., 2006

Improved lower bounds for embeddings into <i>L</i>₁.

Robert Krauthgamer, Yuval Rabani

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

Approximation Algorithms for Graph Homomorphism Problems.

Michael Langberg, Yuval Rabani, Chaitanya Swamy

Proceedings of the Approximation, 2006

2005

On earthmover distance, metric labeling, and 0-extension

Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani

Electron. Colloquium Comput. Complex., 2005

Approximating Directed Multicuts.

Joseph Cheriyan, Howard J. Karloff, Yuval Rabani

Comb., 2005

Approximating k-median with non-uniform capacities.

Julia Chuzhoy, Yuval Rabani

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

2004

Approximation Algorithms for the 0-Extension Problem.

Gruia Calinescu, Howard J. Karloff, Yuval Rabani

SIAM J. Comput., 2004

Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces.

Allan Borodin, Rafail Ostrovsky, Yuval Rabani

Mach. Learn., 2004

Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds.

Allan Borodin, Rafail Ostrovsky, Yuval Rabani

J. Interconnect. Networks, 2004

Cell-probe lower bounds for the partial match problem.

T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani

J. Comput. Syst. Sci., 2004

2003

Approximation schemes for clustering problems.

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani

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.

Omer Barkol, Yuval Rabani

J. Comput. Syst. Sci., 2002

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

Rafail Ostrovsky, Yuval Rabani

J. ACM, 2002

Polynomial Time Approximation Schemes for Metric Min-Sum Clustering

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani

Electron. Colloquium Comput. Complex., 2002

Improved Approximation Algorithms for Resource Allocation.

Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, Yuval Rabani

Proceedings of the Integer Programming and Combinatorial Optimization, 2002

Search and Classification of High Dimensional Data.

Yuval Rabani

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2002

2001

Fairness in Routing and Load Balancing.

Jon M. Kleinberg, Yuval Rabani, Éva Tardos

J. Comput. Syst. Sci., 2001

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

Anna Moss, Yuval Rabani

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

Tree packing and approximating k-cuts.

Joseph Naor, Yuval Rabani

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

2000

Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces.

Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani

SIAM J. Comput., 2000

Allocating Bandwidth for Bursty Connections.

Jon M. Kleinberg, Yuval Rabani, Éva Tardos

SIAM J. Comput., 2000

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

Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks

SIAM J. Comput., 2000

An Improved Approximation Algorithm for MULTIWAY CUT.

Gruia Calinescu, Howard J. Karloff, Yuval Rabani

J. Comput. Syst. Sci., 2000

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

Omer Barkol, Yuval Rabani

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

Polynomial Time Approximation Schemes for Geometric k-Clustering.

Rafail Ostrovsky, Yuval Rabani

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

1999

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

Allan Borodin, Rafail Ostrovsky, Yuval Rabani

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

1998

Competitive Algorithms for Layered Graph Traversal.

Amos Fiat, Dean P. Foster, Howard J. Karloff, Yuval Rabani, Yiftach Ravid, Sundar Vishwanathan

SIAM J. Comput., 1998

An <i>O</i>(log <i>k</i>) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm.

Yonatan Aumann, Yuval Rabani

SIAM J. Comput., 1998

A computational view of population genetics.

Yuval Rabani, Yuri Rabinovich, Alistair Sinclair

Random Struct. Algorithms, 1998

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

Claire Kenyon, Yuval Rabani, Alistair Sinclair

J. Algorithms, 1998

Fairness in Scheduling

Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts

J. Algorithms, 1998

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

Yuval Rabani, Alistair Sinclair, Rolf Wanka

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

1997

Deterministic Many-to-Many Hot Potato Routing.

Allan Borodin, Yuval Rabani, Baruch Schieber

IEEE Trans. Parallel Distributed Syst., 1997

Universal <i>O</i>(Congestion + Dilation + log^1+epsilon<i>N</i>) Local Control Packet Switching Algorithms.

Rafail Ostrovsky, Yuval Rabani

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

1996

On the Value of Coordination in Distributed Decision Making.

Sandy Irani, Yuval Rabani

SIAM J. Comput., 1996

Distributed Packet Switching in Arbitrary Networks.

Yuval Rabani, Éva Tardos

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).

Claire Kenyon, Yuval Rabani, Alistair Sinclair

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

Path Coloring on the Mesh.

Yuval Rabani

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

1995

Competitive Algorithms for Distributed Data Management.

Yair Bartal, Amos Fiat, Yuval Rabani

J. Comput. Syst. Sci., 1995

Improved Bounds for All Optical Routing.

Yonatan Aumann, Yuval Rabani

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

1994

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

Howard J. Karloff, Yuval Rabani, Yiftach Ravid

SIAM J. Comput., 1994

Competitive k-Server Algorithms.

Amos Fiat, Yuval Rabani, Yiftach Ravid

J. Comput. Syst. Sci., 1994

A Better Lower Bound for On-Line Scheduling.

Yair Bartal, Howard J. Karloff, Yuval Rabani

Inf. Process. Lett., 1994

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

Amos Fiat, Yuval Rabani, Yiftach Ravid, Baruch Schieber

Algorithmica, 1994

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

Sanjeev Arora, Yuval Rabani, Umesh V. Vazirani

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

Baruch Awerbuch, Rainer Gawlick, Frank Thomson Leighton, Yuval Rabani

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

1993

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

Sandy Irani, Yuval Rabani

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

1992

On the Space Complexity of Some Algorithms for Sequence Comparison.

Yuval Rabani, Zvi Galil

Theor. Comput. Sci., 1992

Competitive Algorithms for Distributed Data Management (Extended Abstract)

Yair Bartal, Amos Fiat, Yuval Rabani

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

A Decomposition Theorem and Bounds for Randomized Server Problems

Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks

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

1990

Competitive k-Server Algorithms (Extended Abstract)

Amos Fiat, Yuval Rabani, Yiftach Ravid

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