Show simple item record

dc.contributor.authorLevi, Amiten_US
dc.contributor.authorPallavoor, Ramesh Krishnan S.en_US
dc.contributor.authorRaskhodnikova, Sofyaen_US
dc.contributor.authorVarma, Nithinen_US
dc.date.accessioned2021-11-04T12:49:47Z
dc.date.available2021-11-04T12:49:47Z
dc.date.issued2020
dc.identifier.citationA. Levi, R.K.S. Pallavoor, S. Raskhodnikova, N. Varma. 2020. "Erasure-Resilient Sublinear-Time Graph Algorithms.." CoRR, Volume abs/2011.14291, https://arxiv.org/abs/2011.14291
dc.identifier.urihttps://hdl.handle.net/2144/43266
dc.description.abstractWe 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.en_US
dc.language.isoen_US
dc.relation.ispartofCoRR
dc.rightsThis work is distributed under a Creative Commons Attribution 4.0 International (CC BY 4.0) license.en_US
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/
dc.titleErasure-resilient sublinear-time graph algorithmsen_US
dc.typeArticleen_US
dc.description.versionFirst author draften_US
pubs.elements-sourcedblpen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Arts & Sciencesen_US
pubs.organisational-groupBoston University, College of Arts & Sciences, Department of Computer Scienceen_US
dc.identifier.mycv576075


This item appears in the following Collection(s)

Show simple item record

This work is distributed under a Creative Commons Attribution 4.0 International (CC BY 4.0) license.
Except where otherwise noted, this item's license is described as This work is distributed under a Creative Commons Attribution 4.0 International (CC BY 4.0) license.