## 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: