Ronitt Rubinfeld

2009
78	EE	Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio: Testing halfspaces. SODA 2009: 256-264
77	EE	Khanh Do Ba, Huy L. Nguyen, Huy N. Nguyen, Ronitt Rubinfeld: Sublinear Time Algorithms for Earth Mover's Distance CoRR abs/0904.0292: (2009)
76	EE	Ronitt Rubinfeld, Rocco A. Servedio: Testing monotone high-dimensional distributions. Random Struct. Algorithms 34(1): 24-44 (2009)
2008
75		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
74	EE	Ronitt Rubinfeld: Linearity Testing/Testing Hadamard Codes. Encyclopedia of Algorithms 2008
73	EE	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
72	EE	Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam Smith: Sublinear Algorithms for Approximating String Compressibility. APPROX-RANDOM 2007: 609-623
71	EE	Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan: Testing for Concise Representations. FOCS 2007: 549-558
70	EE	Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie: Testing k-wise and almost k-wise independence. STOC 2007: 496-505
69	EE	Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam Smith: Sublinear Algorithms for Approximating String Compressibility CoRR abs/0706.1084: (2007)
68	EE	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)
67	EE	Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio: Testing Halfspaces. Electronic Colloquium on Computational Complexity (ECCC) 14(128): (2007)
2006
66		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
65	EE	Michal Parnas, Dana Ron, Ronitt Rubinfeld: Tolerant property testing and distance approximation. J. Comput. Syst. Sci. 72(6): 1012-1042 (2006)
2005
64	EE	Ronitt Rubinfeld, Rocco A. Servedio: Testing monotone high-dimensional distributions. STOC 2005: 147-156
63	EE	Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler: 05291 Abstracts Collection -- Sublinear Algorithms. Sublinear Algorithms 2005
62	EE	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)
61	EE	Tugkan Batu, Ronitt Rubinfeld, Patrick White: Fast approximate PCPs for multidimensional bin-packing problems. Inf. Comput. 196(1): 42-56 (2005)
60	EE	Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan: Approximating the Minimum Spanning Tree Weight in Sublinear Time. SIAM J. Comput. 34(6): 1370-1379 (2005)
59	EE	Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld: The Complexity of Approximating the Entropy. SIAM J. Comput. 35(1): 132-150 (2005)
58	EE	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
57	EE	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
56	EE	Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, Ayellet Tal: The Bloomier filter: an efficient data structure for static support lookup tables. SODA 2004: 30-39
55	EE	Tugkan Batu, Ravi Kumar, Ronitt Rubinfeld: Sublinear algorithms for testing monotone and unimodal distributions. STOC 2004: 381-390
54	EE	Michal Parnas, Dana Ron, Ronitt Rubinfeld: Tolerant Property Testing and Distance Approximation Electronic Colloquium on Computational Complexity (ECCC)(010): (2004)
53	EE	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)
52	EE	Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: Fast approximate probabilistically checkable proofs. Inf. Comput. 189(2): 135-159 (2004)
2003
51	EE	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
50	EE	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
49	EE	Michal Parnas, Dana Ron, Ronitt Rubinfeld: Testing membership in parenthesis languages. Random Struct. Algorithms 22(1): 98-138 (2003)
48	EE	Michal Parnas, Dana Ron, Ronitt Rubinfeld: On Testing Convexity and Submodularity. SIAM J. Comput. 32(5): 1158-1184 (2003)
2002
47	EE	Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld: The Complexity of Approximating the Entropy. IEEE Conference on Computational Complexity 2002: 17
46	EE	Michal Parnas, Dana Ron, Ronitt Rubinfeld: On Testing Convexity and Submodularity. RANDOM 2002: 11-25
45	EE	Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky: Monotonicity testing over general poset domains. STOC 2002: 474-483
44	EE	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	EE	Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan: Approximating the Minimum Spanning Tree Weight in Sublinear Time. ICALP 2001: 190-200
41	EE	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	EE	Michal Parnas, Dana Ron, Ronitt Rubinfeld: Testing Parenthesis Languages. RANDOM-APPROX 2001: 261-272
39	EE	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	EE	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	EE	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	EE	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	EE	Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan: Spot-Checkers. STOC 1998: 259-268
30	EE	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	EE	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	EE	Funda Ergün, Ravi Kumar, Ronitt Rubinfeld: On Learning Bounded-Width Branching Programs. COLT 1995: 361-368
20	EE	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	EE	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	EE	Dana Ron, Ronitt Rubinfeld: Learning Fallible Finite State Automata. COLT 1993: 218-227
12	EE	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	EE	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	EE	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	[70]
2	Nancy M. Amato	[1]
3	Alexandr Andoni	[70]
4	Sigal Ar	[10] [29]
5	Khanh Do Ba	[77]
6	Tugkan Batu	[34] [38] [43] [44] [47] [50] [55] [59] [61]
7	Michael Ben-Or	[53] [57] [73]
8	Manuel Blum	[1] [3] [11]
9	Ran Canetti	[41]
10	Bernard Chazelle	[42] [56] [60]
11	Don Coppersmith	[53] [57] [73]
12	Artur Czumaj	[51] [58] [63] [66]
13	Sanjoy Dasgupta	[44] [47] [59]
14	Ilias Diakonikolas	[68] [71]
15	Funda Ergün	[21] [25] [28] [31] [33] [36] [39] [50] [51] [52] [58]
16	Ronald Fagin	[37]
17	Eldar Fischer	[43] [45]
18	Lance Fortnow	[38] [43] [51] [58]
19	Yoav Freund	[12] [18] [27]
20	Peter Gemmell	[5]
21	Ashish Goel	[75]
22	Oded Goldreich	[19] [30] [35]
23	Sandy Irani	[1] [4] [7]
24	Yuval Ishai	[41]
25	Klaus Jansen	[75]
26	Sampath Kannan	[31] [36]
27	Anna R. Karlin	[37]
28	Tali Kaufman	[70]
29	Michael J. Kearns	[12] [14] [18] [27]
30	Joe Kilian	[6] [50] [56]
31	Jon M. Kleinberg	[24] [37]
32	Ravi Kumar (S. Ravi Kumar)	[21] [25] [28] [31] [33] [36] [39] [41] [43] [44] [47] [52] [55] [59]
33	Homin K. Lee	[68] [71]
34	Eric Lehman	[45]
35	Richard J. Lipton	[5] [10] [29]
36	Michael Luby	[3] [11] [53] [57] [73]
37	Avner Magen	[50] [51] [58]
38	Yishay Mansour	[14] [18]
39	Kevin Matulef	[67] [68] [70] [71] [78]
40	S. Muthukrishnan (S. Muthu Muthukrishnan)	[63] [66]
41	Moni Naor	[7]
42	Ilan Newman	[45] [51] [58]
43	Huy L. Nguyen	[77]
44	Huy N. Nguyen	[77]
45	Ryan O'Donnell	[67] [78]
46	Krzysztof Onak	[68] [71]
47	Michal Parnas	[40] [46] [48] [49] [54] [65]
48	Prabhakar Raghavan	[37]
49	Sridhar Rajagopalan	[37]
50	Sofya Raskhodnikova	[45] [50] [62] [69] [72]
51	Michael K. Reiter	[41]
52	José D. P. Rolim	[75]
53	Dana Ron	[12] [13] [14] [17] [18] [20] [26] [27] [40] [46] [48] [49] [54] [62] [65] [69] [72]
54	Rahul Sami	[50]
55	Alex Samorodnitsky	[45]
56	Robert E. Schapire	[12] [14] [18] [27]
57	Linda Sellie	[12] [14] [27]
58	Rocco A. Servedio	[64] [67] [68] [71] [76] [78]
59	Amir Shpilka	[62]
60	Adam Smith	[62] [69] [72]
61	Warren D. Smith	[38]
62	Christian Sohler	[51] [58] [63] [66]
63	Madhu Sudan	[5] [9] [10] [19] [22] [29] [30] [35] [37]
64	Ayellet Tal	[56]
65	Andrew Tomkins	[37]
66	Luca Trevisan	[42] [60]
67	Mahesh Viswanathan	[31] [36]
68	Andrew Wan	[68] [71]
69	Patrick White	[34] [38] [43] [61]
70	Avi Wigderson	[5]
71	Rebecca N. Wright	[41]
72	Ning Xie	[70]
73	Richard Zippel	[16]

Colors in the list of coauthors