Comparison Graphs: a Unified Method for Uniformity Testing

on YouTube ↗36m

" summary

Defines comparison graph as which sample pairs to compare and proves a structural theorem: if the graph has enough edges and few two-paths dependencies then the normalized edge-collision count distinguishes uniform vs. ε-far. Recovers classical sample bound Θ(√n/ε^2) for the clique tester, shows a streaming lemma (average degree ≤ 2m) and constructs disjoint-clique graphs that achieve sample complexity Θ(n/(m ε^4)) in the streaming model, and matching optimality in several constrained models.

AI-written summary · about

" chapters (16)

1. 0:00Start
2. 0:11PROPERTY TESTING?
3. 1:54A BRIEF HISTORY OF UNIFORMITY TESTING
4. 3:43COLLISION-BASED TESTER (GR 00)
5. 7:04RECENT HISTORY
6. 10:56MOTIVATION
7. 12:07ROADMAP
8. 13:48COMPARISON GRAPHS - EXAMPLES
9. 16:37COUNTING COLLISIONS IS OPTIMAL DGPP'16
10. 17:59STRUCTURAL RESULT
11. 20:33GENERIC RECIPE
12. 25:44USING COMPARISON GRAPHS
13. 28:33CHOOSING A GRAPH
14. 32:00STREAMING MODEL - SUMMARY
15. 33:49SIMULTANEOUS MODEL - SUMMARY
16. 34:50TALK SUMMARY