{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T19:28:42Z","timestamp":1776194922563,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,12,15]],"date-time":"2021-12-15T00:00:00Z","timestamp":1639526400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1909612"],"award-info":[{"award-number":["CCF-1909612"]}]},{"name":"ISF","award":["497\/17"],"award-info":[{"award-number":["497\/17"]}]},{"name":"Israel PBC Fellowship for Outstanding Postdoctoral Researchers from India and China"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2022,3,31]]},"abstract":"<jats:p>We investigate sublinear-time algorithms that take partially erased graphs represented by adjacency lists as input. Our algorithms make degree and neighbor queries to the input graph and work with a specified fraction of adversarial erasures in adjacency entries. We focus on two computational tasks: testing if a graph is connected or \u03b5-far from connected and estimating the average degree. For testing connectedness, we discover a threshold phenomenon: when the fraction of erasures is less than \u03b5, this property can be tested efficiently (in time independent of the size of the graph); when the fraction of erasures is at least \u03b5, then a number of queries linear in the size of the graph representation is required. Our erasure-resilient algorithm (for the special case with no erasures) is an improvement over the previously known algorithm for connectedness in the standard property testing model and has optimal dependence on the proximity parameter \u03b5. For estimating the average degree, our results provide an \u201cinterpolation\u201d between the query complexity for this computational task in the model with no erasures in two different settings: with only degree queries, investigated by Feige (SIAM J. Comput. \u201806), and with degree queries and neighbor queries, investigated by Goldreich and Ron (Random Struct. Algorithms \u201808) and Eden et\u00a0al. (ICALP \u201817). We conclude with a discussion of our model and open questions raised by our work.<\/jats:p>","DOI":"10.1145\/3488250","type":"journal-article","created":{"date-parts":[[2021,12,15]],"date-time":"2021-12-15T16:02:45Z","timestamp":1639584165000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Erasure-Resilient Sublinear-Time Graph Algorithms"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8530-5182","authenticated-orcid":false,"given":"Amit","family":"Levi","sequence":"first","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ramesh Krishnan S.","family":"Pallavoor","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Boston University, Boston, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4902-050X","authenticated-orcid":false,"given":"Sofya","family":"Raskhodnikova","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Boston University, Boston, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1211-2566","authenticated-orcid":false,"given":"Nithin","family":"Varma","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute, Kelambakkam, Tamil Nadu, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,12,15]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0287-3"},{"key":"e_1_3_2_3_2","series-title":"Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS\u201919),","first-page":"6:1\u20136:20","volume":"124","author":"Assadi Sepehr","year":"2019","unstructured":"Sepehr Assadi, Michael Kapralov, and Sanjeev Khanna. 2019. A simple sublinear-time algorithm for counting arbitrary subgraphs via edge sampling. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS\u201919),LIPIcs, Vol. 124, Avrim Blum (Ed.). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 6:1\u20136:20. https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2019.6"},{"key":"e_1_3_2_4_2","series-title":"Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS\u201920),","first-page":"9:1\u20139:27","volume":"151","author":"Ben-Eliezer Omri","year":"2020","unstructured":"Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Ron D. Rothblum. 2020. Hard properties with (very) short PCPPs and their applications. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS\u201920),LIPIcs, Vol. 151, Thomas Vidick (Ed.). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 9:1\u20139:27. https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2020.9"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.05.008"},{"key":"e_1_3_2_6_2","series-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","first-page":"90:1\u201390:14","volume":"55","author":"Berman Piotr","year":"2016","unstructured":"Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. 2016. Tolerant testers of image properties. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)LIPIcs, Vol. 55, Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi (Eds.). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 90:1\u201390:14. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.90"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591887"},{"key":"e_1_3_2_8_2","first-page":"174","article-title":"Isoperimetric inequalities for real-valued functions with applications to monotonicity testing","volume":"27","author":"Black Hadley","year":"2020","unstructured":"Hadley Black, Iden Kalemaj, and Sofya Raskhodnikova. 2020. Isoperimetric inequalities for real-valued functions with applications to monotonicity testing. Electron. Colloq. Comput. Complex. 27 (2020), 174.","journal-title":"Electron. Colloq. Comput. Complex."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403244"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1075661"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1054389"},{"key":"e_1_3_2_12_2","unstructured":"Talya Eden Dana Ron and C. Seshadhri. 2019. Extremely simple algorithm for estimating the number of edges. (2019). Personal communication."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1159014"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1176701"},{"key":"e_1_3_2_15_2","series-title":"Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization and the Conference on Algorithms and Techniques in Computer Science (APPROX\/RANDOM 2018),","first-page":"11:1\u201311:18","volume":"116","author":"Eden Talya","year":"2018","unstructured":"Talya Eden and Will Rosenbaum. 2018. Lower bounds for approximating graph parameters via communication complexity. In Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization and the Conference on Algorithms and Techniques in Computer Science (APPROX\/RANDOM 2018),LIPIcs, Vol. 116, Eric Blais, Klaus Jansen, Jos\u00e9 D. P. Rolim, and David Steurer (Eds.). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 11:1\u201311:18. https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2018.11"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704447304"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108135252"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.5555\/1387061.1387065"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/100783066"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436424"},{"key":"e_1_3_2_23_2","series-title":"Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS\u201921),","first-page":"80:1\u201380:20","volume":"185","author":"Levi Amit","year":"2021","unstructured":"Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma. 2021. Erasure-resilient sublinear-time graph algorithms. In Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS\u201921),LIPIcs, Vol. 185, James R. Lee (Ed.). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 80:1\u201380:20. https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2021.80"},{"key":"e_1_3_2_24_2","series-title":"Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP\u201921),","first-page":"100:1\u2013100:20","volume":"198","author":"Newman Ilan","year":"2021","unstructured":"Ilan Newman and Nithin Varma. 2021. New sublinear algorithms and lower bounds for LIS estimation. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP\u201921),LIPIcs, Vol. 198, Nikhil Bansal, Emanuela Merelli, and James Worrell (Eds.). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 100:1\u2013100:20. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.100"},{"key":"e_1_3_2_25_2","unstructured":"Ramesh Krishnan S. Pallavoor Sofya Raskhodnikova and Nithin Varma. 2020. Improved bounds for k -connectedness testing(unpublished)."},{"key":"e_1_3_2_26_2","doi-asserted-by":"crossref","unstructured":"Ramesh Krishnan S. Pallavoor Sofya Raskhodnikova and Erik Waingarten. 2021. Approximating the distance to monotonicity of Boolean functions. https:\/\/doi.org\/10.1002\/rsa.21029","DOI":"10.1137\/1.9781611975994.123"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10013.abs"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"e_1_3_2_29_2","series-title":"Proceedings of the Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201903), and Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM\u201903)","first-page":"370","volume":"2764","author":"Raskhodnikova Sofya","year":"2003","unstructured":"Sofya Raskhodnikova. 2003. Approximate testing of visual properties. In Proceedings of the Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201903), and Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM\u201903)Lecture Notes in Computer Science, Vol. 2764, Sanjeev Arora, Klaus Jansen, Jos\u00e9 D. P. Rolim, and Amit Sahai (Eds.). Springer, 370\u2013381. https:\/\/doi.org\/10.1007\/978-3-540-45198-3_31"},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","unstructured":"Sofya Raskhodnikova Noga Ron-Zewi and Nithin Varma. 2021. Erasures versus errors in local decoding and property testing. Random Structures & Algorithms 59 4 (2021) 640\u2013670. DOI:https:\/\/doi.org\/10.1002\/rsa.21031","DOI":"10.1002\/rsa.21031"},{"issue":"89","key":"e_1_3_2_31_2","article-title":"A note on adaptivity in testing properties of bounded degree graphs","volume":"13","author":"Raskhodnikova Sofya","year":"2006","unstructured":"Sofya Raskhodnikova and Adam D. Smith. 2006. A note on adaptivity in testing properties of bounded degree graphs. Electron. Colloq. Comput. Complex. 13, 89 (2006).","journal-title":"Electron. Colloq. Comput. Complex."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3488250","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3488250","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3488250","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:23Z","timestamp":1750188623000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3488250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,15]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.1145\/3488250"],"URL":"https:\/\/doi.org\/10.1145\/3488250","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,15]]},"assertion":[{"value":"2020-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}