KKL, Kruskal--Katona, and Monotone Nets

DOI10.1137/100787325zbMath1285.68075OpenAlexW2092614531MaRDI QIDQ5408770

Karl Wimmer, Ryan O'Donnell

Publication date: 11 April 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/100787325

zbMATH Keywords

computational learning theoryBoolean functionsmonotone functionsKruskal-Katona theoremSchreier graphsKKLlog Sobolev constant

Mathematics Subject Classification ID

Computational learning theory (68Q32) Combinatorial inequalities (05A20) Classical measure theory (28A99) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (14)

Log-Sobolev inequality for the multislice, with applications ⋮ Biased halfspaces, noise sensitivity, and local Chernoff inequalities ⋮ Boolean degree 1 functions on some classical association schemes ⋮ An orthogonal basis for functions over a slice of the Boolean hypercube ⋮ Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions ⋮ Hypercontractivity on the symmetric group ⋮ Unnamed Item ⋮ A structure theorem for almost low-degree functions on the slice ⋮ On Quantitative Noise Stability and Influences for Discrete and Continuous Models ⋮ Diversity ⋮ Query complexity of Boolean functions on the middle slice of the cube ⋮ Unnamed Item ⋮ Boolean function analysis on high-dimensional expanders ⋮ Functional \(L_1\)-\(L_p\) inequalities in the CAR algebra

This page was built for publication: KKL, Kruskal--Katona, and Monotone Nets