Communication memento: Memoryless communication complexity

on YouTube ↗33m

" summary

Defines memoryless communication complexity where messages are a rewritable register and cost is the largest message size, proves tight equivalences with space‑bounded and overlay/garden‑hose models (complexity ≈ log(garden‑hose)), and characterizes the model by bipartite branching programs. Gives a simple protocol that refutes the conjectured Ω(n^2) garden‑hose lower bound for indirect storage access (reduces to linear), shows quantum versions can be exponentially smaller, and highlights that any superconstant lower bound would imply new superlinear formula and garden‑hose lower bounds; proposes 3‑clique XOR as a candidate hard function.

AI-written summary · about

" chapters (11)

1. 0:00Start
2. 2:06One-way Communication Complexity
3. 2:44What if the Players Have No Memory in Between Rounds?
4. 7:00Variants of the Memoryless Communication Complexity Model
5. 15:44Relation with the Space-bounded Model
6. 18:06Consequences of the Tight Bound
7. 21:19Inequalities Relating Various Models of Communication Complexity
8. 24:53Bipartite Branching Programs
9. 26:18Characterization
10. 27:48Towards Obtaining Better Formula Bounds
11. 30:10Open Questions