Distribution-Free Junta Testing

on YouTube ↗35m

" summary

Shows nonadaptive distribution-free junta testing needs exponential queries and gives an efficient adaptive alternative: a 2^{Ω(k)} lower bound comes from a yes/no distribution-of-(distribution,function) construction that places uniform mass on ~2^k points and plants large Hamming-ball construction differences so samples look identical and nonadaptive queries can’t find disagreeing pairs. Adaptivity yields a one-sided tester that uses O(k^2/ε) queries (poly(k)/ε, sketched via block-wise binary search, maintaining witness X/Y pairs per block and running uniform-case 1-junta subtests to refine blocks).

AI-written summary · about

" chapters (16)

1. 0:00Introduction
2. 0:46Testing Algorithm
3. 1:10Uniform Distribution Model
4. 5:51Background
5. 7:11Results
6. 10:25Lower Bound
7. 14:47Intuition
8. 16:26Adaptive Algorithm
9. 17:17Simplified Algorithm
10. 19:25Query Complexity
11. 21:01Simple Variant
12. 21:58Future Work
13. 23:55Algorithm Setup
14. 25:53Defining Relevant Variables
15. 28:12Uniform Distribution Testing
16. 29:41Future Directions