## Lower Bounds for Tolerant Junta and Unateness Testing via Rejection
Sampling of Graphs

by Amit Levi and Erik Waingarten

#### Oded's comments

I missed the ECCC posting at the time,
but picked up from the monthly review of the
Property Testing Review.
I reproduce Gautam Kamath's
take on this paper, which reads

This paper proves a number of new lower bounds for tolerant testing of
Boolean functions, including non-adaptive k-junta testing and adaptive and
non-adaptive unateness testing. Combined with upper bounds for these and
related problems, these results establishes separation between the
complexity of tolerant and non-tolerant testing for natural properties of
Boolean functions, which have so far been elusive.

Let me add that I disagree with the authors' claim to introducing
a (new) model for testing graph properties. In my opinion, what
they introduce is a technique for proving lower bounds on property
testing tasks. Indeed, their proof technique consists of showing
that too good testers for such tasks yield an algorithm for
distinguishing balanced bicliques from their complements that violates
a (easy to prove) lower bound regarding a rather weird complexity measure.

#### The original abstract

We introduce a new model for testing graph properties which we call the
\emph{rejection sampling model}. We show that testing bipartiteness of
n-nodes graphs using rejection sampling queries requires complexity
tildeOmega(n^2). Via reductions from the rejection sampling model, we give
three new lower bounds for tolerant testing of Boolean functions of the
form f:\{0,1\}^n\to\{0,1\}

- Tolerant k-junta testing with \emph{non-adaptive} queries requires
tildeOmega(k^2) queries.
- Tolerant unateness testing requires (n) queries.
- Tolerant unateness testing with \emph{non-adaptive} queries requires
tildeOmega(n^{3/2}) queries.

Given the tildeO(k^{3/2}) -query non-adaptive junta tester of Blais
\cite{B08}, we conclude that non-adaptive tolerant junta testing requires
more queries than non-tolerant junta testing. In addition, given the
tildeO(n^{3/4}) -query unateness tester of Chen, Waingarten, and Xie
\cite{CWX17b} and the tildeO(n)-query non-adaptive unateness tester of
Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova, and Seshadhri
\cite{BCPRS17}, we conclude that tolerant unateness testing requires more
queries than non-tolerant unateness testing, in both adaptive and
non-adaptive settings. These lower bounds provide the first separation
between tolerant and non-tolerant testing for a natural property of Boolean
functions.
See ECCC TR18-094.

Back to
list of Oded's choices.