Random Restrictions and Fourier Concentration 2
summary
Correlation inequality uses hypercontractivity (L4 bound ~3^d) to bound E[f g] for Boolean f and degree-d real g and deduces KKL and Friedgut-style conclusions: min-entropy ≤ (total influence)^2 and a lower bound on the largest Fourier weight of roughly exp(−O(total influence)). Iterated random restrictions reduce degree to v and yield exp(O(v)) factors, letting the recursion reach the I log I regime. Decision trees satisfy L1 of Fourier coefficients ≤ decision-tree size, giving concentration: at most 1/μ^2 coefficients above μ and ε-approximation by O(size/ε) characters.
AI-written summary · about