Kahn-Kalai-Linial and Kruskal-Katona

Опубликовано 17 августа 2016, 21:20

The notable KKL Theorem of Kahn, Kalai, and Linial says that if f : {0,1}^n - {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.