Kahn-Kalai-Linial and Kruskal-Katona

The notable KKL Theorem of Kahn, Kalai, and Linial says that if f : 0,1n – 0,1 is a balanced boolean function, then there is at least one coordinate i with “influence” at least Omega(log n / n).
We generalize this result to boolean functions on Cayley and Schreier graphs, whenever the generating set is a union of conjugacy classes and the associated Markov chain has a good log-Sobolev constant. E.g., we show that if f is a balanced Boolean function on the set of n-bit strings with Hamming weight n/2, then there exists some pair of indices i, j such that the influence on f of swapping the ith and jth coordinates is at least Omega(log n / n). As an application we prove a new “robustification” of the classical Kruskal-Katona Theorem from combinatorics. We also discuss an application in computational learning theory. This talk is based on two joint works with Karl Wimmer of Duquesne University.

Speaker Details

Ryan O’Donnell received his PhD from MIT in 2003. He then spent a year as a postdoc at the IAS and 2 years as a postdoc in the Theory group at MSR before joining the faculty in CMU. He is well known for diverse and imaginative applications of discrete Fourier analysis to algorithms, learning and complexity (among other contributions).

Date:
Speakers:
Ryan O'Donnell

    • Portrait of Jeff Running

      Jeff Running