What are the limitations to what computers can learn? Do certain mathematical theorems 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 look at two facets of communication complexity. In the first part we study the 'number on the forehead' model of multiparty communication complexity, which has applications in circuit complexity, proof complexity, branching programs, pseudorandom generators, and Ramsey theory. We determine the communication complexity of various functions in this model and discuss the motivation and applications.
In the second part, we study privacy in the context of communication complexity: how much information do the players reveal about their private inputs when following a communication protocol. We discuss and compare different formalizations of privacy. We obtain asymptotically tight bounds for the trade-offs between communication cost and privacy loss of any communication protocol computing the Vickrey auction, which is the canonical example of a truthful auction.
Anil Ada is currently a lecturer in the School of Computer Science, McGill University. He received his B.Sc. (Joint Honors in Mathematics and Computer Science), M.Sc. (Computer Science), and Ph.D. (Computer Science) degrees all from McGill University. His research interests lie in theoretical computer science. In particular, he is interested in understanding the inherent limitations of computers and computation.
Faculty Host: Klaus Sutner