# 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$$.

• @domotorp, I allow negations in leafs. In other words, I can choose for every leaf to put either a variable or its negation there. So it least we can compute any function by a sceleton' ' of a complete DNF of size $n 2^n$, right? – Sasha Kozachinskiy Feb 21 at 9:35
• Using [1]+[2] for an $O(2^n)$ seems like an overkill. You can just prove by induction that $2^{n+1}-3$ is enough: Compute $f$ restricted to $x_n=0$ and $x_n=1$, respectively, then take the AND of their outputs with the literals $x_n$ false and $x_n$ true, respectively, and finally the OR of these two branches. – domotorp Feb 21 at 20:47
• That's a great point, thank you! – Sasha Kozachinskiy Feb 22 at 10:47
• I think you should post the answer from your latest update as an actual answer rather than including it in the question. – Emil Jeřábek Mar 13 at 14:35
• Thanks for the suggestion, posted it as an answer – Sasha Kozachinskiy Mar 13 at 14:49

A $$O(2^n/\log n)$$-size depth-3 universal Boolean formula was constructed in