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

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