The KRW Conjecture: Results and Open Problems

on YouTube ↗33m

" summary

KRW conjecture claims depth(f ∘ g) is essentially depth(f) + depth(g); proven cases replace “essentially” with small losses only for specific inners: universal relation, parity, and compositions mixing a function with the universal relation. Proofs use the Karchmer–Wigderson communication equivalence and adversary arguments that track per-row progress via an information-theoretic adversary. Open problems: handle arbitrary inner g, prove the composition lower bound when g is the multiplexer relation (candidate complete problem), or for natural inners like connectivity, clique, or other monotone functions.

AI-written summary · about

" chapters (11)

1. 0:00Introduction to the conjecture
2. 1:02Circuit complexity background
3. 3:51The KW conjecture
4. 5:14The KW relations framework
5. 7:33Analyzing KW relations
6. 9:36Universal relations results
7. 12:35Recent progress in proofs
8. 15:08Proof strategy and adversaries
9. 21:46Future directions
10. 25:22Proposed research problems
11. 30:52Discussion and concluding remarks