Structure of Communication | Richard M. Karp Distinguished Lecture

Communication complexity is a theoretical framework used to analyze the amount of communication required for solving computational problems in a distributed setting. It measures the amount of communication that needs to be exchanged between multiple parties in order to accomplish a particular task or computation.



Since its introduction in the early 1980s, some of the great success stories of communication complexity have been determining the communication needed to solve important concrete problems that have arisen in applications. These, in turn, have been used to prove sharp lower bounds in a host of application domains, such as approximation algorithms, data structures, and streaming algorithms.



We have made much less progress, however, in understanding the structures underlying efficient communication for general communication problems. The most famous open problem in this area, the log-rank conjecture, speculates a tight connection between communication in the simplest setting, that of two players and deterministic protocols, with the rank of associated matrices. There are also structural conjectures that attempt to capture the structure underlying randomized protocols, or protocols with more than two players. These structural conjectures in turn have tight connections to structural conjectures in other areas of mathematics, such as in combinatorics, discrete geometry, algebra, and additive combinatorics.



In this talk, Shachar Lovett will focus on the structural conjectures that underlie efficient communication in a number of settings, how they are connected to structural conjectures in mathematics more broadly, and what progress has been achieved so far.

 

Shachar Lovett is an associate professor at UC San Diego. He has a broad interest in theoretical computer science and mathematics, with a focus on computational complexity, randomness and pseudorandomness, algebraic constructions, coding theory, additive combinatorics and high-dimensional geometry. He is the recipient of an NSF CAREER award, a Sloan Fellowship and a Simons Investigator award.

===================================================================

The Richard M. Karp Distinguished Lectures were created in Fall 2019 to celebrate the role of Simons Institute Founding Director Dick Karp in establishing the field of theoretical computer science, formulating its central problems, and contributing stunning results in the areas of computational complexity and algorithms. Formerly known as the Simons Institute Open Lectures, the series features visionary leaders in the field of theoretical computer science, and is geared toward a broad scientific audience.

Light refreshments will be available prior to the start of the lecture. This lecture will be viewable thereafter on this page and on our YouTube channel.

The Simons Institute regularly captures photos and video of activity around the Institute for use in publications and promotional materials. 

If you require special accommodation, please contact our access coordinator at simonsevents@berkeley.edu with as much advance notice as possible.