FDD3502 Communication Complexity 6.0 credits

Kommunikationskomplexitet

The area of communication complexity studies measures communication as computational resource---a mathematical abstraction that encompasses all the problems with communication bottleneck. The basic model of communication complexity deals with two parties, namely Alice and Bob. Their task is to compute a function on input which is distributed among them. For doing so, they communicate between each other adhering to a set of rules which they agree upon a priori, and what we measure is the number of bits they need to communicate in order to compute the function. This problem, and many of its variants, appear frequently in practice in many guises and in different levels of abstractions---in network protocols where the goal is to minimize the communication (and thereby error in communication) between two network hubs, in VLSI circuit design where the goal is to minimize energy used and to pack efficiently by decreasing the amount of wires required, also in data-structure, circuit complexity, auctions and a plethora of other interesting areas of study. In this course, we will discuss the classical results in communication complexity and also cover the recent developments and important open problems. We will discuss different models of communication complexity---deterministic, nondeterministic, asymmetric, randomized, and multiparty---and their inter-relationship. We will mostly be interested in showing combinatorial, algebraic and information theoretic techniques for showing communication complexity lower bounds, i.e., for showing that certain functions cannot be computed without a lot of communication no matter how clever the communication algorithm is.

Offering and execution

Course offering missing for current semester as well as for previous and coming semesters

Course information

Content and learning outcomes

Course contents *

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.

Intended learning outcomes *

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.

Course Disposition

15 lectures, each of 120 mins (including 2 lectures by Jakob Nordstrom regarding results from his research area), 1 paper presentation (oral) per student.

Literature and preparations

Specific prerequisites *

No information inserted

Recommended prerequisites

Computational complexity, Probability, Design and analysis of algorithm

Equipment

Personal laptop.

Literature

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). 

Examination and completion

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

Grading scale *

P, F

Examination *

  • 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.

Other requirements for final grade *

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.

Opportunity to complete the requirements via supplementary examination

No information inserted

Opportunity to raise an approved grade via renewed examination

No information inserted

Examiner

Danupon Na Nongkai

Ethical approach *

  • 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.

Further information

Course web

Further information about the course can be found on the Course web at the link below. Information on the Course web will later be moved to this site.

Course web FDD3502

Offered by

EECS/Theoretical Computer Science

Main field of study *

No information inserted

Education cycle *

Third cycle

Add-on studies

No information inserted

Postgraduate course

Postgraduate courses at EECS/Theoretical Computer Science