Yuval Rabani

ORCID

Publication Activity (10 Years)

Years Active: 1990-2024
Publications (10 Years): 39

Top Venues

Publications

Spencer L. Gordon, Erik Jahn, Bijan Mazaheri, Yuval Rabani, Leonard J. Schulman
Identification of mixtures of discrete product distributions in near-optimal sample and time complexity. COLT (2024)
Yuval Rabani, Leonard J. Schulman, Alistair Sinclair
Diversity in Evolutionary Dynamics. CoRR (2024)
Sébastien Bubeck, Christian Coester, Yuval Rabani
The Randomized k-Server Conjecture Is False! STOC (2023)
Bijan Mazaheri, Spencer Gordon, Yuval Rabani, Leonard J. Schulman
Causal Discovery under Latent Class Confounding. CoRR (2023)
Spencer L. Gordon, Bijan Mazaheri, Yuval Rabani, Leonard J. Schulman
Causal Inference Despite Limited Global Confounding via Mixture Models. CLeaR (2023)
Spencer L. Gordon, Erik Jahn, Bijan Mazaheri, Yuval Rabani, Leonard J. Schulman
Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity. CoRR (2023)
Shichuan Deng, Jian Li, Yuval Rabani
Generalized Unrelated Machine Scheduling Problem. SODA (2023)
Krishnamurthy Dvijotham, Yuval Rabani, Leonard J. Schulman
Convergence of incentive-driven dynamics in Fisher markets. Games Econ. Behav. 134 (2022)
Yuval Rabani, Amir Shpilka
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions. SIAM J. Comput. 51 (5) (2022)
Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Rakesh Venkat
A refined approximation for Euclidean k-means. Inf. Process. Lett. 176 (2022)
Shichuan Deng, Jian Li, Yuval Rabani
Generalized Unrelated Machine Scheduling Problem. CoRR (2022)
Sébastien Bubeck, Christian Coester, Yuval Rabani
Shortest Paths without a Map, but with an Entropic Regularizer. CoRR (2022)
Sébastien Bubeck, Christian Coester, Yuval Rabani
Shortest Paths without a Map, but with an Entropic Regularizer. FOCS (2022)
Shichuan Deng, Jian Li, Yuval Rabani
Approximation algorithms for clustering with dynamic points. J. Comput. Syst. Sci. 130 (2022)
Sébastien Bubeck, Christian Coester, Yuval Rabani
The Randomized k-Server Conjecture is False! CoRR (2022)
Spencer Gordon, Bijan H. Mazaheri, Yuval Rabani, Leonard J. Schulman
Source Identification for Mixtures of Product Distributions. COLT (2021)
Simina Brânzei, Nikhil R. Devanur, Yuval Rabani
Proportional Dynamics in Exchange Economies. EC (2021)
Sandip Banerjee, Rafail Ostrovsky, Yuval Rabani
Min-Sum Clustering (With Outliers). APPROX-RANDOM (2021)
Sébastien Bubeck, Yuval Rabani, Mark Sellke
Online Multiserver Convex Chasing and Optimization. SODA (2021)
Spencer L. Gordon, Bijan Mazaheri, Yuval Rabani, Leonard J. Schulman
Identifying Mixtures of Bayesian Network Distributions. CoRR (2021)
Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Rakesh Venkat
A Refined Approximation for Euclidean k-Means. CoRR (2021)
Shichuan Deng, Jian Li, Yuval Rabani
Approximation Algorithms for Clustering with Dynamic Points. ESA (2020)
Sébastien Bubeck, Yuval Rabani, Mark Sellke
Online Multiserver Convex Chasing and Optimization. CoRR (2020)
Spencer Gordon, Bijan Mazaheri, Leonard J. Schulman, Yuval Rabani
The Sparse Hausdorff Moment Problem, with Application to Topic Models. CoRR (2020)
Sébastien Bubeck, Yuval Rabani
Parametrized Metrical Task Systems. APPROX-RANDOM (2020)
Spencer L. Gordon, Bijan Mazaheri, Yuval Rabani, Leonard J. Schulman
Source Identification for Mixtures of Product Distributions. CoRR (2020)
Sandip Banerjee, Rafail Ostrovsky, Yuval Rabani
Min-Sum Clustering (with Outliers). CoRR (2020)
Shichuan Deng, Jian Li, Yuval Rabani
Approximation Algorithms for Clustering with Dynamic Points. CoRR (2020)
Sébastien Bubeck, Yuval Rabani
Parametrized Metrical Task Systems. CoRR (2019)
Simina Brânzei, Nikhil R. Devanur, Yuval Rabani
Proportional Dynamics in Exchange Economies. CoRR (2019)
Rafail Ostrovsky, Yuval Rabani, Arman Yousefi
Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration. ICALP (2018)
Rafail Ostrovsky, Yuval Rabani, Arman Yousefi
Norms: Bounding the Convergence Rate of Osborne's Iteration. SODA (2017)
Rafail Ostrovsky, Yuval Rabani, Arman Yousefi
Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration. CoRR (2017)
Yuval Rabani, Rakesh Venkat
Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low-Dimensional Spaces. CoRR (2017)
Yuval Rabani, Rakesh Venkat
Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low Dimensional Spaces. APPROX-RANDOM (2017)
Krishnamurthy Dvijotham, Yuval Rabani, Leonard J. Schulman
Convergence of Incentive-Driven Dynamics in Fisher Markets. SODA (2017)
Krishnamurthy Dvijotham, Yuval Rabani, Leonard J. Schulman
Market Dynamics of Best-Response with Lookahead. CoRR (2016)
Rafail Ostrovsky, Yuval Rabani, Arman Yousefi
Matrix Balancing in Lp Norms: A New Analysis of Osborne's Iteration. CoRR (2016)
Yuval Rabani, Andréa W. Richa, Jared Saia, David P. Woodruff
Editorial to the Special Issue on SODA'12. ACM Trans. Algorithms 12 (1) (2016)
Jian Li, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy
Learning Arbitrary Statistical Mixtures of Discrete Distributions. CoRR (2015)
Jian Li, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy
Learning Arbitrary Statistical Mixtures of Discrete Distributions. STOC (2015)
Noa Avigdor-Elgrabli, Yuval Rabani
An Improved Competitive Algorithm for Reordering Buffer Management. ACM Trans. Algorithms 11 (4) (2015)
Noa Avigdor-Elgrabli, Sungjin Im, Benjamin Moseley, Yuval Rabani
On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs. ICALP (1) (2015)
Noa Avigdor-Elgrabli, Yuval Rabani
Convergence of Tâtonnement in Fisher Markets. CoRR (2014)
Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy
Learning mixtures of arbitrary distributions over large discrete domains. ITCS (2014)
Noa Avigdor-Elgrabli, Yuval Rabani
An Optimal Randomized Online Algorithm for Reordering Buffer Management CoRR (2013)
Noa Avigdor-Elgrabli, Yuval Rabani
A Constant Factor Approximation Algorithm for Reordering Buffer Management. SODA (2013)
Noa Avigdor-Elgrabli, Yuval Rabani
An optimal randomized online algorithm for reordering buffer management. FOCS (2013)
Zohar Shay Karnin, Yuval Rabani, Amir Shpilka
Explicit Dimension Reduction and Its Applications. SIAM J. Comput. 41 (1) (2012)
Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh S. Vempala
Local Versus Global Properties of Metric Spaces. SIAM J. Comput. 41 (1) (2012)
Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy
The effectiveness of lloyd-type methods for the k-means problem. J. ACM 59 (6) (2012)
Yuval Rabani
Learning Mixtures of Distributions over Large Discrete Domains. FSTTCS (2012)
Alfonso Cevallos, Serge Fehr, Rafail Ostrovsky, Yuval Rabani
Unconditionally-Secure Robust Secret Sharing with Compact Shares. EUROCRYPT (2012)
Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy
Learning Mixtures of Arbitrary Distributions over Large Discrete Domains CoRR (2012)
Noa Avigdor-Elgrabli, Yuval Rabani
A Constant Factor Approximation Algorithm for Reordering Buffer Management CoRR (2012)
Howard J. Karloff, Flip Korn, Konstantin Makarychev, Yuval Rabani
On Parsimonious Explanations for 2-D Tree- and Linearly-Ordered Data CoRR (2011)
Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, Yuval Rabani
An improved approximation algorithm for resource allocation. ACM Trans. Algorithms 7 (4) (2011)
Zohar Shay Karnin, Yuval Rabani, Amir Shpilka
Explicit Dimension Reduction and Its Applications. Computational Complexity Conference (2011)
Howard J. Karloff, Flip Korn, Konstantin Makarychev, Yuval Rabani
On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data. STACS (2011)
Yuval Rabani, Amir Shpilka
Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions. SIAM J. Comput. 39 (8) (2010)
Yossi Azar, Nikhil R. Devanur, Kamal Jain, Yuval Rabani
Monotonicity in Bargaining Networks. SODA (2010)
Noa Avigdor-Elgrabli, Yuval Rabani
An Improved Competitive Algorithm for Reordering Buffer Management. SODA (2010)
Vladimir Braverman, Rafail Ostrovsky, Yuval Rabani
Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform CoRR (2010)
Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman
Error-correcting codes for automatic control. IEEE Trans. Inf. Theory 55 (7) (2009)
Zohar Shay Karnin, Yuval Rabani, Amir Shpilka
Explicit Dimension Reduction and Its Applications. Electron. Colloquium Comput. Complex. 16 (2009)
Yuval Rabani, Amir Shpilka
Explicit construction of a small epsilon-net for linear threshold functions. STOC (2009)
Yuval Rabani, Gabriel Scalosub
Bicriteria approximation tradeoff for the node-cost budget problem. ACM Trans. Algorithms 5 (2) (2009)
Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani
On Earthmover Distance, Metric Labeling, and 0-Extension. SIAM J. Comput. 39 (2) (2009)
Robert Krauthgamer, Yuval Rabani
$. SIAM J. Comput. 38 (6) (2009)
Claire Kenyon, Yuval Rabani, Alistair Sinclair
Low Distortion Maps Between Point Sets. SIAM J. Comput. 39 (4) (2009)
Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy
Approximation algorithms for labeling hierarchical taxonomies. SODA (2008)
Yuval Rabani, Gabriel Scalosub
Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem. SWAT (2008)
Rafail Ostrovsky, Yuval Rabani
Low distortion embeddings for edit distance. J. ACM 54 (5) (2007)
Anna Moss, Yuval Rabani
Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems. SIAM J. Comput. 37 (2) (2007)
Robert Krauthgamer, Yuval Rabani
. SODA (2006)
Julia Chuzhoy, Rafail Ostrovsky, Yuval Rabani
Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems. Math. Oper. Res. 31 (4) (2006)
Michael Langberg, Yuval Rabani, Chaitanya Swamy
Approximation Algorithms for Graph Homomorphism Problems. APPROX-RANDOM (2006)
Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy
The Effectiveness of Lloyd-Type Methods for the k-Means Problem. FOCS (2006)
Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani
On earthmover distance, metric labeling, and 0-extension. STOC (2006)
Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh S. Vempala
Local versus global properties of metric spaces. SODA (2006)
Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar
On the Hardness of Approximating Multicut and Sparsest-Cut. Comput. Complex. 15 (2) (2006)
Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman
Error-Correcting Codes for Automatic Control. FOCS (2005)
Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar
On the Hardness of Approximating Multicut and Sparsest-Cut. Computational Complexity Conference (2005)
Rafail Ostrovsky, Yuval Rabani
Low distortion embeddings for edit distance. STOC (2005)
Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani
On earthmover distance, metric labeling, and 0-extension Electron. Colloquium Comput. Complex. (064) (2005)
Julia Chuzhoy, Yuval Rabani
Approximating k-median with non-uniform capacities. SODA (2005)
Joseph Cheriyan, Howard J. Karloff, Yuval Rabani
Approximating Directed Multicuts. Comb. 25 (3) (2005)
T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani
Cell-probe lower bounds for the partial match problem. J. Comput. Syst. Sci. 69 (3) (2004)
Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds. J. Interconnect. Networks 5 (1) (2004)
Claire Kenyon, Yuval Rabani, Alistair Sinclair
Low distortion maps between point sets. STOC (2004)
Gruia Calinescu, Howard J. Karloff, Yuval Rabani
Approximation Algorithms for the 0-Extension Problem. SIAM J. Comput. 34 (2) (2004)
Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. Mach. Learn. 56 (1-3) (2004)
Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani
Approximation schemes for clustering problems. STOC (2003)
T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani
Cell-probe lower bounds for the partial match problem. STOC (2003)
Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, Yuval Rabani
Improved Approximation Algorithms for Resource Allocation. IPCO (2002)
Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani
Polynomial Time Approximation Schemes for Metric Min-Sum Clustering Electron. Colloquium Comput. Complex. (025) (2002)
Omer Barkol, Yuval Rabani
Tighter Lower Bounds for Nearest Neighbor Search and Related Problems in the Cell Probe Model. J. Comput. Syst. Sci. 64 (4) (2002)
Rafail Ostrovsky, Yuval Rabani
Polynomial-time approximation schemes for geometric min-sum median clustering. J. ACM 49 (2) (2002)
Yuval Rabani
Search and Classification of High Dimensional Data. APPROX (2002)
Joseph Naor, Yuval Rabani
Tree packing and approximating k-cuts. SODA (2001)

Yuval Rabani.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Yuval Rabani