Yuval Rabani

Noa Avigdor-Elgrabli, Yuval Rabani: A Constant Factor Approximation Algorithm for Reordering Buffer Management. SODA 2013: 973-984

Noa Avigdor-Elgrabli, Yuval Rabani: An Optimal Randomized Online Algorithm for Reordering Buffer Management. CoRR abs/1303.3386 (2013)

Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy: The effectiveness of lloyd-type methods for the k-means problem. J. ACM 59(6): 28 (2012)

Zohar Shay Karnin, Yuval Rabani, Amir Shpilka: Explicit Dimension Reduction and Its Applications. SIAM J. Comput. 41(1): 219-249 (2012)

Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala: Local Versus Global Properties of Metric Spaces. SIAM J. Comput. 41(1): 250-271 (2012)

Alfonso Cevallos, Serge Fehr, Rafail Ostrovsky, Yuval Rabani: Unconditionally-Secure Robust Secret Sharing with Compact Shares. EUROCRYPT 2012: 195-208

Yuval Rabani: Learning Mixtures of Distributions over Large Discrete Domains. FSTTCS 2012: 1-3

Yuval Rabani (Ed.): Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012. SIAM 2012

Noa Avigdor-Elgrabli, Yuval Rabani: A Constant Factor Approximation Algorithm for Reordering Buffer Management. CoRR abs/1202.4504 (2012)

Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy: Learning Mixtures of Arbitrary Distributions over Large Discrete Domains. CoRR abs/1212.1527 (2012)

Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, Yuval Rabani: An improved approximation algorithm for resource allocation. ACM Transactions on Algorithms 7(4): 48 (2011)

Zohar Shay Karnin, Yuval Rabani, Amir Shpilka: Explicit Dimension Reduction and Its Applications. IEEE Conference on Computational Complexity 2011: 262-272

Howard J. Karloff, Flip Korn, Konstantin Makarychev, Yuval Rabani: On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data. STACS 2011: 332-343

Howard J. Karloff, Flip Korn, Konstantin Makarychev, Yuval Rabani: On Parsimonious Explanations for 2-D Tree- and Linearly-Ordered Data. CoRR abs/1101.1941 (2011)

Yuval Rabani, Amir Shpilka: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions. SIAM J. Comput. 39(8): 3501-3520 (2010)

Noa Avigdor-Elgrabli, Yuval Rabani: An Improved Competitive Algorithm for Reordering Buffer Management. SODA 2010: 13-21

Yossi Azar, Nikhil R. Devanur, Kamal Jain, Yuval Rabani: Monotonicity in Bargaining Networks. SODA 2010: 817-826

Vladimir Braverman, Rafail Ostrovsky, Yuval Rabani: Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform. CoRR abs/1011.2590 (2010)

Robert Krauthgamer, Yuval Rabani: Improved Lower Bounds for Embeddings intoL₁$. SIAM J. Comput. 38(6): 2487-2498 (2009)

Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani: On Earthmover Distance, Metric Labeling, and 0-Extension. SIAM J. Comput. 39(2): 371-387 (2009)

Claire Kenyon, Yuval Rabani, Alistair Sinclair: Low Distortion Maps Between Point Sets. SIAM J. Comput. 39(4): 1617-1636 (2009)

Yuval Rabani, Gabriel Scalosub: Bicriteria approximation tradeoff for the node-cost budget problem. ACM Transactions on Algorithms 5(2) (2009)

Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman: Error-correcting codes for automatic control. IEEE Transactions on Information Theory 55(7): 2931-2941 (2009)

Yuval Rabani, Amir Shpilka: Explicit construction of a small epsilon-net for linear threshold functions. STOC 2009: 649-658

Zohar Shay Karnin, Yuval Rabani, Amir Shpilka: Explicit Dimension Reduction and Its Applications. Electronic Colloquium on Computational Complexity (ECCC) 16: 121 (2009)

Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy: Approximation algorithms for labeling hierarchical taxonomies. SODA 2008: 671-680

Yuval Rabani, Gabriel Scalosub: Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem. SWAT 2008: 90-101

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): 460-481 (2007)

Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar: On the Hardness of Approximating Multicut and Sparsest-Cut. Computational Complexity 15(2): 94-114 (2006)

Julia Chuzhoy, Rafail Ostrovsky, Yuval Rabani: Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems. Math. Oper. Res. 31(4): 730-738 (2006)

Michael Langberg, Yuval Rabani, Chaitanya Swamy: Approximation Algorithms for Graph Homomorphism Problems. APPROX-RANDOM 2006: 176-187

Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy: The Effectiveness of Lloyd-Type Methods for the k-Means Problem. FOCS 2006: 165-176

Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala: Local versus global properties of metric spaces. SODA 2006: 41-50

Robert Krauthgamer, Yuval Rabani: Improved lower bounds for embeddings into L₁. SODA 2006: 1010-1017

Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani: On earthmover distance, metric labeling, and 0-extension. STOC 2006: 547-556

Joseph Cheriyan, Howard J. Karloff, Yuval Rabani: Approximating Directed Multicuts. Combinatorica 25(3): 251-269 (2005)

Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar: On the Hardness of Approximating Multicut and Sparsest-Cut. IEEE Conference on Computational Complexity 2005: 144-153

Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman: Error-Correcting Codes for Automatic Control. FOCS 2005: 309-316

Julia Chuzhoy, Yuval Rabani: Approximating k-median with non-uniform capacities. SODA 2005: 952-958

Rafail Ostrovsky, Yuval Rabani: Low distortion embeddings for edit distance. STOC 2005: 218-224

Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani: On earthmover distance, metric labeling, and 0-extension. Electronic Colloquium on Computational Complexity (ECCC)(064) (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): 435-447 (2004)

Allan Borodin, Rafail Ostrovsky, Yuval Rabani: Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds. Journal of Interconnection Networks 5(1): 1-12 (2004)

Allan Borodin, Rafail Ostrovsky, Yuval Rabani: Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. Machine Learning 56(1-3): 153-167 (2004)

Gruia Calinescu, Howard J. Karloff, Yuval Rabani: Approximation Algorithms for the 0-Extension Problem. SIAM J. Comput. 34(2): 358-372 (2004)

Claire Kenyon, Yuval Rabani, Alistair Sinclair: Low distortion maps between point sets. STOC 2004: 272-280

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani: Approximation schemes for clustering problems. STOC 2003: 50-58

T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani: Cell-probe lower bounds for the partial match problem. STOC 2003: 667-672

Rafail Ostrovsky, Yuval Rabani: Polynomial-time approximation schemes for geometric min-sum median clustering. J. ACM 49(2): 139-156 (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): 873-896 (2002)

Yuval Rabani: Search and Classification of High Dimensional Data. APPROX 2002: 1-2

Gruia Calinescu, Amit Chakrabarti, Howard J. Karloff, Yuval Rabani: Improved Approximation Algorithms for Resource Allocation. IPCO 2002: 401-414

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani: Polynomial Time Approximation Schemes for Metric Min-Sum Clustering. Electronic Colloquium on Computational Complexity (ECCC)(025) (2002)

Jon M. Kleinberg, Yuval Rabani, Éva Tardos: Fairness in Routing and Load Balancing. J. Comput. Syst. Sci. 63(1): 2-20 (2001)

Joseph Cheriyan, Howard J. Karloff, Yuval Rabani: Approximating Directed Multicuts. FOCS 2001: 320-328

Julia Chuzhoy, Rafail Ostrovsky, Yuval Rabani: Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems. FOCS 2001: 348-356

Gruia Calinescu, Howard J. Karloff, Yuval Rabani: Approximation algorithms for the 0-extension problem. SODA 2001: 8-16

Joseph Naor, Yuval Rabani: Tree packing and approximating k-cuts. SODA 2001: 26-27

Allan Borodin, Rafail Ostrovsky, Yuval Rabani: Stability preserving transformations: packet routing networks with edge capacities and speeds. SODA 2001: 601-610

Anna Moss, Yuval Rabani: Approximation algorithms for constrained for constrained node weighted steiner tree problems. STOC 2001: 373-382

Gruia Calinescu, Howard J. Karloff, Yuval Rabani: An Improved Approximation Algorithm for MULTIWAY CUT. J. Comput. Syst. Sci. 60(3): 564-574 (2000)

Jon M. Kleinberg, Yuval Rabani, Éva Tardos: Allocating Bandwidth for Bursty Connections. SIAM J. Comput. 30(1): 191-217 (2000)

Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani: Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces. SIAM J. Comput. 30(2): 457-474 (2000)

Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks: A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems. SIAM J. Comput. 30(5): 1624-1661 (2000)

Rafail Ostrovsky, Yuval Rabani: Polynomial Time Approximation Schemes for Geometric k-Clustering. FOCS 2000: 349-358

Omer Barkol, Yuval Rabani: Tighter bounds for nearest neighbor search and related problems in the cell probe model. STOC 2000: 388-396

Jon M. Kleinberg, Yuval Rabani, Éva Tardos: Fairness in Routing and Load Balancing. FOCS 1999: 568-578

Allan Borodin, Rafail Ostrovsky, Yuval Rabani: Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems. STOC 1999: 312-321

Allan Borodin, Rafail Ostrovsky, Yuval Rabani: Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. STOC 1999: 435-444

Claire Kenyon, Yuval Rabani, Alistair Sinclair: Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing. J. Algorithms 27(2): 218-235 (1998)

Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts: Fairness in Scheduling. J. Algorithms 29(2): 306-357 (1998)

Yuval Rabani, Yuri Rabinovich, Alistair Sinclair: A computational view of population genetics. Random Struct. Algorithms 12(4): 313-334 (1998)

Yonatan Aumann, Yuval Rabani: An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm. SIAM J. Comput. 27(1): 291-301 (1998)

Amos Fiat, Dean P. Foster, Howard J. Karloff, Yuval Rabani, Yiftach Ravid, Sundar Vishwanathan: Competitive Algorithms for Layered Graph Traversal. SIAM J. Comput. 28(2): 447-462 (1998)

Yuval Rabani, Alistair Sinclair, Rolf Wanka: Local Divergence of Markov Chains and the Analysis of Iterative Load Balancing Schemes. FOCS 1998: 694-705

Gruia Calinescu, Howard J. Karloff, Yuval Rabani: An Improved Approximation Algorithm for Multiway Cut. STOC 1998: 48-52

Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani: Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces. STOC 1998: 614-623

Allan Borodin, Yuval Rabani, Baruch Schieber: Deterministic Many-to-Many Hot Potato Routing. IEEE Trans. Parallel Distrib. Syst. 8(6): 587-596 (1997)

Rafail Ostrovsky, Yuval Rabani: Universal O(Congestion + Dilation + log^1+epsilonN) Local Control Packet Switching Algorithms. STOC 1997: 644-653

Jon M. Kleinberg, Yuval Rabani, Éva Tardos: Allocating Bandwidth for Bursty Connections. STOC 1997: 664-673

Sandy Irani, Yuval Rabani: On the Value of Coordination in Distributed Decision Making. SIAM J. Comput. 25(3): 498-519 (1996)

Yuval Rabani: Path Coloring on the Mesh. FOCS 1996: 400-409

Claire Kenyon, Yuval Rabani, Alistair Sinclair: Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing (Preliminary Version). SODA 1996: 351-358

Yuval Rabani, Éva Tardos: Distributed Packet Switching in Arbitrary Networks. STOC 1996: 366-375

Yair Bartal, Amos Fiat, Yuval Rabani: Competitive Algorithms for Distributed Data Management. J. Comput. Syst. Sci. 51(3): 341-358 (1995)

Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts: Fairness in Scheduling. SODA 1995: 477-485

Yonatan Aumann, Yuval Rabani: Improved Bounds for All Optical Routing. SODA 1995: 567-576

Yuval Rabani, Yuri Rabinovich, Alistair Sinclair: A computational view of population genetics. STOC 1995: 83-92

Amos Fiat, Yuval Rabani, Yiftach Ravid, Baruch Schieber: A Deterministic O(k³)-Competitive k-Server Algorithm for the Circle. Algorithmica 11(6): 572-578 (1994)

Yair Bartal, Howard J. Karloff, Yuval Rabani: A Better Lower Bound for On-Line Scheduling. Inf. Process. Lett. 50(3): 113-116 (1994)

Amos Fiat, Yuval Rabani, Yiftach Ravid: Competitive k-Server Algorithms. J. Comput. Syst. Sci. 48(3): 410-428 (1994)

Howard J. Karloff, Yuval Rabani, Yiftach Ravid: Lower Bounds for Randomized k-Server and Motion-Planning Algorithms. SIAM J. Comput. 23(2): 293-312 (1994)

Baruch Awerbuch, Rainer Gawlick, Frank Thomson Leighton, Yuval Rabani: On-line Admission Control and Circuit Routing for High Performance Computing and Communication. FOCS 1994: 412-423

Sanjeev Arora, Yuval Rabani, Umesh V. Vazirani: Simulating quadratic dynamical systems is PSPACE-complete (preliminary version). STOC 1994: 459-467

Sandy Irani, Yuval Rabani: On the Value of Information in Coordination Games (preliminary version). FOCS 1993: 12-21

Yuval Rabani, Zvi Galil: On the Space Complexity of Some Algorithms for Sequence Comparison. Theor. Comput. Sci. 95(2): 231-244 (1992)

Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks: A Decomposition Theorem and Bounds for Randomized Server Problems. FOCS 1992: 197-207

Yair Bartal, Amos Fiat, Yuval Rabani: Competitive Algorithms for Distributed Data Management (Extended Abstract). STOC 1992: 39-50

Amos Fiat, Dean P. Foster, Howard J. Karloff, Yuval Rabani, Yiftach Ravid, Sundar Vishwanathan: Competitive Algorithms for Layered Graph Traversal. FOCS 1991: 288-297

Howard J. Karloff, Yuval Rabani, Yiftach Ravid: Lower Bounds for Randomized k-Server and Motion Planning Algorithms. STOC 1991: 278-288

Amos Fiat, Yuval Rabani, Yiftach Ravid: Competitive k-Server Algorithms (Extended Abstract). FOCS 1990: 454-463