Property testing is the study of probabilistic algorithms that inspect a given object in few selected locations, and try to decide whether the object has some predetermined property or is significantly different from any object having that property. This is a widely-studied model in theoretical computer science, which is closely related to probabilistically checkable proofs, coding theory, computational learning theory and more.
The main focus of this thesis is a new type of problems in property testing, called dual problems. For a set $\Pi$ in a metric space and $\delta>0$, denote by $F_\delta(\Pi)$ the set of elements that are $\delta$-far from $\Pi$. Then, in property testing, a $\delta$-tester for $\Pi$ is required to accept inputs from $\Pi$ and reject inputs from $F_\delta(\Pi)$. A natural dual problem is the problem of $\delta$-testing the set of "no" instances, that is $F_\delta(\Pi)$: A $\delta$-tester for $F_\delta(\Pi)$ needs to accept inputs from $F_\delta(\Pi)$ and reject inputs that are $\delta$-far from $F_\delta(\Pi)$, that is, reject inputs from $F_\delta(F_\delta(\Pi))$. When $\Pi=F_\delta(F_\delta(\Pi))$ the dual problem is essentially equivalent to the original one, but this equality does not hold in general.
Many dual problems constitute appealing testing problems that are interesting by themselves. In this work we study sets of the form $F_\delta(F_\delta(\Pi))$, and apply this study to investigate several natural dual problems. In particular, we derive lower bounds and upper bounds on the query complexity of dual problems of properties of functions (e.g., testing error-correcting codes and testing monotone functions), of properties of distributions (e.g., testing equivalence to a known distribution), and of various graph properties in the dense graph model (e.g., testing $k$-colorability) and in the bounded-degree model (e.g., testing connectivity and cycle-free graphs). We also show that testing any dual problem with one-sided error is either trivial or requires a linear number of queries.
The thesis also includes excerpts from an unrelated work, which focuses on property testing lower bounds via reductions from other computational models (following Blais, Brody, and Matulef (2012)), attached as appendices.
Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, August 2015.
Available: the thesis (in PDF file).
Back to Oded Goldreich's homepage.