<p>A <span class="math-container">$O(2^n/\log n)$</span>-size depth-3 universal Boolean formula was constructed in </p>

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

<p>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).</p>

CC BY-SA 4.0
2020-03-13T14:48:42.280Z
2020-03-31T08:48:52.550Z
2020-03-31T08:48:52.550Z
Sasha Kozachinskiy
<p>Fix <span class="math-container">$n\in\mathbb{N}$</span>. Consider a rooted binary tree <span class="math-container">$T$</span> in which every non-leaf node contains either AND-gate or OR-gate. Let me say that <span class="math-container">$T$</span> is an <em>universal formula</em> if for every <span class="math-container">$f\colon\{0,1\}^n\to\{0, 1\}$</span> we can assign literals to the leafs of <span class="math-container">$T$</span> in such a way that the resulting formula computes <span class="math-container">$f$</span>. </p>

<blockquote>
  <p>What is the minimal size of universal formula?</p>
</blockquote>

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

<p>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 <span class="math-container">$f$</span> it is possible to assign gates to non-leaf nodes in such a way that the resulting formula computes <span class="math-container">$f$</span>. There is an obvious lower bound <span class="math-container">$\Omega(2^n)$</span> (as there are now 2 choices for every node) and [3] constructs a matching <span class="math-container">$O(2^n)$</span> upper bound.</p>

<p>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.</p>

<p><strong>References</strong></p>

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

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

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

<p><strong>Update</strong></p>

<p>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 <span class="math-container">$F$</span> of size <span class="math-container">$O(2^n)$</span> such that for any <span class="math-container">$f\colon\{0, 1\}^n \to \{0, 1\}$</span> we can change in some leafs of <span class="math-container">$F$</span> the corresonding literals to opposite ones so that the resulting <span class="math-container">$F^\prime$</span> computes <span class="math-container">$f$</span>.</p>

CC BY-SA 4.0
2020-02-21T09:35:36.437Z
@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
CC BY-SA 4.0
2020-02-21T20:47:22.000Z
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
CC BY-SA 4.0
2020-02-22T10:47:31.473Z
That's a great point, thank you!
Sasha Kozachinskiy
CC BY-SA 4.0
2020-03-13T14:35:27.880Z
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
CC BY-SA 4.0
2020-03-13T14:49:45.097Z
Thanks for the suggestion, posted it as an answer
Sasha Kozachinskiy
<circuit-complexity><universal-computation><boolean-formulas>
Universal Boolean Formulas
Sasha Kozachinskiy
# Universal Boolean Formulas

(Asked by: username_0 on 2020-02-20)

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

**Tags:** circuit-complexity, universal-computation, boolean-formulas
> **Comments:**
> **username_0**: @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?  
> **username_1**: 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.  
> **username_0**: That's a great point, thank you!  
> **username_2**: I think you should post the answer from your latest update as an actual answer rather than including it in the question.  
> **username_0**: Thanks for the suggestion, posted it as an answer  

---

## 1 answers

### Answer by username_0 on 2020-03-13. Score: 2 | Accepted answer

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


---

