Course Objective

Consider a system which attempts to perform a certain task where the information involved is distributed across different parts of the system. One could view the different parts of the system as players or parties. Hence, the system could be seen as the players communicating with each other to complete the task.

The key here is the amount of communication needed. Communication Complexity attempts to understand the number of bits of communication that is necessary and sufficient to solve problems. The objective of this course is to introduce various techniques and tools for designing and analyzing communication protocols.

Course Contents

Deterministic two party model of communication. Protocols for Median, Equality and Clique-versus-Independent set problems. Protocols - formal definition and tree representation, protocol cost. (3 lectures)

Combinatorial rectangles, partitions and protocols. Balancing a protocol. (2 lectures)

Deterministic communication lower bounds: Rectangle method, Fooling set method and Rank method. (3 lectures)

Rectangle covers. Equivalence of covers and non-deterministic protocols. Determinism versus non-determinism in communication complexity. (8 lectures)

Communication complexity of relations. Circuit depth and Karchmer Wigderson games. Monotone circuit depth lower bound for s-t connectivity via FORK relation. Communication lower bound for FORK. (8 lectures)

Randomized two party model of communication: one-sided and two-sided error model. Public versus private randomness. (5 lectures)

Randomized communication lower bounds: Distributional Complexity, Yao’s min-max theorem for randomized communication. Discrepancy method. Lower bound for set disjointness. (8 lectures)

Combinatorial problems as linear programs. Connection to Monotone rank by Yanakkakis. Polytopes and Extension complexity. (5 lectures)

Learning Outcomes

  1. Understanding how to design and analyze deterministic, non-deterministic and randomized communication protocols for simple Boolean functions.

  2. Being able to show communication cost lower bound in deterministic, non-deterministic and randomized settings of the two party model.

Text Books

  1. Communication Complexity and Applications, Anup Rao, Amir Yehudayoff, Cambridge University Press; 1st edition, 2020, ISBN: 9781108497985

  2. Communication Complexity, Eyal Kushilevitz, Noam Nisan, Cambridge University Press, 1996, ISBN: 9780511574948

  3. Communication Complexity (for Algorithm Designers), Tim Roughgarden, Foundations and Trends in Theoretical Computer Science, Volume 11, No 3-4, NOW Publishers, 2016. ISBN: 9781680831146

References

  1. Lower bounds in Communication Complexity, Troy Lee, Adi Shraibman, Foundations and Trends in Theoretical Computer Science, Volume 3, Issue 4, NOW Publishers, 2007, ISBN: 978-1-60198-258-2

  2. Complexity Lower Bounds using Linear Algebra, Satya Lokam, Foundations and Trends in Theoretical Computer Science, Volume 4, No. 1-2, NOW Publishers, 2009 ISBN: 978-1-60198-242-1.

  3. The Landscape of Communication Complexity Classes, Mika Göös, Toniann Pitassi, and Thomas Watson

Past Offerings

Course Metadata

Item Details
Course Title Communication Complexity
Course Code CS5647
Course Credits 3-0-0-3
Course Category PME
Proposing Faculty Krishnamoorthy Dinesh
Approved on Senate of IIT Palakkad
Course prerequisites Familiarity with linear algebra (MA1011 or MA5001), probability (MA2041 or CS2020A or MA5007) and algorithms (CS2030 or CS5009).
Course status New