Universal Boolean Formulas Fix $n\in\mathbb{N}$. Consider a rooted binary tree $T$ in which every non-leaf node contains either AND-gate or OR-gate. Let me say that $T$ is an universal formula if for every $f\colon\{0,1\}^n\to\{0, 1\}$ we can assign literals to the leafs of $T$ in such a way that the resulting formula computes $f$. 


  What is the minimal size of universal formula?


There is an obvious lower bound $\Omega\left(\frac{2^n}{\log(n)}\right)$ as a tree of size $L$ can compute at most $(2n)^L = 2^{L \cdot \log_2(2n)}$ different Boolean functions. On the other hand, as far as I can see, there is an upper bound $O(2^n)$. Namely, one can take $(n+2)$-bit communication protocol for the universal relation from [1] and transform it into an universal formula via Karchmer-Wigderson correspondence [2].

One more related work is [3], where a different notion of universality is considered. Instead of fixing gates we fix literals and we want that for any $f$ it is possible to assign gates to non-leaf nodes in such a way that the resulting formula computes $f$. There is an obvious lower bound $\Omega(2^n)$ (as there are now 2 choices for every node) and [3] constructs a matching $O(2^n)$ upper bound.

In [1] it is also stated that their protocol improves and simplifies the result of [3]. I don't see why. An explanation would be greatly appreciated.

References

[1] G. Tardos, U. Zwick. The communication complexity of universal relation. Proc. 12th Computational Complexity Conference, pp. 247-259 (1997).

[2] M. Karchmer, A. Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics, 3(2), pp. 255-265 (1990).

[3] W.F. McColl, M.S. Paterson. The depth of all Boolean functions. SIAM Journal on Computing, 6(2), pp. 373-380 (1977).

Update

Some clarifications: actually in [3] all possible bivariate gates are allowed, not only AND, OR gates. Then it becomes clear why [1] implies [3]. Moreover, it seems that [1] gives a stronger object. Namely, one can get from it a DeMorgan formula $F$ of size $O(2^n)$ such that for any $f\colon\{0, 1\}^n \to \{0, 1\}$ we can change in some leafs of $F$ the corresonding literals to opposite ones so that the resulting $F^\prime$ computes $f$.
A $O(2^n/\log n)$-size depth-3 universal Boolean formula was constructed in 


  O.B. Lupanov. Complexity of the universal parallel-series network of
  depth 3. Trudy Matem. Inst. Steklov, 133:127-131, 1973 (In Russian)


In this paper Lupanov uses language of parallel-series networks, which is equivalent to De Morgan formulas with unbounded fan-in AND, OR gates (parallel connection of two networks corresponds to disjunction and series connection corresponds to conjuction).