Ronitt Rubinfeld

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam Smith: Sublinear Algorithms for Approximating String Compressibility. Algorithmica 65(3): 685-709 (2013)

Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: Testing Closeness of Discrete Distributions. J. ACM 60(1): 4 (2013)

Reut Levi, Dana Ron, Ronitt Rubinfeld: Testing Properties of Collections of Distributions. Theory of Computing 9: 295-347 (2013)

Akashnil Dutta, Reut Levi, Dana Ron, Ronitt Rubinfeld: A simple online competitive adaptation of Lempel-Ziv compression with efficient random access support. CoRR abs/1301.2495 (2013)

Ronitt Rubinfeld: Taming big probability distributions. ACM Crossroads 19(1): 24-28 (2012)

Dana Ron, Ronitt Rubinfeld, Muli Safra, Alex Samorodnitsky, Omri Weinstein: Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity. TOCT 4(4): 11 (2012)

Reut Levi, Dana Ron, Ronitt Rubinfeld: Testing Similar Means. ICALP (1) 2012: 629-640

Piotr Indyk, Reut Levi, Ronitt Rubinfeld: Approximating and testing k-histogram distributions in sub-linear time. PODS 2012: 15-22

Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld: A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. SODA 2012: 1123-1131

Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie: Space-efficient local computation algorithms. SODA 2012: 1132-1139

Andrea Campagna, Alan Guo, Ronitt Rubinfeld: Local reconstructors and tolerant testers for connectivity and diameter. CoRR abs/1208.2956 (2012)

Reut Levi, Dana Ron, Ronitt Rubinfeld: Testing Similar Means. Electronic Colloquium on Computational Complexity (ECCC) 19: 55 (2012)

Piotr Indyk, Reut Levi, Ronitt Rubinfeld: Approximating and Testing k-Histogram Distributions in Sub-linear time. Electronic Colloquium on Computational Complexity (ECCC) 18: 171 (2011)

Khanh Do Ba, Huy L. Nguyen, Huy N. Nguyen, Ronitt Rubinfeld: Sublinear Time Algorithms for Earth Mover's Distance. Theory Comput. Syst. 48(2): 428-442 (2011)

Ronitt Rubinfeld, Asaf Shapira: Sublinear Time Algorithms. SIAM J. Discrete Math. 25(4): 1562-1588 (2011)

Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein: Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity. APPROX-RANDOM 2011: 664-675

Reut Levi, Dana Ron, Ronitt Rubinfeld: Testing Properties of Collections of Distributions. ICS 2011: 179-194

Ronitt Rubinfeld, Gil Tamir, Shai Vardi, Ning Xie: Fast Local Computation Algorithms. ICS 2011: 223-238

Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant: Testing monotonicity of distributions over general partial orders. ICS 2011: 239-252

Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein: Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity. CoRR abs/1101.5345 (2011)

Ronitt Rubinfeld, Gil Tamir, Shai Vardi, Ning Xie: Fast Local Computation Algorithms. CoRR abs/1104.1377 (2011)

Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie: Space-efficient Local Computation Algorithms. CoRR abs/1109.6178 (2011)

Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld: A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size. CoRR abs/1110.1079 (2011)

Ronitt Rubinfeld, Asaf Shapira: Sublinear Time Algorithms. Electronic Colloquium on Computational Complexity (ECCC) 18: 13 (2011)

Elena Grigorescu, Kyomin Jung, Ronitt Rubinfeld: A local decision test for sparse polynomials. Inf. Process. Lett. 110(20): 898-901 (2010)

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio: Testing Halfspaces. SIAM J. Comput. 39(5): 2004-2047 (2010)

Ronitt Rubinfeld, Ning Xie: Testing Non-uniform k-Wise Independent Distributions over Product Spaces. ICALP (1) 2010: 565-581

Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld: Sublinear Algorithms in the External Memory Model. Property Testing 2010: 240-243

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio: Testing (Subclasses of) Halfspaces. Property Testing 2010: 334-340

Krzysztof Onak, Ronitt Rubinfeld: Dynamic Approximate Vertex Cover and Maximum Matching. Property Testing 2010: 341-345

Krzysztof Onak, Ronitt Rubinfeld: Maintaining a large matching and a small vertex cover. STOC 2010: 457-464

Rubi Boim, Haim Kaplan, Tova Milo, Ronitt Rubinfeld: Improved Recommendations via (More) Collaboration. WebDB 2010

Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: Testing Closeness of Discrete Distributions. CoRR abs/1009.5397 (2010)

Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant: Testing monotonicity of distributions over general partial orders. Electronic Colloquium on Computational Complexity (ECCC) 17: 27 (2010)

Reut Levi, Dana Ron, Ronitt Rubinfeld: Testing Properties of Collections of Distributions. Electronic Colloquium on Computational Complexity (ECCC) 17: 157 (2010)

Ronitt Rubinfeld, Rocco A. Servedio: Testing monotone high-dimensional distributions. Random Struct. Algorithms 34(1): 24-44 (2009)

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio: Testing ±1-weight halfspace. APPROX-RANDOM 2009: 646-657

Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld: External Sampling. ICALP (1) 2009: 83-94

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio: Testing halfspaces. SODA 2009: 256-264

Khanh Do Ba, Huy L. Nguyen, Huy N. Nguyen, Ronitt Rubinfeld: Sublinear Time Algorithms for Earth Mover's Distance. CoRR abs/0904.0292 (2009)

Michael Ben-Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld: Non-abelian homomorphism testing, and distributions close to their self-convolutions. Random Struct. Algorithms 32(1): 49-70 (2008)

Ronitt Rubinfeld: Linearity Testing/Testing Hadamard Codes. Encyclopedia of Algorithms 2008

Ashish Goel, Klaus Jansen, José D. P. Rolim, Ronitt Rubinfeld (Eds.): Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008. Proceedings. Lecture Notes in Computer Science 5171, Springer 2008, isbn 978-3-540-85362-6

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam Smith: Sublinear Algorithms for Approximating String Compressibility. APPROX-RANDOM 2007: 609-623

Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan: Testing for Concise Representations. FOCS 2007: 549-558

Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie: Testing k-wise and almost k-wise independence. STOC 2007: 496-505

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam Smith: Sublinear Algorithms for Approximating String Compressibility. CoRR abs/0706.1084 (2007)

Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan: Testing for Concise Representations. Electronic Colloquium on Computational Complexity (ECCC) 14(077) (2007)

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio: Testing Halfspaces. Electronic Colloquium on Computational Complexity (ECCC) 14(128) (2007)

Michal Parnas, Dana Ron, Ronitt Rubinfeld: Tolerant property testing and distance approximation. J. Comput. Syst. Sci. 72(6): 1012-1042 (2006)

Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler (Eds.): Sublinear Algorithms, 17.07. - 22.07.2005. Dagstuhl Seminar Proceedings 05291, Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany 2006

Tugkan Batu, Ronitt Rubinfeld, Patrick White: Fast approximate PCPs for multidimensional bin-packing problems. Inf. Comput. 196(1): 42-56 (2005)

Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan: Approximating the Minimum Spanning Tree Weight in Sublinear Time. SIAM J. Comput. 34(6): 1370-1379 (2005)

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler: Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time. SIAM J. Comput. 35(1): 91-109 (2005)

Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld: The Complexity of Approximating the Entropy. SIAM J. Comput. 35(1): 132-150 (2005)

Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler: 05291 Abstracts Collection -- Sublinear Algorithms. Sublinear Algorithms 2005

Ronitt Rubinfeld, Rocco A. Servedio: Testing monotone high-dimensional distributions. STOC 2005: 147-156

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam Smith: Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size. Electronic Colloquium on Computational Complexity (ECCC)(125) (2005)

Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: Fast approximate probabilistically checkable proofs. Inf. Comput. 189(2): 135-159 (2004)

Michael Ben-Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld: Non-Abelian Homomorphism Testing, and Distributions Close to Their Self-convolutions. APPROX-RANDOM 2004: 273-285

Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, Ayellet Tal: The Bloomier filter: an efficient data structure for static support lookup tables. SODA 2004: 30-39

Tugkan Batu, Ravi Kumar, Ronitt Rubinfeld: Sublinear algorithms for testing monotone and unimodal distributions. STOC 2004: 381-390

Michal Parnas, Dana Ron, Ronitt Rubinfeld: Tolerant Property Testing and Distance Approximation. Electronic Colloquium on Computational Complexity (ECCC)(010) (2004)

Michael Ben-Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld: Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions. Electronic Colloquium on Computational Complexity (ECCC)(052) (2004)

Michal Parnas, Dana Ron, Ronitt Rubinfeld: Testing membership in parenthesis languages. Random Struct. Algorithms 22(1): 98-138 (2003)

Michal Parnas, Dana Ron, Ronitt Rubinfeld: On Testing Convexity and Submodularity. SIAM J. Comput. 32(5): 1158-1184 (2003)

Ravi Kumar, Ronitt Rubinfeld: Algorithms column: sublinear time algorithms. SIGACT News 34(4): 57-67 (2003)

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler: Sublinear-time approximation of Euclidean minimum spanning tree. SODA 2003: 813-822

Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami: A sublinear algorithm for weakly approximating edit distance. STOC 2003: 316-324

Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld: The Complexity of Approximating the Entropy. IEEE Conference on Computational Complexity 2002: 17

Michal Parnas, Dana Ron, Ronitt Rubinfeld: On Testing Convexity and Submodularity. RANDOM 2002: 11-25

Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky: Monotonicity testing over general poset domains. STOC 2002: 474-483

Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld: The complexity of approximating entropy. STOC 2002: 678-687

Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: Checking Approximate Computations of Polynomials and Functional Equations. SIAM J. Comput. 31(2): 550-576 (2001)

Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, Patrick White: Testing Random Variables for Independence and Identity. FOCS 2001: 442-451

Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan: Approximating the Minimum Spanning Tree Weight in Sublinear Time. ICALP 2001: 190-200

Ran Canetti, Yuval Ishai, Ravi Kumar, Michael K. Reiter, Ronitt Rubinfeld, Rebecca N. Wright: Selective private function evaluation with applications to private statistics. PODC 2001: 293-304

Michal Parnas, Dana Ron, Ronitt Rubinfeld: Testing Parenthesis Languages. RANDOM-APPROX 2001: 261-272

Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan: Spot-Checkers. J. Comput. Syst. Sci. 60(3): 717-751 (2000)

Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan: Learning Polynomials with Queries: The Highly Noisy Case. SIAM J. Discrete Math. 13(4): 535-570 (2000)

Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: Testing that distributions are close. FOCS 2000: 259-269

Ronald Fagin, Anna R. Karlin, Jon M. Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, Madhu Sudan, Andrew Tomkins: Random walks with ``back buttons'' (extended abstract). STOC 2000: 484-493

Ronitt Rubinfeld: On the Robustness of Functional Equations. SIAM J. Comput. 28(6): 1972-1997 (1999)

Tugkan Batu, Ronitt Rubinfeld, Patrick White: Fast Approximate PCPs for Multidimensional Bin-Packing Problems. RANDOM-APPROX 1999: 245-256

Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: Fast Approximate PCPs. STOC 1999: 41-50

Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan: Reconstructing Algebraic Functions from Mixed Data. SIAM J. Comput. 28(2): 487-510 (1998)

Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan: Spot-Checkers. STOC 1998: 259-268

Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan: Learning Polynomials with Queries - The Highly Noisy Case. Electronic Colloquium on Computational Complexity (ECCC) 5(60) (1998)

Yoav Freund, Michael J. Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie: Efficient Learning of Typical Finite Automata from Random Walks. Inf. Comput. 138(1): 23-48 (1997)

Dana Ron, Ronitt Rubinfeld: Exactly Learning Automata of Small Cover Time. Machine Learning 27(1): 69-96 (1997)

Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: Learning Distributions from Random Walks. COLT 1997: 243-249

Ronitt Rubinfeld: Designing Checkers for Programs that Run in Parallel. Algorithmica 15(4): 287-301 (1996)

Ronitt Rubinfeld, Madhu Sudan: Robust Characterizations of Polynomials with Applications to Program Testing. SIAM J. Comput. 25(2): 252-271 (1996)

Jon M. Kleinberg, Ronitt Rubinfeld: Short Paths in Expander Graphs. FOCS 1996: 86-95

Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: Approximate Checking of Polynomials and Functional Equations (extended abstract). FOCS 1996: 592-601

Dana Ron, Ronitt Rubinfeld: Learning Fallible Deterministic Finite Automata. Machine Learning 18(2-3): 149-185 (1995)

Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: On Learning Bounded-Width Branching Programs. COLT 1995: 361-368

Dana Ron, Ronitt Rubinfeld: Exactly Learning Automata with Small Cover Time. COLT 1995: 427-436

Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan: Learning Polynomials with Queries: The Highly Noisy Case. FOCS 1995: 294-303

Yoav Freund, Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire: Efficient Algorithms for Learning to Play Repeated Games Against Computationally Bounded Adversaries. FOCS 1995: 332-341

Ronitt Rubinfeld, Richard Zippel: A new modular interpolation algorithm for factoring multivariate polynominals. ANTS 1994: 93-107

Ronitt Rubinfeld: On the robustness of functional equations. FOCS 1994: 288-299

Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie: On the learnability of discrete distributions. STOC 1994: 273-282

Manuel Blum, Michael Luby, Ronitt Rubinfeld: Self-Testing/Correcting with Applications to Numerical Problems. J. Comput. Syst. Sci. 47(3): 549-595 (1993)

Dana Ron, Ronitt Rubinfeld: Learning Fallible Finite State Automata. COLT 1993: 218-227

Yoav Freund, Michael J. Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie: Efficient learning of typical finite automata from random walks. STOC 1993: 315-324

Ronitt Rubinfeld: Batch Checking with Applications to Linear Functions. Inf. Process. Lett. 42(2): 77-80 (1992)

Sandy Irani, Moni Naor, Ronitt Rubinfeld: On the Time and Space Complexity of Computation Using Write-Once Memory Or Is Pen Really Much Worse Than Pencil? Mathematical Systems Theory 25(2): 141-159 (1992)

Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan: Reconstructing Algebraic Functions from Mixed Data. FOCS 1992: 503-512

Ronitt Rubinfeld, Madhu Sudan: Self-Testing Polynomial Functions Efficiently and Over Rational Domains. SODA 1992: 23-32

Sandy Irani, Ronitt Rubinfeld: A Competitive 2-Server Algorithm. Inf. Process. Lett. 39(2): 85-91 (1991)

Joe Kilian, Ronitt Rubinfeld: Interactive Proofs with Space Bounded Provers. CRYPTO 1991: 225-231

Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson: Self-Testing/Correcting for Polynomials and for Approximate Functions. STOC 1991: 32-42

Ronitt Rubinfeld: The Cover Time of a Regular Expander is O(n log n). Inf. Process. Lett. 35(1): 49-51 (1990)

Manuel Blum, Michael Luby, Ronitt Rubinfeld: Self-Testing/Correcting with Applications to Numerical Problems. STOC 1990: 73-83

Nancy M. Amato, Manuel Blum, Sandy Irani, Ronitt Rubinfeld: Reversing Trains: A Turn of the Century Sorting Problem. J. Algorithms 10(3): 413-428 (1989)