Aarhus University Seal

On Friday 5 October Joshua Brody will give a Computer Science Friday Lecture

Computer Science Friday Lectures are a series of talks aiming for a broad computer science audience, including student and scientific staff. This is an opportunity to hear about, for example, new research projects or overviews of research areas, presented by our own local experts. Participation is for free, there is no registration and everybody are welcome. Talks will be in English unless stated otherwise.

Communication Complexity, and Lower Bounds in Computer Science

Time: Friday 5 October at 14:15-15:00 (Coffee and cake at 14:00 - the talk begins at 14:15)
Place: Peter Bøgh Andersen Auditorium, Nygaard Building, Åbogade 34

One of the central questions we ask as computer scientists is the following: Given a computational problem, how much resources are required to compute it?

Providing an algorithm for a problem and analyzing its efficiency amounts to proving an _upper bound_ on the resources required. However, how do you show that a large amount of resources are required? Proving such _lower bounds_ in computer science is a notoriously difficult task, 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 become one of the central tools in proving lower bounds. I will briefly introduce the basic concepts in communication complexity, as well as a few of the techniques used to prove communication lower bounds.

The bulk of this talk will tour the recent history of lower bounds in computer science. I'll present computational problems from a wide range of areas, including VLSI circuit design, data structures, and streaming algorithms. In each case, I'll present a sample computational task and provide a lower bound for it, using communication complexity.

No prior knowledge is required, and questions during the talk are encouraged.

About Joshua Brody

Se the Friday Lecture webpage for upcoming lectures