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\}

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.