This talk is part of the Advances in Boolean Function Analysis Lecture Series. The series will feature weekly two-hour lectures that aim to address both the broad context of the result and the technical details. Though closely related in theme, each lecture will be self-contained. Join us weekly at 10:00 a.m. PDT, from July 15, 2020 to August 18, 2020. There is a five minute break at the end of the first hour.
Abstract:
Many complexity measures of Boolean functions have been well studied in theoretical computer science. These include sensitivity, block sensitivity, degree, approximate degree, certificate complexity, decision-tree complexity, among many others. It has been long known that almost all these measures are polynomially related to each other, yet whether sensitivity belongs to the same class (a.k.a. the Sensitivity Conjecture of Nisan and Szegedy) has remained a mystery for almost three decades until last July.
In this talk, we will explain some background, walk through a linear algebraic proof of the Sensitivity Conjecture based on the Gotsman-Linial reduction to an extremal combinatorial problem on discrete cubes, and discuss the remaining challenges.
All scheduled dates:
Upcoming
No Upcoming activities yet