KKL, Kruskal-Katona, and monotone nets
Speaker: Ryan O , Carnegie Mellon University
Date: May 5 2009
Time: 11:00AM to 12:00PM
Location: NOTE: 32-D463 STAR
Host: Scott Aaronson, CSAIL, MIT
Contact: be, 3-6098, imbe@mit.edu
Relevant URL: The notable KKL Theorem of Kahn, Kalai, and Linial says that if f : {0,1}^n -> {0,1} is any roughly balanced boolean function, then there is at least one coordinate i with "influence" at least Omega(log n / n).
We show how to generalize this to boolean functions on certain Cayley graphs; in particular, to certain non-product distributions. E.g., we show that if f is a 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).
A consequence of this is a "robustification" of the classical Kruskal-Katona Theorem of combinatorics. A further consequence is that every monotone function has correlation Omega(log n / sqrt{n}) with one of the n+3 functions 0, 1, x_1, ..., x_n, Majority. This closes an open learning-theory problem of Blum, Burch, and Langford.
Joint work with Karl Wimmer of CMU.
See other events that are part of Theory Colloquium 2008/2009
See other events happening in May 2009
