Title: Decision Trees Have Large Influences

Speaker: Ryan O'Donnell,  Microsoft Research

Abstract:  Let f : {0,1}^n -> {0,1} be a boolean function.  The "influence of the ith coordinate on f" is the probability, over a uniformly random input, that flipping the ith input bit makes a difference to f.  This simple concept plays an important role in complexity theory, combinatorics, voting theory, and learning theory. 
A simple result says that if f is "balanced" (equally often 0 or 1), then f must have a variable with influence at least 1/n.  A famous and deep result of Kahn-Kalai-Linial improves this to Omega(log n / n).

In this work we prove a strengthening for functions with low decision tree complexity.  (The decision tree complexity of f, denoted D(f), is the worst-case of input bits that must be adaptively queried to determine f.)  For balanced functions f, we show that there must be a variable with influence at least 1/D(f).

As an application of our work, we show a new lower bound on the randomized decision tree complexity of any nontrivial monotone graph
property: v^{4/3}/p^{1/3}, where v is the number of vertices and p is the critical probability.

This is joint work with Mike Saks (Rutgers), Oded Schramm (Microsoft), and Rocco Servedio (Columbia).