Commmunication Complexity Aug-Nov 2022

Communication complexity deals with understanding the optimal amount of communication (usually expressed in bits) between two parties when their aim is to jointly determine the output to a computational problem. Lower bounds obtained in communication complexity have proven to be extremely useful in proving lower bounds on resource consumption in other computational models. In this course, we will systematically introduce the concept of communication complexity, prove communication lower bounds for fundamental computational problems and see several applications of these results.

The primary references for the course will be the following textbooks on the subject.

• Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997.
  
• Anup Rao and Amir Yehudayoff. Communication Complexity and Applications.
  
• Tim Roughgarden. Communication Complexity (for Algorithm Designers).
  

Instructors: Prajakta Nimbhorkar and Nithin Varma

Course Schedule

Fundamental Topics (Chapters 1-3 of Kushilevitz and Nisan)


• Aug 3, 2022. Introduction to Yao's two-party communication model; Protocol trees. Lecturer: Prajakta Nimbhorkar
• Aug 5, 2022. Partition number and deterministic communication complexity; Fooling sets. Lecturer: Nithin Varma
• Aug 10, 2022. Log-rank conjecture; Covering number and nondeterministic communication complexity. Lecturer: Nithin Varma
• Aug 12, 2022. Relationship between deterministic and nondeterministic communication complexity, Nondeterministic and Co-nondeterministic communication complexity of k-Disjointness. Lecturer: Nithin Varma
• Aug 17, 2022. Randomized communication protocols, Zero error and bounded error communication, Randomized protocol for Equality. Lecturer: Prajakta Nimbhorkar
• Aug 19, 2022. Public coin and private coin protocols, Public coin protocol for Equality. Lecturer: Prajakta Nimbhorkar
• Aug 24, 2022. Newman's theorem, Public coin protocol for k-Disjointness, Distributional communication complexity. Lecturer: Prajakta Nimbhorkar
• Aug 26, 2022. Yao's minimax lemma, Discrepancy technique for communication lower bound. Lecturer: Prajakta Nimbhorkar


Advanced Topics (Overleaf link for Lecture Notes)
Disclaimer: The lecture notes have not undergone the scrutiny necessary for formal publications.


• Aug 31, 2022. No lecture due to public holiday.
• Sep 2, 2022. Class Cancelled
• Sep 7, 2022. One-way communication complexity, Lower bound of the Index Problem. Lecturer: Nithin Varma
• Sep 9, 2022. Sparse recovery lower bound. Lecturer: Nithin Varma
• Sep 14, 2022. Property testing sortedness, Communication complexity method to prove property testing lower bounds. Lecturer: Nithin Varma
• Sep 16, 2022. Lower bound for testing monotonicity. Lecturer: Nithin Varma
• Sep 21, 2022. Formula depth and communication complexity, Karchmer-Wigderson Games. Lecturer: Prajakta Nimbhorkar
• Sep 23, 2022. Depth lower bound on monotone circuits for matching. Lecturer: Prajakta Nimbhorkar
• Sep 28 & Sep 30, 2022. No lectures due to midterm.
• Oct 5, 2022. Introduction to information theory: entropy, mutual information, properties and examples. Lecturer: Prajakta Nimbhorkar
• Oct 7, 2022. Set disjointness: sqrt(n)log n upper bound for distributional complexity under product distributions. Lecturer: Prajakta Nimbhorkar
• Oct 12, 2022. Set disjointness Omega(n) lower bound. Lecturer: Prajakta Nimbhorkar
• Oct 14, 2022. Hellinger distance and its use in proving the set disjointness Omega(n) lower bound Lecturer: Prajakta Nimbhorkar
• Oct 19, 2022. KL divergence, Pinsker's Inequality. Lecturer: Nithin Varma
• Oct 21, 2022. Information theoretic lower bound for one-way communication complexity of Index. Lecturer: Nithin Varma
• Oct 26, 2022. Lifting theorem Part I. Lecturer: Nithin Varma
• Oct 28, 2022. Lifting theorem Part II. Lecturer: Nithin Varma
• Nov 2, 2022. Lifting theorem Part III. Lecturer: Nithin Varma
• Nov 4, 2022. Lifting theorem Part IV. Lecturer: Nithin Varma
• Nov 9, 2022. Cell probe model, Dictionary problem, FKS Scheme. Lecturer: Nithin Varma
• Nov 11, 2022. Predecessor problem upper bound in the cell probe model. Lecturer: Nithin Varma
• Nov 16, 2022. Predecessor problem lower bound in the randomized cell probe model. Lecturer: Nithin Varma
• Nov 18, 2022. Predecessor problem lower bound in the randomized cell probe model, Round reduction outline. Lecturer: Nithin Varma

Homeworks and Exams

• Homework 1: Exercises 1.30 (for DISJ), 1.31, 2.9, 2.13 from Kushilevitz and Nisan
• Homework 2: Problems 3.15, 3.21, 3.31 from [Kushilevitz, Nisan]
• Extended Homework 2: PDF
• Midterm Exam: PDF
• Endterm Exam: PDF