## Size of universal swtching networks and formulas

Recall that a switching network is an undirected graph $G$ with two
distiguished nodes $s$ (source) and $t$ (target). Some of wires are labeled by
literals (a variable $x_i$ or its negation $\neg x_i$).
The size is the total number
of wires. Given an input $a\in\{0,1\}^n$, the network outputs $1$ if and only if
there is an $s$-$t$ path, along which all literals are consistents
with $a$ (i.e., output $1$ on $a$); unlabeled wires are consistent with
all inputs.
A network $G$ is $n$-*universal* if, for every boolean function
$f(x_1,\ldots,x_n)$, it is possible to remove some wires from $G$ and remove the
labelings of some of the remaining wires so that the resulting
switching network computes $f$.
Let $U(n)$ denote the smallest size of an $n$-universal switching network.

E.V. Sherisheva (1967) proved the following tight estimate:
\[
U(n) \sim c 2^n
\]
for a constant $1/\log_2 3\leq c\leq 1$.

She then considered universal $AC^0$ formulas. Such a formula is $n$-*universal* if, for every boolean function
$f(x_1,\ldots,x_n)$, it is possible to assign constants $0/1$ to some its
input so that the resulting formula computes $f$.
Let $F_d(n)$ denote the smallest leaf-size of an $n$-universal $AC^0$ formula
of depth $\leq d$. Let also $F(n)$ denote the smallest leaf-size
of an $n$-universal $AC^0$ formula. She proved that
\begin{eqnarray*}
F_2(n)&=&2^{n-1}\cdot (n+1),\\
F_3(n)&\leq & 2^{n-1}\cdot \log_2 n,\\
F(n) &\sim& 2^n.
\end{eqnarray*}
**Reference:**

*
*