Prove that $\lambda(f) = o(2^n)$ for almost all boolean functions

Question

How to prove that $\lambda(f) = o(2^n)$ for almost all boolean functions $f$ of $n$ variables?

Here $\lambda(f)$ denotes minimal length (i.e. count of terms) of all possible disjunctive normal forms (DNFs) of $f$.

Answer 1

This is the Korshunov–Kuznetsov Theorem. Quoting [1] which restates the theorem:

Theorem. (Korshunov–Kuznetsov, 1983) The optimal DNF size for a random Boolean function is $(K + o(1))\frac{2n}{\log n \log\log n}$, where $1\leq K\leq 1.54169$ (and the $\log$ is in base $2$)

They refer to the article of Pippenger [2], which (re)proves the lower bound, and improves the constant of the upper bound (which is the quantity you are interested in). From the abstract of [2]:

Our main result is a new upper bound $l(n) \leq (1 + o(1)) H(n) \frac{2n}{\log n \log \log n}$, where $H(n)$ is a function that oscillates between 1.38826... and 1.54169.... The best previous upper bound, due to Korshunov, had a similar form, but with a function oscillating between 1.581411... and 2.621132 .... The main ideas in our new bound are (1) the use of Rödl's "nibble" technique for solving packing and covering problems, (2) the use of correlation inequalities due to Harris and Janson to bound the effects of weakly dependent random variables, and (3) the solution of an optimization problem that determines the sizes of "nibbles" and larger "bites" to be taken at various stages of the construction.

[1] Approximating Boolean functions with depth-2 circuits. Eric Blais and Li-Yang Tan, CCC'13. http://eccc.hpi-web.de/report/2013/051/

[2] The shortest disjunctive normal form of a random Boolean function, Nicholas Pippenger. Random Structures & Algorithms, 22: 161–186, 20003. http://dl.acm.org/citation.cfm?id=770315