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

Bibliographic Details
Main Author: Bshouty, Nader H.
Format: text
Published: 2014
Subjects:
Online Access:http://arxiv.org/abs/1412.5889