Self-testing/correcting with applications to numerical problems M Blum, M Luby, R Rubinfeld Proceedings of the twenty-second annual ACM symposium on Theory of computing …, 1990 | 1221 | 1990 |
Robust characterizations of polynomials with applications to program testing R Rubinfeld, M Sudan SIAM Journal on Computing 25 (2), 252-271, 1996 | 1018 | 1996 |
The bloomier filter: an efficient data structure for static support lookup tables B Chazelle, J Kilian, R Rubinfeld, A Tal Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete …, 2004 | 549 | 2004 |
On the learnability of discrete distributions M Kearns, Y Mansour, D Ron, R Rubinfeld, RE Schapire, L Sellie Proceedings of the twenty-sixth annual ACM symposium on Theory of computing …, 1994 | 353 | 1994 |
Testing that distributions are close T Batu, L Fortnow, R Rubinfeld, WD Smith, P White Proceedings 41st Annual Symposium on Foundations of Computer Science, 259-269, 2000 | 352 | 2000 |
Spot-checkers F Ergün, S Kannan, SR Kumar, R Rubinfeld, M Viswanathan Proceedings of the thirtieth annual ACM symposium on Theory of computing …, 1998 | 302 | 1998 |
Monotonicity testing over general poset domains E Fischer, E Lehman, I Newman, S Raskhodnikova, R Rubinfeld, ... Proceedings of the thiry-fourth annual ACM symposium on Theory of computing …, 2002 | 276 | 2002 |
Self-testing/correcting for polynomials and for approximate functions P Gemmell, R Lipton, R Rubinfeld, M Sudan, A Wigderson STOC 91, 32-42, 1991 | 272 | 1991 |
Testing random variables for independence and identity T Batu, E Fischer, L Fortnow, R Kumar, R Rubinfeld, P White Proceedings 42nd IEEE Symposium on Foundations of Computer Science, 442-451, 2001 | 259 | 2001 |
Tolerant property testing and distance approximation M Parnas, D Ron, R Rubinfeld Journal of Computer and System Sciences 72 (6), 1012-1042, 2006 | 235 | 2006 |
Learning polynomials with queries: The highly noisy case O Goldreich, R Rubinfeld, M Sudan SIAM Journal on Discrete Mathematics 13 (4), 535-570, 2000 | 213 | 2000 |
The complexity of approximating entropy T Batu, S Dasgupta, R Kumar, R Rubinfeld Proceedings of the thiry-fourth annual ACM symposium on Theory of computing …, 2002 | 208 | 2002 |
Sublinear time algorithms R Rubinfeld, A Shapira SIAM Journal on Discrete Mathematics 25 (4), 1562-1588, 2011 | 193 | 2011 |
Testing closeness of discrete distributions T Batu, L Fortnow, R Rubinfeld, WD Smith, P White Journal of the ACM (JACM) 60 (1), 1-25, 2013 | 192 | 2013 |
Fast local computation algorithms R Rubinfeld, G Tamir, S Vardi, N Xie arXiv preprint arXiv:1104.1377, 2011 | 162 | 2011 |
Approximating the minimum spanning tree weight in sublinear time B Chazelle, R Rubinfeld, L Trevisan SIAM Journal on computing 34 (6), 1370-1379, 2005 | 154 | 2005 |
Improved massively parallel computation algorithms for mis, matching, and vertex cover M Ghaffari, T Gouleakis, C Konrad, S Mitrović, R Rubinfeld Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing …, 2018 | 142 | 2018 |
Sublinear algorithms for testing monotone and unimodal distributions T Batu, R Kumar, R Rubinfeld Proceedings of the thirty-sixth annual ACM symposium on Theory of computing …, 2004 | 140 | 2004 |
Testing k-wise and almost k-wise independence N Alon, A Andoni, T Kaufman, K Matulef, R Rubinfeld, N Xie Proceedings of the thirty-ninth annual ACM symposium on Theory of computing …, 2007 | 136 | 2007 |
Maintaining a large matching and a small vertex cover K Onak, R Rubinfeld Proceedings of the forty-second ACM symposium on Theory of computing, 457-464, 2010 | 132 | 2010 |