__
TR12-011 | 7th February 2012 13:01
__

#### Testers and their Applications

**Abstract:**
We develop a new notion called {\it tester of a class $\cM$ of

functions} $f:\cA\to \cC$ that maps the elements $\bfa\in \cA$ in

the domain $\cA$ of the function to a finite number (the size of

the tester) of elements $\bfb_1,\ldots,\bfb_t$ in a smaller

sub-domain $\cB\subset \cA$ where the property $f(\bfa)\not=0$ is

preserved for all $f\in \cM$. I.e., for all $f\in \cM$ and $\bfa\in \cA$ if $f(\bfa)\not=0$ then

$f(\bfb_i)\not=0$ for some $i$.

We use tools from elementary algebra and algebraic function fields

to construct testers of almost optimal size in deterministic polynomial time in the size of the tester. We then apply testers to deterministically construct new set of objects with some combinatorial and algebraic properties that can be used to derandomize some algorithms.

We show that those new constructions are almost optimal and for many of them meet the union bound of the problem. Constructions include,

$d$-restriction problems, perfect hash, universal sets, cover-free families, separating hash functions, polynomial restriction

problems, black box polynomial identity testing for polynomials and circuits

over small fields and hitting sets.