__
TR15-006 | 6th January 2015 10:09
__

#### Dense Testers: Almost Linear Time and Locally Explicit Constructions

**Abstract:**
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.