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) |