Local reconstructors and tolerant testers for connectivity and diameter

Andrea Campagna, Alan Guo, Ronitt Rubinfeld

A local property reconstructor for a graph property is an algorithm which, given oracle access to the adjacency list of a graph that is "close" to having the property, provides ora…