The Strength of Equality Oracles in Communication

on YouTube ↗18m

" summary

Provides tight (up to polylog factors) characterizations of NP^EQ, ∃·EQ, UP^EQ and U·EQ in terms of the blocky covering number, the blocky partition number, and the binary gamma 2 norm of the communication matrix. Shows that for nondeterministic models a single equality oracle call is essentially as powerful as many, uses blocky-matrix covers and the alpha/beta rectangle ratio to reprove SINK XOR’s low approximate rank and to separate NP^EQ from MA.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 0:18Communication Complexity
3. 2:04Communication Matrices
4. 2:27The EQUALITY Function
5. 3:09Example: The GREATER THAN Function
6. 3:59EQUALITY Oracles vs. Randomness
7. 4:38Models in Our Paper
8. 5:24Matrix Characterizations: Blocky Matrices
9. 6:13Blocky Covering Number Example
10. 7:16Matrix Characterizations: Binary Factorization Norm
11. 7:59Matrix Characterizations: Summary
12. 9:02Application: Upper Bounds.
13. 12:41Application: Lower Bounds (Proof Sketch)
14. 16:27Open Problems: Intersection Classes (Ideas)