DIMACS - Graduate Student Combinatorics Seminar

Title: A new approach to the sensitivity conjecture

Speaker: Justin Gilmer, Rutgers University

Date: Wednesday, December 3, 2014 12:10pm

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


We'll discuss a new two-player communication game for which a strong enough lower bound on the cost of this game would imply the famous sensitivity conjecture. We'll then prove such a lower bound for a restricted variant of the game. Some new open questions as a result of this work will be discussed, some of which may turn out to be "low hanging fruit". No prior knowledge will be assumed for this talk. Joint work with Michael Saks.