How small can be a layered boolean circuit for a function with circuit complexity $s$?

Question

Consider a function $f$ computed by a boolean circuit $C$ with $n$ inputs of size $s(n) = \mathsf{poly}(n)$ over the basis $\{\mathsf{XOR},\mathsf{AND},\mathsf{NOT}\}$ (with indegree 2 for the $\mathsf{XOR},\mathsf{AND}$ gates).

A boolean circuit is layered if it can be arranged into $d$ layers ($d$ being the depth of the circuit) of gates such that any edge between two gates connects adjacent layers.

Given that $f$ has a boolean circuit of size $s$, what can we say about the size of a layered circuit computing $f$? There is a trivial upper bound: by adding dummy nodes to $C$ at each layer crossed by an edge, we get a layered circuit of size at most $O(s^2)$. But can we get better in general (e.g. $O(s\cdot \log s)$, or $O(s)$), or for interesting class of circuits?

Background. This question stems from recent results in cryptography which show how to securely compute layered boolean circuits of size $s$ with communication $o(s)$ (e.g. $s/\log s$ or $s/\log\log s)$; I'm trying to understand how restrictive this restriction to layered boolean circuits can be in practice, either for general circuits or for "natural" circuits. However, I've not found much about layered circuits in the literature; appropriate pointers would also be welcome.

Answer 1

As far as I know, three classes of layered circuits have been studied. In all of these definitions arcs are allowed only between two adjacent layers.

1. A circuit is called synchronous (Harper 1977) if all gates are arranged into layers, and inputs must be at the layer 0. (An equivalent definition: for any gate $g$, all paths from the inputs to $g$ have the same length.)

2. A circuit is locally synchronous (Belaga 1984) if each input occurs exactly once but at an arbitrary layer.

3. A circuit is layered (Gál, Jang 2010) if gates and inputs are arranged into layers, inputs can occur multiple times at different layers. (An equivalent definition: for any gate $g$ and output gate $o$, all directed paths from $g$ to $o$ have the same length.)

It is easy to see that the three classes are listed from the weakest to the strongest (and the class of unrestricted circuits is even stronger).

Regarding the size of a layered circuit computing an unrestricted circuit of size $s$ we know the following:

1. Any circuit of size $s$ can be computed by a synchronous/locally synchronous/layered circuit of size $s^2$ (Wegener 1987, Section 12.1).

2. It should be hard to find an explicit function which requires a synchronous/locally synchronous/layered circuit of size $\omega(s\log{s})$. Indeed, every circuit of size $s$ and depth $d$ can be computed by a synchronous circuit of size $O(sd)$ (Wegener 1987, Section 12.1). Thus, even if we have an explicit function $f$ which requires synchronous circuits of size $\omega(n\log{n})$ (regardless of its complexity in the class of unrestricted circuits), then $f$ cannot be computed by a circuit of depth $O(\log{n})$ and size $O(n)$, which answers a long-standing open question in circuit complexity (Valiant 1977).

3. There exist explicit functions

   3.1. with $\Omega(n\log{n})$ lower bound for synchronous circuits but $O(n)$ upper bound for locally synchronous circuits (Turán 1989).

   3.2. with $\Omega(n\log{n})$ lower bound for locally synchronous circuits but $O(n)$ upper bound for layered circuits (Turán 1989).

It is important to note that these two separation results by Turán are proven for functions with one output. It is often much easier to find a function with $n$ outputs which separates two such classes.

As an example, consider the function $f\colon\{0,1\}^n\to\{0,1\}^n$ where the $i$th output bit is an XOR of all inputs except for the $i$th one. This function can easily be computed by a layered circuit of size $O(n)$: First compute an XOR of all inputs in $\log{n}$ layers of total size $n$, then compute all outputs in one layer of size $n$. On the other hand, $f$ requires synchronous circuits of size $\Omega(n\log{n})$. Indeed, in order to compute a parity of length $n-1$, the circuit depth must be at least $\Omega(\log{n})$. On the other hand, each layer must transmit $n$ bits of information, thus its size must be at least $n$.