Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-156 | 7th November 2019 14:07

Almost Optimal Testers for Concise Representations

RSS-Feed




TR19-156
Authors: Nader Bshouty
Publication: 7th November 2019 17:44
Downloads: 107
Keywords: 


Abstract:

We give improved and almost optimal testers for several classes of Boolean functions on $n$ inputs that have concise representation in the uniform and distribution-free model. Classes, such as $k$-Junta, $k$-Linear Function, $s$-Term DNF, $s$-Term Monotone DNF, $r$-DNF, Decision List, $r$-Decision List, size-$s$ Decision Tree, size-$s$ Boolean Formula, size-$s$ Branching Program, $s$-Sparse Polynomial over the binary field and functions with Fourier Degree at most $d$.



ISSN 1433-8092 | Imprint