## Roei Tell

## Abstract of Master Thesis (Weizmann Inst., 2015)

### Dual Problems in Property Testing

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.