Amit
Levi,
PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
We introduce a new model for testing graph properties which we call the {rejection sampling model}. We show that testing bipartiteness of n-nodes graphs using rejection sampling queries requires complexity Ω(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→{0,1}:
- Tolerant k-junta testing with {non-adaptive} queries requires Ω(k^2) queries.
- Tolerant unateness testing requires Ω(n) queries.
- Tolerant unateness testing with {non-adaptive} queries requires Ω(n^3/2) queries.
Given the O(k^3/2)-query non-adaptive junta tester of Blais, we conclude that non-adaptive tolerant junta testing requires more queries than non-tolerant junta testing. In addition, given the O(n^3/4)-query unateness tester of Chen, Waingarten, and Xie and the O(n)-query non-adaptive unateness tester of Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova, and Seshadhri, 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.