Kahn-Kalai-Linial and Kruskal-Katona

Speaker  Ryan O'Donnell

Host  Yuval Peres

Duration  00:52:37

Date recorded  28 May 2010

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.

©2010 Microsoft Corporation. All rights reserved.
> Kahn-Kalai-Linial and Kruskal-Katona