An Introduction to Communication Complexity

Presentation on theme: "An Introduction to Communication Complexity"— Presentation transcript:

1 An Introduction to Communication Complexity
姚鹏晖 助教: 刘明谋 答疑时间: 周四 2pm-4pm, 计算机科学与技术楼 502

2 Communication Protocol
回顾每一个item，定义，定理，证明

3 Example 回顾每一个item，定义，定理，证明

4 Communication Protocol
回顾每一个item，定义，定理，证明

5 Communication Protocol
回顾每一个item，定义，定理，证明

6 Communication Protocol
回顾每一个item，定义，定理，证明

7 Communication Protocol
回顾每一个item，定义，定理，证明

8 Communication Protocol
回顾每一个item，定义，定理，证明

9 Monochromatic rectangle method
# 回顾每一个item，定义，定理，证明

10 Rank method Rank ( )≤1 Rank ( )≤1 回顾每一个item，定义，定理，证明

11 Rank method Rank ( )≤1 Rank ( )≤1 回顾每一个item，定义，定理，证明

12 Example 回顾每一个item，定义，定理，证明

13 Fooling set method 回顾每一个item，定义，定理，证明

14 Example 回顾每一个item，定义，定理，证明

15 Discrepancy method # 回顾每一个item，定义，定理，证明

16 Discrepancy method # 回顾每一个item，定义，定理，证明

17 Discrepancy method # # Max ( size ( ), size ( ) ) 回顾每一个item，定义，定理，证明

18 Discrepancy method # # Max ( size ( ), size ( ) ) 回顾每一个item，定义，定理，证明

19 Why Communication Complexity?
回顾每一个item，定义，定理，证明

20 Randomized Communication Complexity
回顾每一个item，定义，定理，证明

21 Randomized Communication Complexity
回顾每一个item，定义，定理，证明

22 Randomized Communication Complexity
回顾每一个item，定义，定理，证明

23 Examples 回顾每一个item，定义，定理，证明

24 Streaming Algorithms 回顾每一个item，定义，定理，证明

25 Streaming Algorithms 回顾每一个item，定义，定理，证明

26 Quantum Communication Complexity
回顾每一个item，定义，定理，证明

27 Examples 回顾每一个item，定义，定理，证明

28 Communication Complexity
Circuit lower bound Streaming algorithms Communication Complexity Information theory Q. Communication Complexity