Lucky Talk: A Communication Game Approach to the Sensitivity Conjecture
summary
Defines a streaming game where an input permutation σ arrives and bits are irrevocably written to positions; Bob sees the final vector and must output a set that intersects the last position. Constructs a protocol that views indices as GF(2)^k indices, writes zeros for the first n−t positions, then picks the smallest subset S whose XOR with the written zeros is 0 and writes zeros on S and ones elsewhere; with t = log^2 n the residual entropy is O(log log n). Shows monotone protocols admit a worst‑case cost Ω(√n), while non‑monotone and larger alphabets yield much smaller costs.
AI-written summary · about