Ronitt Rubinfeld - Publications

Affiliations: 
Cornell University, Ithaca, NY, United States 
Area:
Computer Science, Statistics

70 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2016 Canonne CL, Diakonikolas I, Gouleakis T, Rubinfeld R. Testing shape restrictions of discrete distributions Leibniz International Proceedings in Informatics, Lipics. 47. DOI: 10.4230/LIPIcs.STACS.2016.25  0.64
2016 Canonne CL, Gouleakis T, Rubinfeld R. Sampling correctors Itcs 2016 - Proceedings of the 2016 Acm Conference On Innovations in Theoretical Computer Science. 93-102. DOI: 10.1145/2840728.2840729  0.64
2016 Levi R, Rubinfeld R, Yodpinyanee A. Local Computation Algorithms for Graphs of Non-constant Degrees Algorithmica. 1-24. DOI: 10.1007/s00453-016-0126-y  0.64
2016 Levi R, Moshkovitz G, Ron D, Rubinfeld R, Shapira A. Constructing near spanning trees with few local inspections Random Structures and Algorithms. DOI: 10.1002/rsa.20652  0.64
2015 Levi R, Rubinfeld R, Yodpinyanee A. Brief announcement: Local computation algorithms for graphs of non-constant degrees Annual Acm Symposium On Parallelism in Algorithms and Architectures. 2015: 59-61. DOI: 10.1145/2755573.2755615  0.64
2015 Devadas S, Rubinfeld R. A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness Theory of Computing Systems. DOI: 10.1007/s00224-015-9639-z  0.64
2015 Rubinfeld R. Foreword Proceedings of the Annual Acm Symposium On Theory of Computing. 14: iii.  0.64
2015 Parnas M, Ron D, Rubinfeld R. Testing parenthesis languages Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2129: 261-272.  0.64
2015 Kim A, Blais E, Parameswaran A, Indyk P, Madden S, Rubinfeld R. Rapid Sampling for Visualizations with Ordering Guarantees Proceedings of the Vldb Endowment. 8: 521-532.  0.64
2014 Levi R, Ron D, Rubinfeld R. Local algorithms for sparse spanning graphs Leibniz International Proceedings in Informatics, Lipics. 28: 826-842. DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.826  0.64
2014 Levi R, Ron D, Rubinfeld R. Testing similar means Siam Journal On Discrete Mathematics. 28: 1699-1724. DOI: 10.1137/120903737  0.64
2014 Canonne C, Rubinfeld R. Testing probability distributions underlying aggregated data Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8572: 283-295. DOI: 10.1007/978-3-662-43948-7_24  0.64
2013 Batu T, Fortnow L, Rubinfeld R, Smith WD, White P. Testing closeness of discrete distributions Journal of the Acm. 60. DOI: 10.1145/2432622.2432626  0.64
2013 Dutta A, Levi R, Ron D, Rubinfeld R. A simple online competitive adaptation of Lempel-Ziv compression with efficient random access support Data Compression Conference Proceedings. 113-122. DOI: 10.1109/DCC.2013.19  0.64
2013 Raskhodnikova S, Ron D, Rubinfeld R, Smith A. Sublinear algorithms for approximating string compressibility Algorithmica. 65: 685-709. DOI: 10.1007/s00453-012-9618-6  0.64
2013 Campagna A, Guo A, Rubinfeld R. Local reconstructors and tolerant testers for connectivity and diameter Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8096: 411-424. DOI: 10.1007/978-3-642-40328-6_29  0.64
2013 Rubinfeld R, Xie N. Robust characterizations of k-wise independence over product spaces and related testing results Random Structures and Algorithms. 43: 265-312. DOI: 10.1002/rsa.20423  0.64
2012 Indyk P, Levi R, Rubinfeld R. Approximating and testing k-histogram distributions in sub-linear time Proceedings of the Acm Sigact-Sigmod-Sigart Symposium On Principles of Database Systems. 15-21. DOI: 10.1145/2213556.2213561  0.64
2012 Onak K, Ron D, Rosen M, Rubinfeld R. A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 1123-1131.  0.64
2012 Alon N, Rubinfeld R, Vardi S, Xie N. Space-efficient local computation algorithms Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 1132-1139.  0.64
2011 Ba KD, Nguyen HL, Nguyen HN, Rubinfeld R. Sublinear Time Algorithms for Earth Mover's Distance Theory of Computing Systems. 48: 428-442. DOI: 10.1007/s00224-010-9265-8  0.64
2010 Boim R, Kaplan H, Milo T, Rubinfeld R. Improved recommendations via (More) collaboration Proceedings of the Acm Sigmod International Conference On Management of Data. DOI: 10.1145/1859127.1859143  0.64
2010 Onak K, Rubinfeld R. Maintaining a large matching and a small vertex cover Proceedings of the Annual Acm Symposium On Theory of Computing. 457-464. DOI: 10.1145/1806689.1806753  0.64
2010 Grigorescu E, Jung K, Rubinfeld R. A local decision test for sparse polynomials Information Processing Letters. 110: 898-901. DOI: 10.1016/j.ipl.2010.07.012  0.64
2010 Onak K, Rubinfeld R. Dynamic approximate vertex cover and maximum matching Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6390: 341-345. DOI: 10.1007/978-3-642-16367-8_28  0.64
2010 Matulef K, O'Donnell R, Rubinfeld R, Servedio R. Testing (subclasses of) halfspaces Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6390: 334-340. DOI: 10.1007/978-3-642-16367-8_27  0.64
2010 Andoni A, Indyk P, Onak K, Rubinfeld R. Sublinear algorithms in the external memory model Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6390: 240-243. DOI: 10.1007/978-3-642-16367-8_15  0.64
2010 Rubinfeld R, Xie N. Testing non-uniform k-wise independent distributions over product spaces Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6198: 565-581. DOI: 10.1007/978-3-642-14165-2_48  0.64
2009 Matulef K, O'Donnell R, Rubinfeld R, Servedio RA. Testing ±1-weight halfspace Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5687: 646-657. DOI: 10.1007/978-3-642-03685-9_48  0.64
2009 Andoni A, Indyk P, Onak K, Rubinfeld R. External sampling Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5555: 83-94. DOI: 10.1007/978-3-642-02927-1_9  0.64
2009 Rubinfeld R, Servedio RA. Testing monotone high-dimensional distributions Random Structures and Algorithms. 34: 24-44. DOI: 10.1002/rsa.20247  0.64
2009 Matulef K, O'Donnell R, Rubinfeld R, Servedio RA. Testing halfspaces Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 256-264.  0.64
2007 Alon N, Andoni A, Kaufman T, Matulef K, Rubinfeld R, Xie N. Testing k-wise and almost k-wise independence Proceedings of the Annual Acm Symposium On Theory of Computing. 496-505. DOI: 10.1145/1250790.1250863  0.64
2007 Diakonikolas I, Lee HK, Matulef K, Onak K, Rubinfeld R, Servedio RA, Wan A. Testing for concise representations Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 549-558. DOI: 10.1109/FOCS.2007.4389524  0.64
2006 Czumaj A, Ergün F, Fortnow L, Magen A, Newman I, Rubinfeld R, Sohler C. Approximating the weight of the Euclidean minimum spanning tree in sublinear time Siam Journal On Computing. 35: 91-109. DOI: 10.1137/S0097539703435297  0.64
2006 Batu T, Dasgupta S, Kumar R, Rubinfeld R. The complexity of approximating the entropy Siam Journal On Computing. 35: 132-150. DOI: 10.1137/S0097539702403645  0.64
2006 Rubinfeld R. Sublinear time algorithms International Congress of Mathematicians, Icm 2006. 3: 1095-1110. DOI: 10.1137/100791075  0.64
2006 Parnas M, Ron D, Rubinfeld R. Tolerant property testing and distance approximation Journal of Computer and System Sciences. 72: 1012-1042. DOI: 10.1016/j.jcss.2006.03.002  0.64
2006 Kenthapadi K, Panigrahy R, Achlioptas D, Azar Y, Brightwell G, Cheriyan J, Gustedt J, Hell P, Iacono J, Kobourov S, Kolliopoulos S, Ladner R, Lewenstein M, Mahdian M, Plaxton G, ... ... Rubinfeld R, et al. Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms: Preface Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms 0.64
2005 Chazelle B, Rubinfeld R, Trevisan L. Approximating the minimum spanning tree weight in sublinear time Siam Journal On Computing. 34: 1370-1379. DOI: 10.1137/S0097539702403244  0.64
2005 Batu T, Rubinfeld R, White P. Fast approximate PCPs for multidimensional bin-packing problems Information and Computation. 196: 42-56. DOI: 10.1016/j.ic.2004.10.001  0.64
2004 Ergün F, Kumar R, Rubinfeld R. Fast approximate probabilistically checkable proofs Information and Computation. 189: 135-159. DOI: 10.1016/j.ic.2003.09.005  0.64
2004 Ben M, Coppersmith D, Luby M, Rubinfeld R. Non-Abelian homomorphism testing, and distributions close to their self-convolutions Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 3122: 273-285. DOI: 10.1002/rsa.20182  0.64
2004 Batu T, Kumar R, Rubinfeld R. Sublinear algorithms for testing monotone and unimodal distributions Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 381-390.  0.64
2004 Chazelle B, Kilian J, Rubinfeld R, Tal A. The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 15: 30-39.  0.64
2003 Parnas M, Ron D, Rubinfeld R. Testing Membership in Parenthesis Languages Random Structures and Algorithms. 22: 98-138. DOI: 10.1002/rsa.10067  0.64
2003 Batu T, Ergün F, Kilian J, Magen A, Raskhodnikova S, Rubinfeld R, Sami R. A sublinear algorithm for weakly approximating edit distance Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 316-324.  0.64
2003 Czumaj A, Ergün F, Fortnow L, Magen A, Newman I, Rubinfeld R, Sohler C. Sublinear-time approximation of Euclidean minimum spanning tree Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 813-822.  0.64
2002 Parnas M, Ron D, Rubinfeld R. On testing convexity and submodularity Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2483: 11-25. DOI: 10.1007/3-540-45726-7_2  0.64
2002 Batu T, Dasgupta S, Kumar R, Rubinfeld R. The complexity of approximating entropy Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 678-687.  0.64
2002 Fischer E, Lehman E, Newman I, Raskhodnikova S, Rubinfeld R, Samorodnitsky A. Monotonicity testing over general poset domains Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 474-483.  0.64
2001 Fagin R, Karlin AR, Kleinberg J, Raghavan P, Rajagopalan S, Rubinfeld R, Sudan M, Tomkins A. Random walks with "back buttons" Annals of Applied Probability. 11: 810-862. DOI: 10.1214/aoap/1015345350  0.64
2001 Ergün F, Kumar SR, Rubinfeld R. Checking approximate computations of polynomials and functional equations Siam Journal On Computing. 31: 550-576.  0.64
2001 Canetti R, Ishai Y, Kumar R, Reiter MK, Rubinfeld R, Wright RN. Selective private function evaluation with applications to private statistics Proceedings of the Annual Acm Symposium On Principles of Distributed Computing. 293-302.  0.64
2001 Batu T, Fischer E, Fortnow L, Kumar R, Rubinfeld R, White P. Testing random variables for independence and identity Annual Symposium On Foundations of Computer Science - Proceedings. 442-451.  0.64
2000 Ergün F, Kannan S, Kumar SR, Rubinfeld R, Viswanathan M. Spot-checkers Journal of Computer and System Sciences. 60: 717-751. DOI: 10.1006/jcss.1999.1692  0.64
2000 Goldreich O, Rubinfeld R, Sudan M. Learning polynomials with queries: The highly noisy case Siam Journal On Discrete Mathematics. 13: 535-570.  0.64
2000 Fagin R, Karlin AR, Kleinberg J, Raghavan P, Rajagopalan S, Rubinfeld R, Sudan M, Tomkins A. Random walks with `back buttons' Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 484-493.  0.64
1999 Rubinfeld R. On the robustness of functional equations Siam Journal On Computing. 28: 1972-1997.  0.64
1997 Ron D, Rubinfeld R. Exactly Learning Automata of Small Cover Time Machine Learning. 27: 69-96.  0.64
1997 Freund Y, Kearns M, Ron D, Rubinfeld R, Schapire RE, Sellie L. Efficient Learning of Typical Finite Automata from Random Walks Information and Computation. 138: 23-48.  0.64
1996 Rubinfeld R. Designing Checkers for Programs that Run in Parallel Algorithmica (New York). 15: 287-301.  0.64
1996 Rubinfeld R, Sudan M. Robust characterizations of polynomials with applications to program testing Siam Journal On Computing. 25: 252-271.  0.64
1995 Ron D, Rubinfeld R. Learning Fallible Deterministic Finite Automata Machine Learning. 18: 149-185. DOI: 10.1023/A:1022899313248  0.64
1993 Blum M, Luby M, Rubinfeld R. Self-testing/correcting with applications to numerical problems Journal of Computer and System Sciences. 47: 549-595. DOI: 10.1016/0022-0000(93)90044-W  0.64
1992 Rubinfeld R. Batch checking with applications to linear functions Information Processing Letters. 42: 77-80. DOI: 10.1016/0020-0190(92)90093-B  0.64
1992 Irani S, Naor M, Rubinfeld R. On the time and space complexity of computation using write-once memory or is pen really much worse than pencil? Mathematical Systems Theory. 25: 141-159. DOI: 10.1007/BF02835833  0.64
1991 Irani S, Rubinfeld R. A competitive 2-server algorithm Information Processing Letters. 39: 85-91. DOI: 10.1016/0020-0190(91)90160-J  0.64
1990 Rubinfeld R. The cover time of a regular expander is O(n log n) Information Processing Letters. 35: 49-51. DOI: 10.1016/0020-0190(90)90173-U  0.64
1989 Amato N, Blum M, Irani S, Rubinfeld R. Reversing trains: A turn of the century sorting problem Journal of Algorithms. 10: 413-428. DOI: 10.1016/0196-6774(89)90037-0  0.64
Show low-probability matches.