Testing Graph Blow-Up

Webpage for a paper by Lidor Avigad and Oded Goldreich

Abstract

Referring to the query complexity of testing graph properties in the adjacency matrix model, we advance the study of the class of properties that can be tested non-adaptively within complexity that is inversely proportional to the proximity parameter. Arguably, this is the lowest meaningful complexity class in this model, and we show that it contains a very natural class of graph properties. Specifically, for every fixed graph $H$, we consider the set of all graphs that are obtained by a (possibly unbalanced) blow-up of $H$. We show a non-adaptive tester of query complexity $\tildeO(1/\e)$ that distinguishes graphs that are a blow-up of $H$ from graphs that are $\e$-far from any such blow-up.

Material available on-line

Back to either Oded Goldreich's homepage. or general list of papers.