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.