Given a Boolean function $f: \{-1,1\}^n\rightarrow \{-1,1\}$, define the Fourier distribution to be the distribution on subsets of $[n]$, where each $S\subseteq [n]$ is sampled with probability $\widehat{f}(S)^2$. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [FK96] seeks to relate two fundamental measures associated with the Fourier distribution: does ... more >>>

There are two natural complexity measures associated with DNFs: their size, which is the number of clauses; and their width, which is the maximal number of variables in a clause. It is a folklore result that DNFs of small size can be approximated by DNFs of small width (logarithmic in ... more >>>