The sensitivity conjecture: background and new results

-
Avi Wigderson , IAS
Fine Hall 224

What are smooth Boolean functions, and how simple are they? One measure of smoothness is the sensitivity of the function to local changes.  Let the graph G(f) of a  Boolean function f on the n-dimensional cube be the (bipartite) subgraph of the cube graph containing only edges with different f-values. The sensitivity of f, denoted s(f), is simply the maximum vertex degree of G(f). When s(f) is small compared to the number n of variables, it means that  for every vertex x, flipping the bit in one coordinate will change the value of f only for very few coordinates. The basic high level question under study is what structure is implied by this smoothness? One measure of simplicity of a Boolean function is its Fourier degree. More precisely, let deg(f) be the degree of the unique real multilinear  polynomial which equals f on every vertex of the cube.  This measure of simplicity is extremely robust, in that remarkably many other parameters of Boolean functions are polynomially related to deg(f). These include the computational complexity of f in the deterministic, probabilistic, quantum and non-deterministic decision tree models. The sensitivity conjecture,  formulated by Noam Nisan and Mario Szegedy in the 1990s, asserts that smooth functions are simple:  deg(f) < (s(f))^c,  for some fixed constant c independent of n and f. It has been wide open since. I will survey some of what is known about the conjecture, and some new results. In particular I plan to prove a sharp bound on the approximate degree of f in the L_2 norm (more precisely, an exponential decay of the Fourier mass above degree s(f)). This will require the introduction of new combinatorial parameters of the graph G(f) as well as random restrictions and switching lemmas typically used in circuit complexity. No special background will be assumed. Based on several joint works with  Parikshit Gopalan, Noam Nisan, Rocco Servedio, Avishay Tal and Kunal Talwar.