Lidor Avigad

Abstract of Master Thesis (Weizmann Inst., 2009)

On the lowest level of query complexity in testing graph properties

In this thesis, we continue the work of Goldreich and Ron in (ECCC 2008) by presenting an infinite family of natural properties of dense graphs having non-adaptive testers of query complexity of $\Otilde{\eps^{-1}}$, where $\eps$ is the proximity parameter. Specifically, for every fixed graph $H$, we show a non-adaptive tester of query complexity $\Otilde{\eps^{-1}}$ for the property of being a blow-up $H$. This considerably extends the result of Goldreich and Ron that corresponds to the special case in which $H$ consists of a complete graph.

Our techniques significantly extend those of Goldreich and Ron, while coping with difficulties that emerge from the "non forcing" structure of a blow-up of a non-clique.

Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, December 2009.

Available: the thesis (in PDF).

Back to Oded Goldreich's homepage.