PhD Seminar • Algorithms and Complexity — Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of GraphsExport this event to calendar

Wednesday, March 13, 2019 1:30 PM EDT

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.

Location 
MC - Mathematics & Computer Building
5501
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
  1. 2024 (96)
    1. April (19)
    2. March (27)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)