Universal circuit for aNC¹ in aNC¹

A universal family of circuits is a family of circuits such that takes as input and a description of circuit of depth at most and size at most and outputs

[Val76] gives a construction where the UC has size and depth which has optimal size (by an information theoretic argument). It also gives a construction where the UC has size and depth 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

Since I came up with this question when I was thinking about arithmetic I will write down the concrete construction for formulae.

Arithmetic circuits

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

  • Constant gate, with a value 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
  • 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 can be expanded into a formula of size at most and of the same depth.

I’m interested in universal circuits for and in 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 formulae (the encoding will be a vector whose entries are ring elements). Then I’ll show a modular construction.

Encoding of formulae

How to push gates downHow to push gates downHow to push gates downHow to push gates downHow to push gates down
How to push gates down

It is natural that arithmetic formulae have arithmetic encodings. For a -deep -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 -tuples where is the constant (or zero if it’s an input gate), is the indicator whether this is an input gate for Then we encode the other nodes bottom-up left-to-right, each of which is encoded as a 2-tuple where indicates whether this gate is subtraction and indicates whether this gate is multiplication.

UC for in

This encoding is super convenient to use. For a circuit universal up to depth we first lay out the simulation for input or constant gates (leaves). This is straighforward — we compute which by our encoding, will be the actual value in the original circuit. Note that fan-in addition can be simulated using fan-in 2 additions of depth with balanced grouping, and that addition can be simulated using subtraction by

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., and 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 of depth The doesn’t kill us, as in the formula model, to touch all the input variables, you need Note that the concrete depth can be optimised by choosing a better encoding, i.e., use for certain indicators so that we can effectively and efficiently perform addition with the good choice of coefficient and subtraction.

Simulating a leaf gateSimulating a leaf gateSimulating a leaf gateSimulating a leaf gateSimulating a leaf gate
Simulating a leaf gate
Simulating an intermediate gateSimulating an intermediate gateSimulating an intermediate gateSimulating an intermediate gateSimulating an intermediate gate
Simulating an intermediate gate

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

Please enable JavaScript to view the comments powered by Disqus.