Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-006 | 6th January 2015 10:09

Dense Testers: Almost Linear Time and Locally Explicit Constructions


Authors: Nader Bshouty
Publication: 6th January 2015 16:38
Downloads: 1382


We develop a new notion called {\it $(1-\epsilon)$-tester for a
set $M$ of functions} $f:A\to C$. A $(1-\epsilon)$-tester
for $M$ maps each element $a\in A$ to a finite number of
elements $B_a=\{b_1,\ldots,b_t\}\subset B$ in a smaller
sub-domain $B\subset A$ where for every $f\in M$ if
$f(a)\not=0$ then $f(b)\not=0$ for at least $(1-\epsilon)$
fraction of the elements $b$ of $B_a$. I.e., if
$f(a)\not=0$ then $\Pr_{b\in B_a}[f(b)\not=0]\ge
1-\epsilon$. The {\it size} of the $(1-\epsilon)$-tester is
$\max_{a\in A}|B_a|$. The goal is to minimize this size,
construct $B_a$ in deterministic almost linear time and access
and compute each map in poly-log time.

We use tools from elementary algebra and algebraic function fields
to build $(1-\epsilon)$-testers of small size in deterministic
almost linear time. We also show that our constructions
are locally explicit, i.e.,
one can find any entry in the construction in time poly-log in the size
of the construction and the field size.
We also prove lower bounds that show that the
sizes of our testers and the densities are almost optimal.

Testers were used in [Bshouty, Testers and its application, ITCS 2014] to construct almost optimal perfect hash families, universal sets, cover-free families,
separating hash functions, black box identity testing and hitting sets.
The dense testers in this paper shows that such constructions can be done
in almost linear time, are locally explicit and can be made to be dense.

ISSN 1433-8092 | Imprint