Document Open Access Logo

Erasure-Resilient Sublinear-Time Graph Algorithms

Authors Amit Levi, Ramesh Krishnan S. Pallavoor , Sofya Raskhodnikova, Nithin Varma

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.80.pdf
  • Filesize: 0.6 MB
  • 20 pages

Document Identifiers

Author Details

Amit Levi
  • David R. Cheriton School of Computer Science, University of Waterloo, Canada
Ramesh Krishnan S. Pallavoor
  • Department of Computer Science, Boston University, MA, USA
Sofya Raskhodnikova
  • Department of Computer Science, Boston University, MA, USA
Nithin Varma
  • Department of Computer Science, University of Haifa, Israel

Funding

  • Levi, Amit: Part of this work was done while the author was visiting Boston University.
  • Pallavoor, Ramesh Krishnan S.: The work of this author was partially supported by NSF award CCF-1909612 and was done in part while the author was visiting the Simons Institute for the Theory of Computing.
  • Raskhodnikova, Sofya: The work of this author was partially supported by NSF award CCF-1909612 and was done in part while the author was visiting the Simons Institute for the Theory of Computing.
  • Varma, Nithin: The work of this author was partially supported by ISF grant 497/17 and Israel PBC Fellowship for Outstanding Postdoctoral Researchers from India and China. This work was done in part while the author was a student at Boston University.

Acknowledgements

We thank Talya Eden for useful discussions that led to simplification of analysis in Section 3.1.

Cite AsGet BibTex

Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma. Erasure-Resilient Sublinear-Time Graph Algorithms. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 80:1-80:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITCS.2021.80

Abstract

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 ε-far from connected and estimating the average degree. For testing connectedness, we discover a threshold phenomenon: when the fraction of erasures is less than ε, this property can be tested efficiently (in time independent of the size of the graph); when the fraction of erasures is at least ε, 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 ε. For estimating the average degree, our results provide an "interpolation" 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. `06), and with degree queries and neighbor queries, investigated by Goldreich and Ron (Random Struct. Algorithms `08) and Eden et al. (ICALP `17). We conclude with a discussion of our model and open questions raised by our work.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
  • Mathematics of computing → Approximation algorithms
Keywords
  • Graph property testing
  • Computing with incomplete information
  • Approximating graph parameters

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Maryam Aliakbarpour, Amartya Shankha Biswas, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, and Anak Yodpinyanee. Sublinear-time algorithms for counting star subgraphs via edge sampling. Algorithmica, 80(2):668-697, 2018. URL: https://doi.org/10.1007/s00453-017-0287-3.
  2. Sepehr Assadi, Michael Kapralov, and Sanjeev Khanna. A simple sublinear-time algorithm for counting arbitrary subgraphs via edge sampling. In Proc. of Innovations in Theoretical Computer Science (ITCS), pages 6:1-6:20, 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.6.
  3. Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Ron D. Rothblum. Hard properties with (very) short PCPPs and their applications. In Proc. of Innovations in Theoretical Computer Science (ITCS), pages 9:1-9:27, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.9.
  4. Petra Berenbrink, Bruce Krayenhoff, and Frederik Mallmann-Trenn. Estimating the number of connected components in sublinear time. Inf. Process. Lett., 114(11):639-642, 2014. URL: https://doi.org/10.1016/j.ipl.2014.05.008.
  5. Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. L_p-testing. In Proc. of ACM Symposium on Theory of Computing (STOC), pages 164-173, 2014. URL: https://doi.org/10.1145/2591796.2591887.
  6. Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the minimum spanning tree weight in sublinear time. SIAM J. Comput., 34(6):1370-1379, 2005. URL: https://doi.org/10.1137/S0097539702403244.
  7. Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin Varma. Erasure-resilient property testing. SIAM J. Comput., 47(2):295-329, 2018. URL: https://doi.org/10.1137/16M1075661.
  8. Talya Eden, Amit Levi, Dana Ron, and C. Seshadhri. Approximately counting triangles in sublinear time. SIAM J. Comput., 46(5):1603-1646, 2017. URL: https://doi.org/10.1137/15M1054389.
  9. Talya Eden, Dana Ron, and C. Seshadhri. Sublinear time estimation of degree distribution moments: The degeneracy connection. In Proc. of Intl. Colloquium on Automata, Languages and Programming (ICALP), pages 7:1-7:13, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.7.
  10. Talya Eden, Dana Ron, and C. Seshadhri. Extremely simple algorithm for estimating the number of edges. Personal Communication, 2019. Google Scholar
  11. Talya Eden, Dana Ron, and C. Seshadhri. On approximating the number of k-cliques in sublinear time. SIAM J. Comput., 49(4):747-771, 2020. URL: https://doi.org/10.1137/18M1176701.
  12. Talya Eden and Will Rosenbaum. Lower bounds for approximating graph parameters via communication complexity. In Proc. of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX-RANDOM), pages 11:1-11:18, 2018. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.11.
  13. Uriel Feige. On sums of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM J. Comput., 35(4):964-984, 2006. URL: https://doi.org/10.1137/S0097539704447304.
  14. Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781108135252.
  15. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. URL: https://doi.org/10.1145/285055.285060.
  16. Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. Algorithmica, 32(2):302-343, 2002. URL: https://doi.org/10.1007/s00453-001-0078-7.
  17. Oded Goldreich and Dana Ron. Approximating average parameters of graphs. Random Struct. Algorithms, 32(4):473-493, 2008. URL: https://doi.org/10.1002/rsa.20203.
  18. Mira Gonen, Dana Ron, and Yuval Shavitt. Counting stars and other small subgraphs in sublinear-time. SIAM J. Discrete Math., 25(3):1365-1411, 2011. URL: https://doi.org/10.1137/100783066.
  19. Tali Kaufman, Michael Krivelevich, and Dana Ron. Tight bounds for testing bipartiteness in general graphs. SIAM J. Comput., 33(6):1441-1483, 2004. URL: https://doi.org/10.1137/S0097539703436424.
  20. Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma. Erasure-resilient sublinear-time graph algorithms. CoRR, abs/2011.14291, 2020. URL: http://arxiv.org/abs/2011.14291.
  21. Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma. Improved bounds for k-connectedness testing. Unpublished manuscript, 2020. Google Scholar
  22. Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Erik Waingarten. Approximating the distance to monotonicity of Boolean functions. In Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1995-2009, 2020. URL: https://doi.org/10.1137/1.9781611975994.123.
  23. Michal Parnas and Dana Ron. Testing the diameter of graphs. Random Struct. Algorithms, 20(2):165-183, 2002. URL: https://doi.org/10.1002/rsa.10013.
  24. Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. J. Comput. Syst. Sci., 72(6):1012-1042, 2006. URL: https://doi.org/10.1016/j.jcss.2006.03.002.
  25. Sofya Raskhodnikova, Noga Ron-Zewi, and Nithin Varma. Erasures vs. errors in local decoding and property testing. In Proc. of Innovations in Theoretical Computer Science (ITCS), pages 63:1-63:21, 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.63.
  26. Sofya Raskhodnikova and Adam D. Smith. A note on adaptivity in testing properties of bounded degree graphs. Electronic Colloquium on Computational Complexity (ECCC), 13(089), 2006. URL: http://eccc.hpi-web.de/eccc-reports/2006/TR06-089/index.html.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact