Swarthmore College Department of Computer Science

Talk by Joshua Brody, Aarhus University

Communication Complexity and Lower Bounds in Computer Science
Fri, Feb 8, 2013
SCI 240, 4:30 pm (cookies at 4:15)

Abstract

One of the central questions we ask as computer scientists is the following: How efficiently can we solve computational tasks? Designing and analyzing an algorithm for a problem amounts to giving an upper bound; i.e., it shows that a limited amount of resources suffice for this task. However, how do you show that a large amount of resources are required? Proving such lower bounds in computer science is notoriously difficult, because lower bounds cannot rely on particular characteristics of an algorithm. They must hold no matter how a computational problem is solved.

In this talk, I will introduce the field of communication complexity. Over the past 30 years, communication complexity has emerged as one of the central tools in proving lower bounds. I will briefly introduce basic concepts in communication complexity, as well as a few of the techniques used to prove communication lower bounds. In the main part of the talk I will present some recent applications where communication complexity has proven particularly powerful. Finally, I'll conclude the talk with a road map on where I see communication complexity heading and some interesting topics for future research.