Calendar
What We Have Here is a Failure to Communicate: A Communication Game and Applications to the Sensitivity Conjecture
John Chiarelli, Rutgers University
Location: Hill GSL
Date & time: Wednesday, 29 November 2017 at 12:10PM - 1:10PM
Abstract: 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.