Y. Rabani

Most-cited papers

The Effectiveness of Lloyd-Type Methods for the k-Means Problem
R. Ostrovsky, Y. Rabani, L. Schulman, Chaitanya Swamy
2006IEEE Annual Symposium on Foundations of Computer Science532 citations Open access
Semantic Scholar
ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT
Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Y. Rabani +1 more
2005Cybersecurity and Cyberforensics Conference270 citations Open access
Semantic Scholar
Approximation algorithms for the 0-extension problem
G. Călinescu, H. Karloff, Y. Rabani
2001ACM-SIAM Symposium on Discrete Algorithms181 citations Open access
Semantic Scholar
Approximation schemes for clustering problems
W. Fernandez de la Véga, M. Karpinski, C. Kenyon, Y. Rabani
2003Symposium on the Theory of Computing175 citations
Semantic Scholar
Improved lower bounds for embeddings into L1
Robert Krauthgamer, Y. Rabani
2006ACM-SIAM Symposium on Discrete Algorithms100 citations Open access
Semantic Scholar
Low distortion embeddings for edit distance
R. Ostrovsky, Y. Rabani
2005Symposium on the Theory of Computing92 citations
Semantic Scholar
Improved Approximation Algorithms for Resource Allocation
G. Călinescu, Amit Chakrabarti, H. Karloff, Y. Rabani
2002Conference on Integer Programming and Combinatorial Optimization92 citations
Semantic Scholar
Approximating k-median with non-uniform capacities
Julia Chuzhoy, Y. Rabani
2005ACM-SIAM Symposium on Discrete Algorithms68 citations
Semantic Scholar
Polynomial-time approximation schemes for geometric min-sum median clustering
R. Ostrovsky, Y. Rabani
2002JACM64 citations
Semantic Scholar
Low distortion maps between point sets
C. Kenyon, Y. Rabani, A. Sinclair
2004Symposium on the Theory of Computing59 citations
Semantic Scholar
Approximation algorithms for constrained for constrained node weighted steiner tree problems
Anna Moss, Y. Rabani
2001Symposium on the Theory of Computing55 citations Open access
Semantic Scholar
Unconditionally-Secure Robust Secret Sharing with Compact Shares
Alfonso Cevallos, S. Fehr, R. Ostrovsky, Y. Rabani
2012International Conference on the Theory and Application of Cryptographic Techniques54 citations Open access
Semantic Scholar
Error-correcting codes for automatic control
R. Ostrovsky, Y. Rabani, L. Schulman
2005IEEE Annual Symposium on Foundations of Computer Science51 citations
Semantic Scholar
Approximating Directed Multicuts
J. Cheriyan, H. Karloff, Y. Rabani
2001Proceedings IEEE International Conference on Cluster Computing50 citations
Semantic Scholar
Cell-probe lower bounds for the partial match problem
T. S. Jayram, Subhash Khot, Ravi Kumar, Y. Rabani
2003Symposium on the Theory of Computing47 citations Open access
Semantic Scholar
Explicit construction of a small epsilon-net for linear threshold functions
Y. Rabani, Amir Shpilka
2009Symposium on the Theory of Computing46 citations
Semantic Scholar
Learning mixtures of arbitrary distributions over large discrete domains
Y. Rabani, L. Schulman, Chaitanya Swamy
2012Information Technology Convergence and Services39 citations
Semantic Scholar
An improved approximation algorithm for resource allocation
G. Călinescu, Amit Chakrabarti, H. Karloff, Y. Rabani
2011TALG39 citations
Semantic Scholar
Tree packing and approximating k-cuts
J. Naor, Y. Rabani
2001ACM-SIAM Symposium on Discrete Algorithms39 citations
Semantic Scholar
Stability preserving transformations: packet routing networks with edge capacities and speeds
A. Borodin, R. Ostrovsky, Y. Rabani
2001ACM-SIAM Symposium on Discrete Algorithms37 citations
Semantic Scholar
The Randomized 𝑘-Server Conjecture Is False!
Sébastien Bubeck, Christian Coester, Y. Rabani
2022Symposium on the Theory of Computing36 citations Open access
Semantic Scholar
Proportional Dynamics in Exchange Economies
Simina Brânzei, Nikhil R. Devanur, Y. Rabani
2019ACM Conference on Economics and Computation35 citations Open access
Semantic Scholar
Linear Programming
Y. Rabani
2007Handbook of Approximation Algorithms and Metaheuristics32 citations
Semantic Scholar
Approximation Algorithms for Graph Homomorphism Problems
M. Langberg, Y. Rabani, Chaitanya Swamy
2006International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques30 citations
Semantic Scholar
On Lipschitz extension from finite subsets
A. Naor, Y. Rabani
201529 citations Open access
Semantic Scholar
Explicit Dimension Reduction and Its Applications
Zohar S. Karnin, Y. Rabani, Amir Shpilka
20112011 IEEE 26th Annual Conference on Computational Complexity29 citations Open access
Semantic Scholar
An Improved Competitive Algorithm for Reordering Buffer Management
Noa Avigdor-Elgrabli, Y. Rabani
2013IEEE Annual Symposium on Foundations of Computer Science28 citations
Semantic Scholar
Local Versus Global Properties of Metric Spaces
Sanjeev Arora, L. Lovász, Ilan Newman, Y. Rabani +2 more
2011SIAM journal on computing (Print)28 citations Open access
Semantic Scholar
On earthmover distance, metric labeling, and 0-extension
H. Karloff, Subhash Khot, Aranyak Mehta, Y. Rabani
2006Symposium on the Theory of Computing28 citations
Semantic Scholar
Source Identification for Mixtures of Product Distributions
Spencer Gordon, Bijan Mazaheri, Y. Rabani, L. Schulman
2020Annual Conference Computational Learning Theory26 citations
Semantic Scholar
Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform
V. Braverman, R. Ostrovsky, Y. Rabani
2010arXiv.org26 citations
Semantic Scholar
A Refined Approximation for Euclidean k-Means
F. Grandoni, R. Ostrovsky, Y. Rabani, L. Schulman +1 more
2021Information Processing Letters23 citations Open access
Semantic Scholar
An optimal randomized online algorithm for reordering buffer management
Noa Avigdor-Elgrabli, Y. Rabani
2013IEEE Annual Symposium on Foundations of Computer Science23 citations Open access
Semantic Scholar
Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
A. Naor, Y. Rabani, A. Sinclair
200522 citations Open access
Semantic Scholar
Learning Arbitrary Statistical Mixtures of Discrete Distributions
Jian Li, Y. Rabani, L. Schulman, Chaitanya Swamy
2015Symposium on the Theory of Computing21 citations Open access
Semantic Scholar
Shortest Paths without a Map, but with an Entropic Regularizer
Sébastien Bubeck, Christian Coester, Y. Rabani
2022IEEE Annual Symposium on Foundations of Computer Science18 citations
Semantic Scholar
A Constant Factor Approximation Algorithm for Reordering Buffer Management
Noa Avigdor-Elgrabli, Y. Rabani
2012ACM-SIAM Symposium on Discrete Algorithms18 citations
Semantic Scholar
Polynomial Time Approximation Schemes for Metric Min-Sum Clustering
W. F. de la Vega, M. Karpinski, C. Kenyon, Y. Rabani
2002Electron. Colloquium Comput. Complex.17 citations
Semantic Scholar
Matrix Balancing in Lp Norms: Bounding the Convergence Rate of Osborne's Iteration
R. Ostrovsky, Y. Rabani, A. Yousefi
2017ACM-SIAM Symposium on Discrete Algorithms16 citations
Semantic Scholar
Generalized Unrelated Machine Scheduling Problem
Shichuan Deng, Jun Yu Li, Y. Rabani
2022ACM-SIAM Symposium on Discrete Algorithms12 citations Open access
Semantic Scholar
Convergence of Tâtonnement in Fisher Markets
Noa Avigdor-Elgrabli, Y. Rabani
2014arXiv.org11 citations
Semantic Scholar
Error-Correcting Codes for Automatic Control
R. Ostrovsky, Y. Rabani, L. Schulman
2009IEEE Transactions on Information Theory11 citations Open access
Semantic Scholar
Causal Inference Despite Limited Global Confounding via Mixture Models
Spencer Gordon, Bijan Mazaheri, Y. Rabani, L. Schulman
2021CLEaR10 citations
Semantic Scholar
The Sparse Hausdorff Moment Problem, with Application to Topic Models
Spencer Gordon, Bijan Mazaheri, Y. Rabani, L. Schulman
2020arXiv.org10 citations
Semantic Scholar
Convergence of Incentive-Driven Dynamics in Fisher Markets
K. Dvijotham, Y. Rabani, L. Schulman
2017ACM-SIAM Symposium on Discrete Algorithms10 citations Open access
Semantic Scholar
On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs
Noa Avigdor-Elgrabli, Sung-Jin Im, Benjamin Moseley, Y. Rabani
2015International Colloquium on Automata, Languages and Programming10 citations Open access
Semantic Scholar
Corrigendum: Explicit Construction of a Small ε -Net for Linear Threshold Functions
Y. Rabani, Amir Shpilka
20228 citations
Semantic Scholar
On Parsimonious Explanations for 2-D Tree- and Linearly-Ordered Data
H. Karloff, F. Korn, K. Makarychev, Y. Rabani
2011Symposium on Theoretical Aspects of Computer Science8 citations
Semantic Scholar
Monotonicity in bargaining networks
Y. Azar, Nikhil R. Devanur, K. Jain, Y. Rabani
2010ACM-SIAM Symposium on Discrete Algorithms8 citations
Semantic Scholar
Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity
Spencer Gordon, Erik Jahn, Bijan Mazaheri, Y. Rabani +1 more
2023Annual Conference Computational Learning Theory7 citations Open access
Semantic Scholar