Fall 2018

Open Problems in Number-On-Forehead Communication Complexity

Monday, October 15th, 2018 2:30 pm3:00 pm

Add to Calendar


Toni Pitassi (University of Toronto)

In this talk we discuss both new and old connections between classic problems in Number-on-Forehead Communication Complexity and Additive Combinatorics and Ramsey Theory. We also give a new, direct protocol for the Exact-n problem, of determining if the sum of the players inputs is exactly n. This is joint work with Adi Shraibman and Nati Linial.