Nithin Mahendra Varma
Erasure-resilient graph property testing
Abstract: We initiate the study of erasure-resilient testers for graph
properties. Testing properties of graphs [Goldreich, Goldwasser, and
Ron '98, Goldreich and Ron '02, Parnas and Ron '02] is of fundamental
importance in the field of sublinear algorithms. Erasure-resilient
testing was defined and studied for properties of real-valued
functions by Dixit, Raskhodnikova, Thakurta and Varma (SICOMP '18).
In graph property testing, an algorithm for testing a property P is
given oracle access to a graph G represented by adjacency lists, where
the oracle answers neighbor queries in constant time.
In this talk, we will present a generalization of this model in which
a constant fraction of the entries in the adjacency lists are
adversarially erased. We will also briefly describe some preliminary
results on testing connectedness in our model. In particular, the
query complexity of erasure-resilient testing of connectedness
exhibits a threshold phenomenon: On one hand, we design an
erasure-resilient connectedness tester with query complexity
independent of the number of nodes when the fraction of erasures is
small. On the other hand, we show that every erasure-resilient
connectedness tester has query complexity that is linear in the number
of nodes, when the fraction of erasures is large.