Number-on-the-Forehead Communication Complexity

 Since the Winter 2020 semester at McGill, I've helped run a Communication Complexity reading group attended by undergraduate and graduate students. Recently, I became particularly excited by the Number-on-the-Forehead model, and gave a talk on it in the reading group. 

The idea is quite simple. For 2 player communication, imagine that Alice's input is on top of Bob's forehead, making it easy for Alice to see but impossible for Bob to see. Likewise, Bob's input is on Alice's forehead. 

This generalizes to k-player problems where k people stand in a circle, each with a card on their forehead indicating some information that is viewable to everyone but the forehead owner. 

If this still doesn't make sense, think of this scene from The Office. 

Here are the lecture notes I wrote for the talk. I cover basic definitions, Behrend's bound and it's application to the Exactly-N problem, and Ramsey Theoretic lower bounds on cylinders.

 As I liked this topic so much, I'll be additionally posting a recorded lecture. I'm still in the process of editing the video, so this post will be updated soon. 

Comments

Popular posts from this blog

Extension Complexity Part II - Classifying Nonnegative Rank by Randomized Communication

Derandomization of BPP Using Hitting Set Generators