Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Ronitt Rubinfeld
2010 – today
- 2013
[j38]Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam Smith: Sublinear Algorithms for Approximating String Compressibility. Algorithmica 65(3): 685-709 (2013)- [j37]Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: Testing Closeness of Discrete Distributions. J. ACM 60(1): 4 (2013)
- [j36]Ronitt Rubinfeld, Ning Xie: Robust characterizations of k-wise independence over product spaces and related testing results. Random Struct. Algorithms 43(3): 265-312 (2013)
- [j35]Reut Levi, Dana Ron, Ronitt Rubinfeld: Testing Properties of Collections of Distributions. Theory of Computing 9: 295-347 (2013)
- [c59]Andrea Campagna, Alan Guo, Ronitt Rubinfeld: Local Reconstructors and Tolerant Testers for Connectivity and Diameter. APPROX-RANDOM 2013: 411-424
- [c58]Akashnil Dutta, Reut Levi, Dana Ron, Ronitt Rubinfeld: A Simple Online Competitive Adaptation of Lempel-Ziv Compression with Efficient Random Access Support. DCC 2013: 113-122
- [i19]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)
- 2012
- [j34]
- [j33]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)
- [c57]
- [c56]Piotr Indyk, Reut Levi, Ronitt Rubinfeld: Approximating and testing k-histogram distributions in sub-linear time. PODS 2012: 15-22
- [c55]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
- [c54]Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie: Space-efficient local computation algorithms. SODA 2012: 1132-1139
- [i18]Andrea Campagna, Alan Guo, Ronitt Rubinfeld: Local reconstructors and tolerant testers for connectivity and diameter. CoRR abs/1208.2956 (2012)
- [i17]Reut Levi, Dana Ron, Ronitt Rubinfeld: Testing Similar Means. Electronic Colloquium on Computational Complexity (ECCC) 19: 55 (2012)
- 2011
- [j32]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)
- [j31]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)
- [j30]Ronitt Rubinfeld, Asaf Shapira: Sublinear Time Algorithms. SIAM J. Discrete Math. 25(4): 1562-1588 (2011)
- [c53]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
- [c52]
- [c51]Ronitt Rubinfeld, Gil Tamir, Shai Vardi, Ning Xie: Fast Local Computation Algorithms. ICS 2011: 223-238
- [c50]Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant: Testing monotonicity of distributions over general partial orders. ICS 2011: 239-252
- [i16]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)
- [i15]Ronitt Rubinfeld, Gil Tamir, Shai Vardi, Ning Xie: Fast Local Computation Algorithms. CoRR abs/1104.1377 (2011)
- [i14]Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie: Space-efficient Local Computation Algorithms. CoRR abs/1109.6178 (2011)
- [i13]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)
- [i12]Ronitt Rubinfeld, Asaf Shapira: Sublinear Time Algorithms. Electronic Colloquium on Computational Complexity (ECCC) 18: 13 (2011)
- 2010
- [j29]Elena Grigorescu, Kyomin Jung, Ronitt Rubinfeld: A local decision test for sparse polynomials. Inf. Process. Lett. 110(20): 898-901 (2010)
- [j28]Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio: Testing Halfspaces. SIAM J. Comput. 39(5): 2004-2047 (2010)
- [c49]Ronitt Rubinfeld, Ning Xie: Testing Non-uniform k-Wise Independent Distributions over Product Spaces. ICALP (1) 2010: 565-581
- [c48]Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld: Sublinear Algorithms in the External Memory Model. Property Testing 2010: 240-243
- [c47]Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio: Testing (Subclasses of) Halfspaces. Property Testing 2010: 334-340
- [c46]Krzysztof Onak, Ronitt Rubinfeld: Dynamic Approximate Vertex Cover and Maximum Matching. Property Testing 2010: 341-345
- [c45]Krzysztof Onak, Ronitt Rubinfeld: Maintaining a large matching and a small vertex cover. STOC 2010: 457-464
- [c44]Rubi Boim, Haim Kaplan, Tova Milo, Ronitt Rubinfeld: Improved Recommendations via (More) Collaboration. WebDB 2010
- [i11]Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: Testing Closeness of Discrete Distributions. CoRR abs/1009.5397 (2010)
- [i10]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)
- [i9]Reut Levi, Dana Ron, Ronitt Rubinfeld: Testing Properties of Collections of Distributions. Electronic Colloquium on Computational Complexity (ECCC) 17: 157 (2010)
2000 – 2009
- 2009
- [j27]Ronitt Rubinfeld, Rocco A. Servedio: Testing monotone high-dimensional distributions. Random Struct. Algorithms 34(1): 24-44 (2009)
- [c43]Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio: Testing ±1-weight halfspace. APPROX-RANDOM 2009: 646-657
- [c42]Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld: External Sampling. ICALP (1) 2009: 83-94
- [c41]Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio: Testing halfspaces. SODA 2009: 256-264
- [i8]Khanh Do Ba, Huy L. Nguyen, Huy N. Nguyen, Ronitt Rubinfeld: Sublinear Time Algorithms for Earth Mover's Distance. CoRR abs/0904.0292 (2009)
- 2008
- [j26]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)
- [e2]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
- [r1]
- 2007
- [c40]Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam Smith: Sublinear Algorithms for Approximating String Compressibility. APPROX-RANDOM 2007: 609-623
- [c39]Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan: Testing for Concise Representations. FOCS 2007: 549-558
- [c38]Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie: Testing k-wise and almost k-wise independence. STOC 2007: 496-505
- [i7]Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam Smith: Sublinear Algorithms for Approximating String Compressibility. CoRR abs/0706.1084 (2007)
- [i6]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)
- [i5]Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio: Testing Halfspaces. Electronic Colloquium on Computational Complexity (ECCC) 14(128) (2007)
- 2006
- [j25]Michal Parnas, Dana Ron, Ronitt Rubinfeld: Tolerant property testing and distance approximation. J. Comput. Syst. Sci. 72(6): 1012-1042 (2006)
- [e1]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
- 2005
- [j24]Tugkan Batu, Ronitt Rubinfeld, Patrick White: Fast approximate PCPs for multidimensional bin-packing problems. Inf. Comput. 196(1): 42-56 (2005)
- [j23]Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan: Approximating the Minimum Spanning Tree Weight in Sublinear Time. SIAM J. Comput. 34(6): 1370-1379 (2005)
- [j22]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)
- [j21]Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld: The Complexity of Approximating the Entropy. SIAM J. Comput. 35(1): 132-150 (2005)
- [c37]Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler: 05291 Abstracts Collection -- Sublinear Algorithms. Sublinear Algorithms 2005
- [c36]Ronitt Rubinfeld, Rocco A. Servedio: Testing monotone high-dimensional distributions. STOC 2005: 147-156
- [i4]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)
- 2004
- [j20]Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: Fast approximate probabilistically checkable proofs. Inf. Comput. 189(2): 135-159 (2004)
- [c35]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
- [c34]Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, Ayellet Tal: The Bloomier filter: an efficient data structure for static support lookup tables. SODA 2004: 30-39
- [c33]Tugkan Batu, Ravi Kumar, Ronitt Rubinfeld: Sublinear algorithms for testing monotone and unimodal distributions. STOC 2004: 381-390
- [i3]Michal Parnas, Dana Ron, Ronitt Rubinfeld: Tolerant Property Testing and Distance Approximation. Electronic Colloquium on Computational Complexity (ECCC)(010) (2004)
- [i2]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)
- 2003
- [j19]Michal Parnas, Dana Ron, Ronitt Rubinfeld: Testing membership in parenthesis languages. Random Struct. Algorithms 22(1): 98-138 (2003)
- [j18]Michal Parnas, Dana Ron, Ronitt Rubinfeld: On Testing Convexity and Submodularity. SIAM J. Comput. 32(5): 1158-1184 (2003)
- [j17]Ravi Kumar, Ronitt Rubinfeld: Algorithms column: sublinear time algorithms. SIGACT News 34(4): 57-67 (2003)
- [c32]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
- [c31]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
- 2002
- [c30]Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld: The Complexity of Approximating the Entropy. IEEE Conference on Computational Complexity 2002: 17
- [c29]Michal Parnas, Dana Ron, Ronitt Rubinfeld: On Testing Convexity and Submodularity. RANDOM 2002: 11-25
- [c28]Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky: Monotonicity testing over general poset domains. STOC 2002: 474-483
- [c27]Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld: The complexity of approximating entropy. STOC 2002: 678-687
- 2001
- [j16]Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: Checking Approximate Computations of Polynomials and Functional Equations. SIAM J. Comput. 31(2): 550-576 (2001)
- [c26]Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, Patrick White: Testing Random Variables for Independence and Identity. FOCS 2001: 442-451
- [c25]Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan: Approximating the Minimum Spanning Tree Weight in Sublinear Time. ICALP 2001: 190-200
- [c24]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
- [c23]Michal Parnas, Dana Ron, Ronitt Rubinfeld: Testing Parenthesis Languages. RANDOM-APPROX 2001: 261-272
- 2000
- [j15]Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan: Spot-Checkers. J. Comput. Syst. Sci. 60(3): 717-751 (2000)
- [j14]Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan: Learning Polynomials with Queries: The Highly Noisy Case. SIAM J. Discrete Math. 13(4): 535-570 (2000)
- [c22]Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: Testing that distributions are close. FOCS 2000: 259-269
- [c21]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
1990 – 1999
- 1999
- [j13]Ronitt Rubinfeld: On the Robustness of Functional Equations. SIAM J. Comput. 28(6): 1972-1997 (1999)
- [c20]Tugkan Batu, Ronitt Rubinfeld, Patrick White: Fast Approximate PCPs for Multidimensional Bin-Packing Problems. RANDOM-APPROX 1999: 245-256
- [c19]
- 1998
- [j12]Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan: Reconstructing Algebraic Functions from Mixed Data. SIAM J. Comput. 28(2): 487-510 (1998)
- [c18]Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan: Spot-Checkers. STOC 1998: 259-268
- [i1]Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan: Learning Polynomials with Queries - The Highly Noisy Case. Electronic Colloquium on Computational Complexity (ECCC) 5(60) (1998)
- 1997
- [j11]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)
- [j10]Dana Ron, Ronitt Rubinfeld: Exactly Learning Automata of Small Cover Time. Machine Learning 27(1): 69-96 (1997)
- [c17]Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: Learning Distributions from Random Walks. COLT 1997: 243-249
- 1996
- [j9]Ronitt Rubinfeld: Designing Checkers for Programs that Run in Parallel. Algorithmica 15(4): 287-301 (1996)
- [j8]Ronitt Rubinfeld, Madhu Sudan: Robust Characterizations of Polynomials with Applications to Program Testing. SIAM J. Comput. 25(2): 252-271 (1996)
- [c16]
- [c15]Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: Approximate Checking of Polynomials and Functional Equations (extended abstract). FOCS 1996: 592-601
- 1995
- [j7]Dana Ron, Ronitt Rubinfeld: Learning Fallible Deterministic Finite Automata. Machine Learning 18(2-3): 149-185 (1995)
- [c14]Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: On Learning Bounded-Width Branching Programs. COLT 1995: 361-368
- [c13]
- [c12]Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan: Learning Polynomials with Queries: The Highly Noisy Case. FOCS 1995: 294-303
- [c11]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
- 1994
- [c10]Ronitt Rubinfeld, Richard Zippel: A new modular interpolation algorithm for factoring multivariate polynominals. ANTS 1994: 93-107
- [c9]
- [c8]Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie: On the learnability of discrete distributions. STOC 1994: 273-282
- 1993
- [j6]Manuel Blum, Michael Luby, Ronitt Rubinfeld: Self-Testing/Correcting with Applications to Numerical Problems. J. Comput. Syst. Sci. 47(3): 549-595 (1993)
- [c7]
- [c6]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
- 1992
- [j5]Ronitt Rubinfeld: Batch Checking with Applications to Linear Functions. Inf. Process. Lett. 42(2): 77-80 (1992)
- [j4]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)
- [c5]Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan: Reconstructing Algebraic Functions from Mixed Data. FOCS 1992: 503-512
- [c4]Ronitt Rubinfeld, Madhu Sudan: Self-Testing Polynomial Functions Efficiently and Over Rational Domains. SODA 1992: 23-32
- 1991
- [j3]Sandy Irani, Ronitt Rubinfeld: A Competitive 2-Server Algorithm. Inf. Process. Lett. 39(2): 85-91 (1991)
- [c3]
- [c2]Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson: Self-Testing/Correcting for Polynomials and for Approximate Functions. STOC 1991: 32-42
- 1990
- [j2]Ronitt Rubinfeld: The Cover Time of a Regular Expander is O(n log n). Inf. Process. Lett. 35(1): 49-51 (1990)
- [c1]Manuel Blum, Michael Luby, Ronitt Rubinfeld: Self-Testing/Correcting with Applications to Numerical Problems. STOC 1990: 73-83
1980 – 1989
- 1989
- [j1]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)
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-10-02 11:20 CEST by the dblp team