Certificate games

on YouTube ↗21m

" summary

Defines a zero-communication certificate game that yields four complexity measures: CG (private randomness), CG_pub (shared randomness), CG (shared entanglement) and CG_ns (non-signaling). Shows concrete bounds: CG ≤ C0·C1 and parity achieves CG = n^2; CG_pub ≤ C(f) and ≤ R(f) with Tribes giving CG_pub = Θ(√n) while CG = Θ(n); CG_ns ≥ fractional certificate complexity and for OR proves CG_ns ≥ n. Single-bit CG_pub equals sensitivity and private single-bit CG equals spectral sensitivity squared*.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 0:41Certificate Games
3. 1:38Certificate Game Complexity Variants
4. 2:50Related concepts
5. 3:57Outline
6. 6:30Can shared randomness help?
7. 7:40Example: Tribes function
8. 10:53Public randomness helps in Tribes
9. 12:30Analysis
10. 13:42Definition: Query Complexity
11. 16:13Non-signalling strategies
12. 17:55Definition: Fractional certificate complexity
13. 19:51Single bit versions
14. 20:22Open Questions