| Year |
Citation |
Score |
| 2018 |
Aliakbarpour M, Biswas AS, Gouleakis T, Peebles J, Rubinfeld R, Yodpinyanee A. Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling Algorithmica. 80: 668-697. DOI: 10.1007/S00453-017-0287-3 |
0.474 |
|
| 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.463 |
|
| 2016 |
Canonne CL, Diakonikolas I, Gouleakis T, Rubinfeld R. Testing shape restrictions of discrete distributions Leibniz International Proceedings in Informatics, Lipics. 47. DOI: 10.1007/S00224-017-9785-6 |
0.542 |
|
| 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.359 |
|
| 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.424 |
|
| 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.448 |
|
| 2014 |
Levi R, Ron D, Rubinfeld R. Testing similar means Siam Journal On Discrete Mathematics. 28: 1699-1724. DOI: 10.1137/120903737 |
0.511 |
|
| 2014 |
Levi R, Ron D, Rubinfeld R. Local algorithms for sparse spanning graphs Leibniz International Proceedings in Informatics, Lipics. 28: 826-842. DOI: 10.1007/S00453-019-00612-6 |
0.464 |
|
| 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.472 |
|
| 2013 |
Levi R, Ron D, Rubinfeld R. Testing Properties of Collections of Distributions Theory of Computing. 9: 295-347. DOI: 10.4086/Toc.2013.V009A008 |
0.533 |
|
| 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.795 |
|
| 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.425 |
|
| 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.379 |
|
| 2012 |
Ron D, Rubinfeld R, Safra M, Samorodnitsky A, Weinstein O. Approximating the influence of monotone Boolean functions in O(√n) query complexity Acm Transactions On Computation Theory. 4. DOI: 10.1145/2382559.2382562 |
0.47 |
|
| 2012 |
Rubinfeld R. Taming big probability distributions Acm Crossroads Student Magazine. 19: 24-28. DOI: 10.1145/2331042.2331052 |
0.476 |
|
| 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.345 |
|
| 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.343 |
|
| 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.347 |
|
| 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.518 |
|
| 2010 |
Matulef K, O'Donnell R, Rubinfeld R, Servedio RA. Testing Halfspaces Siam Journal On Computing. 39: 2004-2047. DOI: 10.1137/070707890 |
0.495 |
|
| 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.535 |
|
| 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.389 |
|
| 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.447 |
|
| 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.38 |
|
| 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.386 |
|
| 2009 |
Rubinfeld R, Servedio RA. Testing monotone high-dimensional distributions Random Structures and Algorithms. 34: 24-44. DOI: 10.1002/Rsa.V34:1 |
0.432 |
|
| 2009 |
Rubinfeld R, Servedio RA. Testing monotone high-dimensional distributions Random Structures and Algorithms. 34: 24-44. DOI: 10.1002/rsa.20247 |
0.506 |
|
| 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.454 |
|
| 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.791 |
|
| 2006 |
Rubinfeld R. Sublinear time algorithms International Congress of Mathematicians, Icm 2006. 3: 1095-1110. DOI: 10.1137/100791075 |
0.469 |
|
| 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.417 |
|
| 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.365 |
|
| 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.43 |
|
| 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.745 |
|
| 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.401 |
|
| 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.791 |
|
| 2003 |
Kumar R, Rubinfeld R. Algorithms column: sublinear time algorithms Sigact News. 34: 57-67. DOI: 10.1145/954092.954103 |
0.454 |
|
| 2003 |
Parnas M, Ron D, Rubinfeld R. On Testing Convexity and Submodularity Siam Journal On Computing. 32: 1158-1184. DOI: 10.1137/S0097539702414026 |
0.512 |
|
| 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.397 |
|
| 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.746 |
|
| 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.356 |
|
| 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.398 |
|
| 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.362 |
|
| 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.787 |
|
| 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.386 |
|
| 2001 |
Ergün F, Kumar SR, Rubinfeld R. Checking approximate computations of polynomials and functional equations Siam Journal On Computing. 31: 550-576. DOI: 10.1137/S0097539798337613 |
0.311 |
|
| 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.759 |
|
| 2000 |
Goldreich O, Rubinfeld R, Sudan M. Learning Polynomials with Queries: The Highly Noisy Case Siam Journal On Discrete Mathematics. 13: 535-570. DOI: 10.1137/S0895480198344540 |
0.412 |
|
| 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.359 |
|
| 1999 |
Ar S, Lipton RJ, Rubinfeld R, Sudan M. Reconstructing Algebraic Functions from Mixed Data Siam Journal On Computing. 28: 487-510. DOI: 10.1137/S0097539796297577 |
0.327 |
|
| 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. DOI: 10.1006/Inco.1997.2648 |
0.401 |
|
| 1997 |
Ron D, Rubinfeld R. Exactly Learning Automata of Small Cover Time Machine Learning. 27: 69-96. |
0.31 |
|
| 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.581 |
|
| 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.468 |
|
| 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.4 |
|
| 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.634 |
|
| Show low-probability matches. |