Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-011 | 7th February 2012 13:01

Testers and their Applications


Authors: Nader Bshouty
Publication: 7th February 2012 16:28
Downloads: 3927


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.

ISSN 1433-8092 | Imprint