Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > TESTERS:
Reports tagged with Testers:
TR15-006 | 6th January 2015
Nader Bshouty

Dense Testers: Almost Linear Time and Locally Explicit Constructions

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 ... more >>>




ISSN 1433-8092 | Imprint