Universal circuit for aNC¹ in aNC¹

A universal family of circuits is a family of circuits $\mathcal{U}={\{C_{n,d,m}\}}_{n,d,m\in \mathbb{N}}$ such that $C_{n,d,m}$ takes as input $x\in {\{0,1\}}^n$ and a description $f$ of circuit of depth at most $d$ and size at most m, and outputs f(x).

[Val76] gives a construction where the UC has size $\mathcal{O}(m\log m)$ and depth O(m), which has optimal size (by an information theoretic argument). It also gives a construction where the UC has size $\mathcal{O}(dm\log m)$ and depth O(dlogm). Neither preserves the depth.

[CH85] gives a depth-universal circuit, meaning that the circuit has depth linear in that of the circuits to be simulated. The construction has size O(m3d/logm).

Since I came up with this question when I was thinking about arithmetic NC1, I will write down the concrete construction for ${\mathsf{a}\mathsf{N}\mathsf{C}}^1$ formulae.

Arithmetic circuits

Arithmetic circuits over a ring $R$ are modelled as directed acyclic graphs where there is only one gate with fan-out 0. Types of gates include

• Constant gate, with a value c∈R. Ideally, such constant should be an integer (existing in all rings) so that the circuit is an oracle circuit that can be instantiated in different rings.
• Input gate, with an index i∈[n].
• Fan-in 2 subtraction gate.
• Fan-in 2 multiplication gate.

The exclusion of addition and inclusion of subtraction is for a simpler completeness. The depth of a circuit is 1 plus the length of the longest path in the graph. A formula is a circuit whose graph is a tree. Of course, a circuit of depth $d$ can be expanded into a formula of size at most $2^d-1$ and of the same depth.

I’m interested in universal circuits for and in aNC1. It is well known [BB02] that a polynomial-sized Boolean formula can be rebalanced into a logarithmically deep Boolean circuit. I don’t know whether it is the case for arithmetic formulae.

The construction is not hard to come up with. First I’ll describe the encoding of ${\mathsf{a}\mathsf{N}\mathsf{C}}^1$ formulae (the encoding will be a vector whose entries are ring elements). Then I’ll show a modular construction.

Encoding of ${\mathsf{a}\mathsf{N}\mathsf{C}}^1$ formulae

It is natural that arithmetic formulae have arithmetic encodings. For a $d$-deep $n$-variate arithmetic formula, we first turn it into a perfect binary tree. This is rather straightforward: Pick any constant or input gate above the lowest level, replace it with a subtraction gate whose minuend is the original gate and whose subtrahend is the constant zero. Repeat this process until all constant and input gates are at the lowest level. We then encode the leaves of this tree from the left in $(n+1)$-tuples (c,b1​,b2​,…,bn​), where $c$ is the constant (or zero if it’s an input gate), $b_i$ is the indicator whether this is an input gate for xi​. Then we encode the other nodes bottom-up left-to-right, each of which is encoded as a 2-tuple (s,m), where $s$ indicates whether this gate is subtraction and $m$ indicates whether this gate is multiplication.

UC for ${\mathsf{a}\mathsf{N}\mathsf{C}}^1$ in ${\mathsf{a}\mathsf{N}\mathsf{C}}^1$

This encoding is super convenient to use. For a circuit universal up to depth d, we first lay out the simulation for $2^{d-1}$ input or constant gates (leaves). This is straightforward — we compute c+b1​x1​+b2​x2​+⋯+bn​xn​, which by our encoding, will be the actual value in the original circuit. Note that fan-in $n+1$ addition can be simulated using fan-in 2 additions of depth $\mathcal{O}(\log n)$ with balanced grouping, and that addition can be simulated using subtraction by a+b=a−(0−b).

Now we lay out the intermediate gates, which are either subtraction or multiplication. Easy, we just do both and choose the required one using the encoding, i.e., $x-y=1\cdot (x-y)+0\cdot xy$ and xy=0⋅(x−y)+1⋅xy. Note that we must duplicate the incoming gates. But that’s no problem as the depth doesn’t grow too much.

The construction gives us a universal circuit for depth $d$ of depth O(d+logn). The $\log n$ doesn’t kill us, as in the formula model, to touch all the input variables, you need d=Ω(logn). Note that the concrete depth can be optimised by choosing a better encoding, i.e., use $-1$ for certain indicators so that we can effectively and efficiently perform addition with the good choice of coefficient and subtraction.

References

↩[Val76] Leslie G. Valiant. 1976. Universal circuits (Preliminary Report). In Proceedings of the eighth annual ACM symposium on Theory of computing (STOC '76). ACM, New York, NY, USA, 196-203. DOI=http://dx.doi.org/10.1145/800113.803649

↩[CH85] Stephen A. Cook and H. James Hoover. A depth-universal circuit. SIAM J. Comput., 14(4), 833–839. (7 pages) DOI=https://doi.org/10.1137/0214058

↩[BB02] Maria Luisa Bonet and Samuel R. Buss. Size-depth tradeoffs for Boolean formulae. Information Processing Letters, 11 (1994) 151-155. DOI=https://doi.org/10.1016/0020-0190(94)90093-0