dimacs logo color

Events

Event Calendar

« Previous Month

August 2026

Next Month »
Sun Mon Tue Wed Thu Fri Sat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Seminar Details

Open Problems in NOF Communication Complexity

  • Start Date: February 2, 2022
  • Event Start Time: 11:00 AM
  • Event End Time: 12:00 PM
  • Seminar Series: Theoretical Computer Science Seminar
  • Presenter(s): Joshua Brody - Swarthmore College
  • Event Location: Online Event
  • Event Additional Info: <p>Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar.&nbsp;</p> <p>See:&nbsp;<a href="https://theory.cs.rutgers.edu/theory_seminar" target="_blank">https://theory.cs.rutgers.edu/theory_seminar</a>&nbsp;</p>
  • Presentation Type: Stand Alone Presentation
  • 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.