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 CliqueversusIndependent 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 nondeterministic protocols. Determinism versus nondeterminism in communication complexity. (8 lectures)
Communication complexity of relations. Circuit depth and Karchmer Wigderson games. Monotone circuit depth lower bound for st connectivity via FORK relation. Communication lower bound for FORK. (8 lectures)
Randomized two party model of communication: onesided and twosided error model. Public versus private randomness. (5 lectures)
Randomized communication lower bounds: Distributional Complexity, Yaoâ€™s minmax 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

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

Being able to show communication cost lower bound in deterministic, nondeterministic and randomized settings of the two party model.
Text Books

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

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

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

Lower bounds in Communication Complexity, Troy Lee, Adi Shraibman, Foundations and Trends in Theoretical Computer Science, Volume 3, Issue 4, NOW Publishers, 2007, ISBN: 9781601982582

Complexity Lower Bounds using Linear Algebra, Satya Lokam, Foundations and Trends in Theoretical Computer Science, Volume 4, No. 12, NOW Publishers, 2009 ISBN: 9781601982421.

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  3003 
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 