Ronitt Rubinfeld

	2009
81		Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio: Testing ±1-weight halfspace. APPROX-RANDOM 2009: 646-657
80		Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld: External Sampling. ICALP (1) 2009: 83-94
79		Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio: Testing halfspaces. SODA 2009: 256-264
78		Khanh Do Ba, Huy L. Nguyen, Huy N. Nguyen, Ronitt Rubinfeld: Sublinear Time Algorithms for Earth Mover's Distance CoRR abs/0904.0292: (2009)
77		Ronitt Rubinfeld, Rocco A. Servedio: Testing monotone high-dimensional distributions. Random Struct. Algorithms 34(1): 24-44 (2009)
	2008
76		Ashish Goel, Klaus Jansen, José D. P. Rolim, Ronitt Rubinfeld: 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 Springer 2008
75		Ronitt Rubinfeld: Linearity Testing/Testing Hadamard Codes. Encyclopedia of Algorithms 2008
74		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)
	2007
73		Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam Smith: Sublinear Algorithms for Approximating String Compressibility. APPROX-RANDOM 2007: 609-623
72		Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan: Testing for Concise Representations. FOCS 2007: 549-558
71		Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie: Testing k-wise and almost k-wise independence. STOC 2007: 496-505
70		Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam Smith: Sublinear Algorithms for Approximating String Compressibility CoRR abs/0706.1084: (2007)
69		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)
68		Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio: Testing Halfspaces. Electronic Colloquium on Computational Complexity (ECCC) 14(128): (2007)
	2006
67		Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler: Sublinear Algorithms, 17.07. - 22.07.2005 Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany 2006
66		Michal Parnas, Dana Ron, Ronitt Rubinfeld: Tolerant property testing and distance approximation. J. Comput. Syst. Sci. 72(6): 1012-1042 (2006)
	2005
65		Ronitt Rubinfeld, Rocco A. Servedio: Testing monotone high-dimensional distributions. STOC 2005: 147-156
64		Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler: 05291 Abstracts Collection -- Sublinear Algorithms. Sublinear Algorithms 2005
63		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)
62		Tugkan Batu, Ronitt Rubinfeld, Patrick White: Fast approximate PCPs for multidimensional bin-packing problems. Inf. Comput. 196(1): 42-56 (2005)
61		Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan: Approximating the Minimum Spanning Tree Weight in Sublinear Time. SIAM J. Comput. 34(6): 1370-1379 (2005)
60		Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld: The Complexity of Approximating the Entropy. SIAM J. Comput. 35(1): 132-150 (2005)
59		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)
	2004
58		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
57		Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, Ayellet Tal: The Bloomier filter: an efficient data structure for static support lookup tables. SODA 2004: 30-39
56		Tugkan Batu, Ravi Kumar, Ronitt Rubinfeld: Sublinear algorithms for testing monotone and unimodal distributions. STOC 2004: 381-390
55		Michal Parnas, Dana Ron, Ronitt Rubinfeld: Tolerant Property Testing and Distance Approximation Electronic Colloquium on Computational Complexity (ECCC)(010): (2004)
54		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)
53		Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: Fast approximate probabilistically checkable proofs. Inf. Comput. 189(2): 135-159 (2004)
	2003
52		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
51		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
50		Michal Parnas, Dana Ron, Ronitt Rubinfeld: Testing membership in parenthesis languages. Random Struct. Algorithms 22(1): 98-138 (2003)
49		Michal Parnas, Dana Ron, Ronitt Rubinfeld: On Testing Convexity and Submodularity. SIAM J. Comput. 32(5): 1158-1184 (2003)
48		Ravi Kumar, Ronitt Rubinfeld: Algorithms column: sublinear time algorithms. SIGACT News 34(4): 57-67 (2003)
	2002
47		Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld: The Complexity of Approximating the Entropy. IEEE Conference on Computational Complexity 2002: 17
46		Michal Parnas, Dana Ron, Ronitt Rubinfeld: On Testing Convexity and Submodularity. RANDOM 2002: 11-25
45		Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky: Monotonicity testing over general poset domains. STOC 2002: 474-483
44		Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld: The complexity of approximating entropy. STOC 2002: 678-687
	2001
43		Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, Patrick White: Testing Random Variables for Independence and Identity. FOCS 2001: 442-451
42		Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan: Approximating the Minimum Spanning Tree Weight in Sublinear Time. ICALP 2001: 190-200
41		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
40		Michal Parnas, Dana Ron, Ronitt Rubinfeld: Testing Parenthesis Languages. RANDOM-APPROX 2001: 261-272
39		Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: Checking Approximate Computations of Polynomials and Functional Equations. SIAM J. Comput. 31(2): 550-576 (2001)
	2000
38		Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: Testing that distributions are close. FOCS 2000: 259-269
37		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
36		Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan: Spot-Checkers. J. Comput. Syst. Sci. 60(3): 717-751 (2000)
35		Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan: Learning Polynomials with Queries: The Highly Noisy Case. SIAM J. Discrete Math. 13(4): 535-570 (2000)
	1999
34		Tugkan Batu, Ronitt Rubinfeld, Patrick White: Fast Approximate PCPs for Multidimensional Bin-Packing Problems. RANDOM-APPROX 1999: 245-256
33		Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: Fast Approximate PCPs. STOC 1999: 41-50
32		Ronitt Rubinfeld: On the Robustness of Functional Equations. SIAM J. Comput. 28(6): 1972-1997 (1999)
	1998
31		Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan: Spot-Checkers. STOC 1998: 259-268
30		Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan: Learning Polynomials with Queries - The Highly Noisy Case. Electronic Colloquium on Computational Complexity (ECCC) 5(60): (1998)
29		Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan: Reconstructing Algebraic Functions from Mixed Data. SIAM J. Comput. 28(2): 487-510 (1998)
	1997
28		Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: Learning Distributions from Random Walks. COLT 1997: 243-249
27		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)
26		Dana Ron, Ronitt Rubinfeld: Exactly Learning Automata of Small Cover Time. Machine Learning 27(1): 69-96 (1997)
	1996
25		Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: Approximate Checking of Polynomials and Functional Equations (extended abstract). FOCS 1996: 592-601
24		Jon M. Kleinberg, Ronitt Rubinfeld: Short Paths in Expander Graphs. FOCS 1996: 86-95
23		Ronitt Rubinfeld: Designing Checkers for Programs that Run in Parallel. Algorithmica 15(4): 287-301 (1996)
22		Ronitt Rubinfeld, Madhu Sudan: Robust Characterizations of Polynomials with Applications to Program Testing. SIAM J. Comput. 25(2): 252-271 (1996)
	1995
21		Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: On Learning Bounded-Width Branching Programs. COLT 1995: 361-368
20		Dana Ron, Ronitt Rubinfeld: Exactly Learning Automata with Small Cover Time. COLT 1995: 427-436
19		Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan: Learning Polynomials with Queries: The Highly Noisy Case. FOCS 1995: 294-303
18		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
17		Dana Ron, Ronitt Rubinfeld: Learning Fallible Deterministic Finite Automata. Machine Learning 18(2-3): 149-185 (1995)
	1994
16		Ronitt Rubinfeld, Richard Zippel: A new modular interpolation algorithm for factoring multivariate polynominals. ANTS 1994: 93-107
15		Ronitt Rubinfeld: On the robustness of functional equations FOCS 1994: 288-299
14		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
13		Dana Ron, Ronitt Rubinfeld: Learning Fallible Finite State Automata. COLT 1993: 218-227
12		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
11		Manuel Blum, Michael Luby, Ronitt Rubinfeld: Self-Testing/Correcting with Applications to Numerical Problems. J. Comput. Syst. Sci. 47(3): 549-595 (1993)
	1992
10		Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan: Reconstructing Algebraic Functions from Mixed Data FOCS 1992: 503-512
9		Ronitt Rubinfeld, Madhu Sudan: Self-Testing Polynomial Functions Efficiently and Over Rational Domains. SODA 1992: 23-32
8		Ronitt Rubinfeld: Batch Checking with Applications to Linear Functions. Inf. Process. Lett. 42(2): 77-80 (1992)
7		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)
	1991
6		Joe Kilian, Ronitt Rubinfeld: Interactive Proofs with Space Bounded Provers. CRYPTO 1991: 225-231
5		Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson: Self-Testing/Correcting for Polynomials and for Approximate Functions STOC 1991: 32-42
4		Sandy Irani, Ronitt Rubinfeld: A Competitive 2-Server Algorithm. Inf. Process. Lett. 39(2): 85-91 (1991)
	1990
3		Manuel Blum, Michael Luby, Ronitt Rubinfeld: Self-Testing/Correcting with Applications to Numerical Problems STOC 1990: 73-83
2		Ronitt Rubinfeld: The Cover Time of a Regular Expander is O(n log n). Inf. Process. Lett. 35(1): 49-51 (1990)
	1989
1		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

1	Noga Alon	[71]
2	Nancy M. Amato	[1]
3	Alexandr Andoni	[71] [80]
4	Sigal Ar	[10] [29]
5	Khanh Do Ba	[78]
6	Tugkan Batu	[34] [38] [43] [44] [47] [51] [56] [60] [62]
7	Michael Ben-Or	[54] [58] [74]
8	Manuel Blum	[1] [3] [11]
9	Ran Canetti	[41]
10	Bernard Chazelle	[42] [57] [61]
11	Don Coppersmith	[54] [58] [74]
12	Artur Czumaj	[52] [59] [64] [67]
13	Sanjoy Dasgupta	[44] [47] [60]
14	Ilias Diakonikolas	[69] [72]
15	Funda Ergün	[21] [25] [28] [31] [33] [36] [39] [51] [52] [53] [59]
16	Ronald Fagin	[37]
17	Eldar Fischer	[43] [45]
18	Lance Fortnow	[38] [43] [52] [59]
19	Yoav Freund	[12] [18] [27]
20	Peter Gemmell	[5]
21	Ashish Goel	[76]
22	Oded Goldreich	[19] [30] [35]
23	Piotr Indyk	[80]
24	Sandy Irani	[1] [4] [7]
25	Yuval Ishai	[41]
26	Klaus Jansen	[76]
27	Sampath Kannan	[31] [36]
28	Anna R. Karlin	[37]
29	Tali Kaufman	[71]
30	Michael J. Kearns	[12] [14] [18] [27]
31	Joe Kilian	[6] [51] [57]
32	Jon M. Kleinberg	[24] [37]
33	Ravi Kumar (S. Ravi Kumar)	[21] [25] [28] [31] [33] [36] [39] [41] [43] [44] [47] [48] [53] [56] [60]
34	Homin K. Lee	[69] [72]
35	Eric Lehman	[45]
36	Richard J. Lipton	[5] [10] [29]
37	Michael Luby	[3] [11] [54] [58] [74]
38	Avner Magen	[51] [52] [59]
39	Yishay Mansour	[14] [18]
40	Kevin Matulef	[68] [69] [71] [72] [79] [81]
41	S. Muthukrishnan (S. Muthu Muthukrishnan)	[64] [67]
42	Moni Naor	[7]
43	Ilan Newman	[45] [52] [59]
44	Huy L. Nguyen	[78]
45	Huy N. Nguyen	[78]
46	Ryan O'Donnell	[68] [79] [81]
47	Krzysztof Onak	[69] [72] [80]
48	Michal Parnas	[40] [46] [49] [50] [55] [66]
49	Prabhakar Raghavan	[37]
50	Sridhar Rajagopalan	[37]
51	Sofya Raskhodnikova	[45] [51] [63] [70] [73]
52	Michael K. Reiter	[41]
53	José D. P. Rolim	[76]
54	Dana Ron	[12] [13] [14] [17] [18] [20] [26] [27] [40] [46] [49] [50] [55] [63] [66] [70] [73]
55	Rahul Sami	[51]
56	Alex Samorodnitsky	[45]
57	Robert E. Schapire	[12] [14] [18] [27]
58	Linda Sellie	[12] [14] [27]
59	Rocco A. Servedio	[65] [68] [69] [72] [77] [79] [81]
60	Amir Shpilka	[63]
61	Adam Smith	[63] [70] [73]
62	Warren D. Smith	[38]
63	Christian Sohler	[52] [59] [64] [67]
64	Madhu Sudan	[5] [9] [10] [19] [22] [29] [30] [35] [37]
65	Ayellet Tal	[57]
66	Andrew Tomkins	[37]
67	Luca Trevisan	[42] [61]
68	Mahesh Viswanathan	[31] [36]
69	Andrew Wan	[69] [72]
70	Patrick White	[34] [38] [43] [62]
71	Avi Wigderson	[5]
72	Rebecca N. Wright	[41]
73	Ning Xie	[71]
74	Richard Zippel	[16]

Colors in the list of coauthors