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

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.