Computational Complexity Theory: Randomness and Communication

Dr. Thomas Watson
University of Toronto


Abstract

In this talk I will give an overview of my research in the field of computational complexity, which is the branch of theoretical computer science studying the inherent power and limitations of efficient computation. My work can be roughly grouped into two strands: randomness as a resource, and communication as a resource. Topics concerning randomness include how to harness limited or imperfect sources of randomness for use in randomized algorithms, and how to quantify the complexity of problems that involve randomness in their definitions. My work on communication complexity is about proving lower bounds on the amount of communication needed to solve problems when the input is distributed across multiple parties; my papers have resolved some of the oldest open problems in this area by exploiting deep connections with another area known as query complexity.