14
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ @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? $\endgroup$
    – Sasha Kozachinskiy
    Feb 21, 2020 at 9:35
  • 3
    $\begingroup$ 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. $\endgroup$
    – domotorp
    Feb 21, 2020 at 20:47
  • $\begingroup$ That's a great point, thank you! $\endgroup$
    – Sasha Kozachinskiy
    Feb 22, 2020 at 10:47
  • $\begingroup$ I think you should post the answer from your latest update as an actual answer rather than including it in the question. $\endgroup$
    – Emil Jeřábek
    Mar 13, 2020 at 14:35
  • $\begingroup$ Thanks for the suggestion, posted it as an answer $\endgroup$
    – Sasha Kozachinskiy
    Mar 13, 2020 at 14:49

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.