KKL, Kruskal--Katona, and Monotone Nets
Authors:
- Ryan O'DOnnellRORyan O'DOnnell
- Karl WimmerKWKarl Wimmer
- 1 January 2013
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 42 (6) , 2375-2399
Abstract
We generalize the Kahn--Kalai--Linial (KKL) theorem to random walks on Cayley and Schreier graphs, making progress on an open problem of Hoory, Linial, and Wigderson. In our generalization, the underlying group need not be abelian so long as the generating set is a union of conjugacy classes. An example corollary is that for every $f : \binom{[n]}{k} \to \{0,1\}$ with ${\bf E}[f]$ and $k/n$ bounded away from $0$ and $1$, there is a pair $1 \leq i < j \leq n$ such that ${\cal I}_{ij}(f) \geq \Omega(\frac{\log n}{n})$. Here ${\cal I}_{ij}(f)$ denotes the “influence” on $f$ of swapping the $i$th and $j$th coordinates. Using this corollary we obtain a “robust” version of the Kruskal--Katona theorem: Given a constant-density subset $A$ of a middle slice of the Hamming $n$-cube, the density of $\partial A$ is greater by at least $\Omega(\frac{\log n}{n})$, unless $A$ is noticeably correlated with a single coordinate. As an application of these results, we show that the set of functions $\{0, 1, x_1, \dots, x_n, \mathrm{Maj}\}$ is a $(1/2 - \gamma)$-net for the set of all $n$-bit monotone Boolean functions, where $\gamma = \Omega(\frac{\log n}{\sqrt{n}})$. This distance is optimal for polynomial-size nets and gives an optimal weak-learning algorithm for monotone functions under the uniform distribution, solving a problem of Blum, Burch, and Langford.
Keywords
This publication has 29 references indexed in Scilit:
- On learning monotone Boolean functions under the uniform distributionTheoretical Computer Science, 2006
- On the hardness of approximating vertex coverAnnals of Mathematics, 2005
- On the log-Sobolev constant for the simple random walk on the n-cycle: the even casesJournal of Functional Analysis, 2003
- Noise sensitivity of boolean functions and applications to percolationPublications mathématiques de l'IHÉS, 1999
- Logarithmic Sobolev inequalities for finite Markov chainsThe Annals of Applied Probability, 1996
- On the Fourier spectrum of monotone functionsJournal of the ACM, 1996
- The influence of variables in product spacesIsrael Journal of Mathematics, 1992
- Threshold functionsCombinatorica, 1987
- Time to Reach Stationarity in the Bernoulli–Laplace Diffusion ModelSIAM Journal on Mathematical Analysis, 1987
- Generating a random permutation with random transpositionsProbability Theory and Related Fields, 1981