Almost Optimal Testers for Concise Representations

by Nader Bshouty

Oded's comments

The results seem impressive enpugh to recommend the paper without knowing how they are obtained. (I decided to do so rather than postpone the recommendation till a time in which I will be able to know more about the technical ideas.)

Added (April 2020): See overview.

The original 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$.

See ECCC TR19-156.

Back to list of Oded's choices.