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.