A Communication Game Approach to the Sensitivity Conjecture

on YouTube ↗34m

" summary

Defines a streaming communication game where one player writes bits into positions revealed by a random permutation and the last position is forced to be a given bit; goal is to output a small set containing that last index. Conjecture: worst-case cost v_n >= n^δ for some δ>0, which would imply the sensitivity conjecture. Known constructions give a sqrt(n) protocol (split into blocks) and a monotone lower bound matching Θ(√n), while allowing a ternary alphabet yields an O(log n) via 3-symbol alphabet protocol, and information-theoretic and entropy variants are discussed.

AI-written summary · about

" chapters (12)

1. 0:00Introduction to the game
2. 1:20Defining the game rules
3. 4:40Game value and strategy
4. 7:24The main conjecture
5. 8:41Sensitivity conjecture
6. 14:28Proposition link
7. 17:02Protocols and bounds
8. 20:33Information-theoretic view
9. 23:34Strengthening the conjectures
10. 27:05Counterexamples and status
11. 30:01Monotone protocols
12. 32:24Proof sketch