Given a DNF formula $f$ on $n$ variables, the two natural size measures are the number of terms or size $s(f)$, and the maximum width of a term $w(f)$. It is folklore that short DNF formulas can be made narrow. We prove a converse, showing that narrow formulas can be ... more >>>

Nisan and Szegedy showed that low degree Boolean functions are juntas. Kindler and Safra showed that low degree functions which are *almost* Boolean are close to juntas. Their result holds with respect to $\mu_p$ for every *constant* $p$. When $p$ is allowed to be very small, new phenomena emerge. ... more >>>

We give alternate proofs for three related results in analysis of Boolean functions, namely the KKL
Theorem, Friedgut’s Junta Theorem, and Talagrand’s strengthening of the KKL Theorem. We follow a
new approach: looking at the first Fourier level of the function after a suitable random restriction and
applying the Log-Sobolev ... more >>>