Communication Complexity
Anil Ada , PhD student, McGill

Area: theoretical computer science

Abstract:

What are the limitations to what computers can learn? Do certain mathematical theorems have have short proofs? Can quantum mechanics be exploited to speed up computation? Is every problem whose solution is efficiently verifiable also efficiently solvable (i.e. is P = NP)? At first these may seem like unrelated questions, but at a high level, they are all concerned with understanding which tasks are complex and which tasks are easy. Although the underlying model and the resource of interest can be different in different contexts, there seems to be a unifying theme captured by the concept of "communication complexity". In many seemingly unrelated settings, efficient solutions to problems can be viewed as efficiently solving certain communication tasks. In other words, many hard tasks have an implicit communication bottleneck, and one can prove the hardness of these tasks by studying them in the context of communication complexity.

In this talk we will: 1) formally define the basic communication complexity model, 2) give some concrete examples to demonstrate how it relates to various branches of theoretical computer science, and 3) argue that these connections are extremely fruitful.