Download as iCal file

Graduate Pizza Seminar

The Sensitivity Conjecture: Twenty Seven Years and Five Pages

John Chiarelli (Rutgers University)

Location:  GSL, Hill 701
Date & time: Friday, 13 September 2019 at 1:40PM - 2:40PM

Abstract: The Sensitivity Conjecture is one of the most central and historically important in the field of computational complexity. Proposed by Nisan and Szegedy in 1992, mathematicians have attempted to prove or disprove the conjecture for decades - which makes it particularly impressive that a recent paper by Hao Huang answers it in a five-page paper. In this seminar, I will talk about why the Sensitivity Conjecture is so important, and give an overview of the techniques used to solve it.