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 >>>