  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 $\varepsilon$-far from connected and
estimating the average degree. For testing connectedness, we discover a
threshold phenomenon: when the fraction of erasures is less than $\varepsilon$,
this property can be tested efficiently (in time independent of the size of the
graph); when the fraction of erasures is at least $\varepsilon,$ 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 $\varepsilon$. 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.
