Lecture on introduction to Communication Complexity.


0:00 Introduction
02:30 Protocols, deterministic communication complexity
08:20 Examples
20:10 Protocol Tree

24:30 Det complexity of equality is at least n

36:08 Set disjointness

39:15 Function Matrix
43:45 Combinatorial Rectangle
53:40 Lower bound in terms of rectangles
59:35 Log Rank Conjecture
1:01:38 Summary

свернуть