Commmunication Complexity
Aug-Nov 2022
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
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