DIMACS - Graduate Student Combinatorics Seminar

Title: What We Have Here is a Failure to Communicate: A Communication Game and Applications to the Sensitivity Conjecture

Speaker: John Chiarelli, Rutgers University

Date: Wednesday, November 29, 2017 12:10pm

Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ


The sensitivity conjecture is one of the core unresolved questions of computational complexity. In this talk, I will look at one angle that has been taken in tackling this problem, via a cooperative two-player game based on communication. I will also talk about conjectures made in that direction that ultimately failed due to particular counterexamples.

See: http://www.math.rutgers.edu/~yb165/GCS.html