Consider a circuit belonging to the class $\text{NC}^i$, as defined here.

From my understanding, the circuit consists of AND, OR ar NOT gates, each of bounded fan in --- without loss of generality, let the fan in be $2$ --- with $\log^{i} n$ depth and polynomial size.

Now, let's say we define a different circuit class, $\text{NearestNeighbourNC}^i$, where we have AND, OR, and NOT gates, again of fan in $2$, with the additional restriction that each gates can only act on nearest neighbor lines. Let's say we also have nearest neighbor SWAP gates.

Is it true that compiling a general $\text{NC}^i$ circuit with a circuit of this new class will blow up the depth and the depth would now be $\text{poly}(n)$?

$\text{NC}^i$ has no guarantee on the locality of the inputs and whether they are nearest neighbour, so I think it should be true. Is there any clever way of compiling $\text{NC}^i$ circuits that preserve locality without blowing up the depth?

For each circuit in the class $\text{NearestNeighbourNC}^i$, consider starting with a $\sqrt{n} \times \sqrt{n}$ 2D grid. We will build a circuit on this grid, in layers

Each vertex denotes an input node, storing some value.

When an AND or OR gate acts on two vertices, it transforms them into one vertex storing the output value. A SWAP gate swaps the value of two vertices. A NOT gate complements the value of a vertex.

The restriction is that the gates are only between adjacent vertices.

Now, consider constructing the circuit in levels.

At each level, we apply AND, OR, or SWAP gates to some pairs of adjacent vertices, NOT gates to some vertices, and do nothing to other vertices.

After each level, we are left with some graph.

In the final level, one of the vertices is the vertex storing the final output value.

  • $\begingroup$ I just mean that the inputs to each gate should come from lines that are spatially local. As in, if we have three lines, spatially separated, and an AND gate, the gate can only act on input lines 1 and 2 or 2 and 3 -- we cannot apply the gate directly to 1 and 3. $\endgroup$
    – Sid Meyers
    Jan 3 at 7:29
  • $\begingroup$ Is it clearer now? $\endgroup$
    – Sid Meyers
    Jan 3 at 10:00
  • $\begingroup$ That helps a lot, thanks. SWAP gates are not part of NC circuits, and they don't have a single output, so they don't fit in this formalism. By "adjacent" do you mean "horizontally adjacent", i.e., also must both be in both layers? It's not clear what it means for a gate to be "between" vertices; do you mean to act on two vertices? $\endgroup$
    – D.W.
    Jan 3 at 21:04
  • $\begingroup$ In a given level, can gate 1 at level $\ell$ take inputs from outputs 100,101 at level $\ell-1$ and gate 2 take inputs from outputs 1,2 at level $\ell-1$? Or do you also intend that the graph be planar? $\endgroup$
    – D.W.
    Jan 3 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.