Seminars & Colloquia Calendar
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
|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.