Loading Events

« All Events

  • This event has passed.

Richard M. Karp Distinguished Lecture: Structure of Communication

Richard M. Karp Distinguished Lecture

Shachar Lovett (UC San Diego) 


July 27, 2023 @ 3:30 pm 4:30 pm

Simons Institute for the Theory of Computing
Calvin Lab auditorium and livestream

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. The series features visionary leaders in the field of theoretical computer science, and is geared toward a broad scientific audience.

Further event details are available here

Light refreshments will be available prior to the start of the lecture.