Rectangles, Complexity and Games in Communication Theory - December 4, 2023

Explore a detailed lecture on computational complexity theory that delves into the relationship between internal and external communication complexity through the lens of combinatorial rectangles and game theory. Learn about the fundamental inequality in communication complexity and its reformulation using mutual information I(c:y:π), where x and y represent random inputs for communication tasks and π denotes the transcript. Examine Romashchenko's generalization, which demonstrates that the inequality holds when π(x,y) is a function with combinatorial rectangle preimages. Discover how this concept extends to a complexity version involving combinatorial rectangles that are simple with respect to their points, leading to the inequality I(Pi:x:y)≥0. Investigate the translation of these theoretical concepts into practical applications through game theory, with particular focus on winning strategy existence in specific game scenarios.