Publications

Journal Papers

1. Testing Properties of Collections of Distributions, Theory of Computing, 9: 295-347 (2013).
   • With D. Ron and R. Rubinfeld.
2. Testing Similar Means, SIAM J. Discrete Math., 28(4), 1699-1724 (2014).
   • With D. Ron and R. Rubinfeld.
3. Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor, ACM Transactions on Algorithms 11(3): 24:1-24:13 (2015).
   • With D. Ron.
4. Constructing Near Spanning Trees with Few Local Inspections, Random Structures & Algorithms, 50(2): 183-200 (2017).
   • With G. Moshkovitz and D. Ron and R. Rubinfeld and A. Shapira.
5. Local Computation Algorithms for Graphs of Non-constant Degrees, Algorithmica 77(4): 971-994 (2017).
   • With R. Rubinfeld and A. Yodpinyanee.
6. A (Centralized) Local Guide. Bulletin of the EATCS 122 (2017).
   • With M. Medina.

Journal Papers Under Review

1. Local Algorithms for Sparse Spanning Graphs, accepted to Algorithmica (ALGO) subject to minor revisions.
   • With D. Ron and R. Rubinfeld.
2. Sublinear Random Access Generators for Preferential Attachment Graphs, submitted to SIAM Journal on Computing (SICOMP).
   • With G. Even and M. Medina and A. Rosén.
3. Testing bounded arboricity, submitted to Transactions on Algorithms (TALG).
   • With T. Eden and D. Ron.

Refereed Conference Papers

1. Testing Properties of Collections of Distributions, ITCS 2011.
   • With D. Ron and R. Rubinfeld.
2. Approximating and Testing k-Histogram Distributions in Sub-linear time, ACM SIGMOD/PODS 2012.
   • With P. Indyk and R. Rubinfeld.
3. Testing Similar Means, ICALP 2012.
   • With D. Ron and R. Rubinfeld.
4. A Simple Online Competitive Adaptation of Lempel-Ziv Compression with Efficient Random Access Support, DCC 2013.
   • With A. Dutta and D. Ron and R. Rubinfeld.
5. A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor, ICALP 2013.
   • With D. Ron.
6. Local Algorithms for Sparse Spanning Graphs, RANDOM 2014.
   • With D. Ron and R. Rubinfeld.
7. Brief Announcement: Local Computation Algorithms for Graphs of Non-Constant Degrees, SPAA 2015.
   • With R. Rubinfeld and A. Yodpinyanee.
8. Distance in the Forest Fire Model How far are you from Eve?, SODA 2016.
   • With V. Kanade and Z. Lotker and F. Mallmann-Trenn and C. Mathieu.
9. Non-local Probes Do Not Help with Many Graph Problems, DISC 2016.
   • With M. Göös and J. Hirvonen and M. Medina and J. Suomela.
10. A Local Algorithm for Constructing Spanners in Minor-Free Graphs, RANDOM 2016.
    • With D. Ron and R. Rubinfeld.
11. Brief Announcement: A Centralized Local Algorithm for the Sparse Spanning Graph Problem, DISC 2017.
    • With C. Lenzen.
12. Three Notes on Distributed Property Testing, DISC 2017.
    • With G. Even and O. Fischer and P. Fraigniaud and T. Gonen and M. Medina and P. Montealegre and D. Olivetti and R. Oshman and I. Rapaport and I. Todinca.
13. Sublinear Random Access Generators for Preferential Attachment Graphs, ICALP 2017.
    • With G. Even and M. Medina and A. Rosén.
14. Testing bounded arboricity, SODA 2018.
    • With T. Eden and D. Ron.
15. Property Testing of Planarity in the CONGEST model, PODC 2018.
    • With M. Medina and D. Ron.
16. A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error, ICALP 2018.
    • With H. Fichtenberger and Y. Vasudev and M. Wötzel.
17. A Centralized Local Algorithm for the Sparse Spanning Graph Problem, ICALP 2018.
    • With C. Lenzen.

Unpublished Manuscripts

1. Closure Operators and Spam Resistance for PageRank, CoRR abs/1803.05001 (2018).
   • With L. Farach-Colton and M. Farach-Colton and M. Medina and M. A. Mosteiro.