FDD3502 Communication Complexity 6.0 credits

1. Introduction to communication complexity, protocol partition and tiling, clique vs independent set.

2. Fooling set and rectangle size bound, rank bound, comparison of two techniques, non-determinism.

3. P = NP ∩ coNP, Separation of P and NP ∩ coNP, UP, Decision tree and composed functions.

4. Simulation theorems.

5. Randomization: Zero-error, one-sided error, EQ function and separations, Private coin vs public coin.

6. Protocol for GT_n and DISJ_nk, Distributional complexity, Yao's minimax principle.

7. Discrepancy: lower bound for IP_n, GT_n; Disjointness under product distribution.

8. Corruption bound, Razborov's hard distribution for DISJ_n, Index function.

9. Information theory primer, Index function lower bound, Information complexity.

10. Direct sum of information complexity, Lower bound for DISJn.

11. Asymmetric communication complexity, Richness method, Index function and lopsided DISJ, Application in data-structure.

12. Proof systems, Proof complexity and communication complexity, (Critical) block sensitivity.

13. Communication complexity of lifted search problem.

After having completed the course, the student should be able to

1. Define and motivate basic concepts in communication complexity theory and explain how these concepts are related to one another.

2. Describe the most important research and some state-of-the-art results in modern communication complexity theory.

3. Use standard tools and techniques in communication complexity to prove theorems and independently solve problems amenable to these methods.

4. Present complexity-theoretic arguments with mathematical stringency orally and in writing.

5. Read and understand a research article in communication complexity, and display this understanding by giving an oral presentation of the paper.

Computational complexity, Probability, Design and analysis of algorithm

Personal laptop.

1. [Bra17]Mark Braverman. Interactive Information Complexity. SIAM Review, 59(4):803-846, 2017.  

2. [BFS86]László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory (preliminary version). In Proc. 27th IEEE Symp. on Foundations of Comp. Science (FOCS), pages 337-347, 1986.  

3. [BJKS04]Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. J. Computer and System Sciences, 68(4):702-732, June 2004. (Preliminary Version in 43rd FOCS, 2002).  

4. [BR11]Mark Braverman and Anup Rao. Towards coding for maximum errors in interactive communication. In STOC, pages 159-166, 2011.  

5. [BW16]Mark Braverman and Omri Weinstein. A Discrepancy Lower Bound for Information Complexity. Algorithmica, 76(3):846-864, 2016.  

6. [CP10]Arkadev Chattopadhyay and Toniann Pitassi. The story of set disjointness. SIGACT News, 41(3):59-85, 2010. 

7. [CKLM17]Arkadev Chattopadhyay, Michal Koucký, Bruno Loff and Sagnik Mukhopadhyay. Simulation Theorems via Pseudorandom Properties. CoRR.abs/1704.06807, 2017. [ ArXiv ]

8. [DHS96]Martin Dietzfelbinger, Juraj Hromkovic, and Georg Schnitger. A Comparison of Two Lower-Bound Methods for Communication Complexity. Theor. Comput. Sci., 168(1):39-51, 1996.  

9. [GPW15] Mika Göös, Toniann Pitassi and Thomas Watson. Deterministic Communication vs. Partition Number. Proceedings of 56th FOCS, 1077-1088, 2015.  

10. [GW16] Mika Göös and Thomas Watson. Communication Complexity of Set-Disjointness for All Probabilities. Theory of Computing, 12(1):1-23, 2016.  

11. [HN12] Trinh Huynh and Jakob Nordström. On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity. Proceedings of the 44th STOC, 233-248, 2012.  

12. [HW07] Johan Håstad and Avi Wigderson. The Randomized Communication Complexity of Set Disjointness. Theory of Computing, 3(1):211-219, 2007.  

13. [JKS03] T. S. Jayram, Ravi Kumar, and D. Sivakumar. Two applications of information complexity. In Proc. 35th ACM Symp. on Theory of Computing (STOC), pages 673-682, 2003. [ bib | DOI ]

14. [Juk11] Stasys Jukna. Extremal Combinatorics - With Applications in Computer Science. Springer, 2011.  

15. [Juk12] Stasys Jukna. Boolean Function Complexity - Advances and Frontiers. Springer, 2012.  

16. [KN97] Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997.  

17. [MNWS98] Peter Bro Miltersen, Noam Nisan, Shmuel Safra and Avi Wigderson On Data Structures and Asymmetric Communication Complexity. J. Comput. Syst. Sci., 57(1): 37-49, 1998.  

18. [RY18] Anup Rao and Amir Yehudayoff. Communication Complexity (Early Draft). 

If the course is discontinued, students may request to be examined during the following two academic years.

• EXA1 - Exam, 6.0 credits, grading scale: P, F

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

Each student who is crediting the course should

1. attend lectures,

2. solve (3) problem sets, and

3. give an technical oral presentation of a paper.

In order to pass the course, a student should

1. solve all problem sets and score at least 60% marks in all of them, and

2. give a satisfactory technical oral presentation of a paper.

Danupon Na Nongkai

• All members of a group are responsible for the group's work.
• In any assessment, every student shall honestly disclose any help received and sources used.
• In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.