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

We develop a new notion called $(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...

Full description

Main Author: text 2014 http://arxiv.org/abs/1412.5889

### Internet

http://arxiv.org/abs/1412.5889