Joshua Brody, Swarthmore College

Abstract

Over the past several years, enormous progress has been made in our understanding of communication complexity, including solving several long-standing open problems. One area where many open problems remain is the Number-On-The-Forehead (NOF) communication model. NOF communication lower bounds have a number of applications, including lower bounds for circuit complexity, dynamic data structures, and streaming algorithms. However, progress in understanding NOF communication complexity remains limited.

In this talk, I will give a biased survey of the NOF communication landscape, focusing on open problems and including some potential lines of attack on these problems. No prior knowledge of Number-On-The-Forehead communication complexity is necessary.

Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://theory.cs.rutgers.edu/theory_seminar