Testing Graph Blow-Up
Webpage for a paper by Lidor Avigad and Oded Goldreich
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
- First version posted:
- Revisions: none yet.
either Oded Goldreich's homepage.
or general list of papers.