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 (a few days later): Reading Sec 1.4, it seems that the results are obtained by a careful application of the "testing by implicit sampling" method of Diakonikolas, Lee, Matulef, Onak, Rubinfeld, Servedio, and Wan (see Chapter 6 in my introduction to property testing book). In particular, an ingredient I don't recall being used before is running a learning algorithm (also via implicit sampling) to obtain a candidate function supposedly closed to the tested function when restricted to the relevant variables.

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.