***********************************
                * Princeton Discrete Math Seminar *
                ***********************************


Date: Thursday 31st March, 3:00 in Fine Hall 224.
 
Speaker: Avi Wigderson (IAS)

Title: The sensitivity conjecture: background and new results

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

                       -----------

Next week: Hehui Wu

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)