Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-156 | 21st June 2023 13:20

Almost Optimal Testers for Concise Representations

RSS-Feed




Revision #1
Authors: Nader Bshouty
Accepted on: 21st June 2023 13:20
Downloads: 197
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.


Paper:

TR19-156 | 7th November 2019 14:07

Almost Optimal Testers for Concise Representations





TR19-156
Authors: Nader Bshouty
Publication: 7th November 2019 17:44
Downloads: 960
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