## 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.