Theory Lunch This Thursday (5/1, 12:00 PM, GCS 502c)

[Grayson York]

Hi all,

Please join us for the last theory lunch of the year and my tenure as Tsar on Thursday 5/1 at 12:00 PM in GCS 502c. This week Guangxu will be presenting some exciting new results in communication complexity. The title and abstract for the talk are as follows.

Thanks,

G

Title: Deterministic Lifting Theorems for One-Way
Number-on-Forehead Communication

Abstract: We initiate the study of lifting results from the Number-in-Hand (NIH) model to the Numbers-on-Forehead (NOF) model. In particular, we prove the first deterministic lifting theorem from one-way communication complexity to one-way NOF communication complexity.

As a main application, we construct an explicit k-player function f : [N]^k to {0,1} that exhibits an optimal separation between randomized and deterministic one-way NOF communication. Specifically, the deterministic complexity of f is log N, while its randomized complexity is only O(1). This significantly improves over the previous best-known separation of log^{1/3} N versus O(1) for three players, due to Kelley, Lovett, and Meka (STOC 2024)