<p>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.</p>

<ol>
<li><p>A circuit is called <strong>synchronous</strong> (<a href="https://www.ams.org/journals/proc/1977-064-02/S0002-9939-1977-0456962-7/S0002-9939-1977-0456962-7.pdf" rel="nofollow noreferrer">Harper 1977</a>) if all gates are arranged into layers, and inputs must be at the layer 0. (An equivalent definition: for any gate <span class="math-container">$g$</span>, all paths from the inputs to <span class="math-container">$g$</span> have the same length.)</p></li>
<li><p>A circuit is <strong>locally synchronous</strong> (<a href="https://link.springer.com/chapter/10.1007%2F3-540-12920-0_12" rel="nofollow noreferrer">Belaga 1984</a>) if each input occurs exactly once but at an arbitrary layer.</p></li>
<li><p>A circuit is <strong>layered</strong> (<a href="https://www.cs.utexas.edu/~panni/sizedepth.pdf" rel="nofollow noreferrer">Gál, Jang 2010</a>) if gates and inputs are arranged into layers, inputs can occur multiple times at different layers. (An equivalent definition: for any  gate <span class="math-container">$g$</span> and output gate <span class="math-container">$o$</span>, all directed paths from <span class="math-container">$g$</span> to <span class="math-container">$o$</span> have the same length.)</p></li>
</ol>

<p>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). </p>

<p>Regarding the size of a layered circuit computing an unrestricted circuit of size <span class="math-container">$s$</span> we know the following:</p>

<ol>
<li><p>Any circuit of size <span class="math-container">$s$</span> can be computed by a synchronous/locally synchronous/layered circuit of size <span class="math-container">$s^2$</span> (<a href="https://eccc.weizmann.ac.il/resources/pdf/cobf.pdf" rel="nofollow noreferrer">Wegener 1987, Section 12.1</a>).</p></li>
<li><p>It should be hard to find an explicit function which requires a synchronous/locally synchronous/layered circuit of size <span class="math-container">$\omega(s\log{s})$</span>. Indeed, every circuit of size <span class="math-container">$s$</span> and depth <span class="math-container">$d$</span> can be computed by a synchronous circuit of size <span class="math-container">$O(sd)$</span> (<a href="https://eccc.weizmann.ac.il/resources/pdf/cobf.pdf" rel="nofollow noreferrer">Wegener 1987, Section 12.1</a>). Thus, even if we have an explicit function <span class="math-container">$f$</span> which requires synchronous circuits of size <span class="math-container">$\omega(n\log{n})$</span> (regardless of its complexity in the class of unrestricted circuits), then <span class="math-container">$f$</span> cannot be computed by a circuit of depth <span class="math-container">$O(\log{n})$</span> and size <span class="math-container">$O(n)$</span>, which answers a long-standing open question in circuit complexity (<a href="https://link.springer.com/chapter/10.1007/3-540-08353-7_135" rel="nofollow noreferrer">Valiant 1977</a>).</p></li>
<li><p>There exist explicit functions</p>

<p>3.1. with <span class="math-container">$\Omega(n\log{n})$</span> lower bound for <em>synchronous</em> circuits but <span class="math-container">$O(n)$</span> upper bound for <em>locally synchronous</em> circuits (<a href="https://link.springer.com/chapter/10.1007/3-540-51498-8_45" rel="nofollow noreferrer">Turán 1989</a>).</p>

<p>3.2. with <span class="math-container">$\Omega(n\log{n})$</span> lower bound for <em>locally synchronous</em> circuits but <span class="math-container">$O(n)$</span> upper bound for <em>layered</em> circuits (<a href="https://link.springer.com/chapter/10.1007/3-540-51498-8_45" rel="nofollow noreferrer">Turán 1989</a>).</p></li>
</ol>

<p>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 <span class="math-container">$n$</span> outputs which separates two such classes. </p>

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

CC BY-SA 4.0
2018-09-24T19:03:26.197Z
2019-02-07T22:38:23.230Z
2019-02-07T22:38:23.230Z
Alex Golovnev
<p>Consider a function <span class="math-container">$f$</span> computed by a boolean circuit <span class="math-container">$C$</span> with <span class="math-container">$n$</span> inputs of size <span class="math-container">$s(n) = \mathsf{poly}(n)$</span> over the basis <span class="math-container">$\{\mathsf{XOR},\mathsf{AND},\mathsf{NOT}\}$</span> (with indegree 2 for the <span class="math-container">$\mathsf{XOR},\mathsf{AND}$</span> gates).</p>
<p>A boolean circuit is <em>layered</em> if it can be arranged into <span class="math-container">$d$</span> layers (<span class="math-container">$d$</span> being the depth of the circuit) of gates such that any edge between two gates connects adjacent layers.</p>
<p>Given that <span class="math-container">$f$</span> has a boolean circuit of size <span class="math-container">$s$</span>, what can we say about the size of a layered circuit computing <span class="math-container">$f$</span>? There is a trivial upper bound: by adding dummy nodes to <span class="math-container">$C$</span> at each layer crossed by an edge, we get a layered circuit of size at most <span class="math-container">$O(s^2)$</span>. But can we get better in general (e.g. <span class="math-container">$O(s\cdot \log s)$</span>, or <span class="math-container">$O(s)$</span>), or for interesting class of circuits?</p>
<p><strong>Background.</strong> This question stems from recent results in cryptography which show how to securely compute layered boolean circuits of size <span class="math-container">$s$</span> with communication <span class="math-container">$o(s)$</span> (e.g. <span class="math-container">$s/\log s$</span> or <span class="math-container">$s/\log\log s)$</span>; I'm trying to understand how restrictive this restriction to layered boolean circuits can be in practice, either for general circuits or for &quot;natural&quot; circuits. However, I've not found much about layered circuits in the literature; appropriate pointers would also be welcome.</p>

CC BY-SA 4.0
2018-09-18T01:05:50.013Z
Here's an example of a circuit that seems hard to convert to a layered circuit without a significant blowup in size.  Define $f:\{0,1\}^{n-1} \to \{0,1\}$ to be some function that can be computed in size $u$.  Define $g(x_1,\dots,x_n) = (x_2,\dots,x_n,x_1 \oplus f(x_2,\dots,x_n))$, and let $C$ be $t$ iterations of $g$.  Then $C$ has size $O(tu)$.  It seems hard to build a layered circuit with size less than $\Theta(nt)$. So, if $u=o(n)$, maybe we should expect a gap between the size of a circuit vs size of a layered circuit.  Not a proof, just a suggestive example to maybe drive the intuition.
D.W.
CC BY-SA 4.0
2018-09-18T08:58:55.937Z
As far as I remember, for layered circuits the best known lower bound is of the form $\Omega(n \log n)$. It is particularly easy to prove for an $n$-to-$n$ function. Take, for example, a linear map $Ax$ where $A \in \{0,1\}^{n \times n}$ has zeroes on the main diagonal only. Then it must have at least $n$ gates on every layer and the number of layers is at least $\log_2 n$. Note that this function can be easily computed by a regular circuit of size $O(n)$. For single-output functions, it is also possible to prove the same lower bound, but I don't remember the argument.
Alexander S. Kulikov
CC BY-SA 4.0
2018-09-18T09:20:12.620Z
Thanks a lot for the comments. @AlexanderS.Kulikov, is your argument folklore, or do you have some pointer to works on layered circuits? The $\Omega(n \log n)$ makes sense - I would have been very surprise by something smaller - but is $O(n^2)$ the only known upper bound?
Geoffroy Couteau
CC BY-SA 4.0
2018-09-18T14:04:25.723Z
I guess it is a folklore, yes. I'm not sure I get the question about $O(n^2)$ upper bound. You may want to take a look at the following paper: https://www.cs.utexas.edu/~panni/sizedepth.pdf
Alexander S. Kulikov
CC BY-SA 4.0
2018-09-18T15:31:48.953Z
My question is the following: some functions with size-$n$ circuit require size-$\Omega(n\log n)$ layered circuit (by your comment); all functions with size-$n$ circuit have a size-$O(n^2)$ layered circuit. Are there functions with size-$n$ circuit and no size $O(n\log n)$ layered circuit? Or can all functions with size-$n$ circuit be computed by size-$o(n^2)$ layered circuits?

I saw the paper (it's essentially the only one I've found on layered boolean circuits). It might have implications for my question, but I don't see which ones. Thanks for your remarks anyway, it already helps a lot.
Geoffroy Couteau
CC BY-SA 4.0
2018-09-18T23:12:38.407Z
I think that we don't know a better than $O(s^2)$ transformation in general. Note that a circuit of size $s$ and depth $d$ can be transformed into a layered circuit of size at most $ds$. (Which in the worst case gives us a circuit of size $O(s^2)$.) I just wanted to point out that if we could prove a lower bound of $\omega(n\log{n})$ on the size of a layered circuit, this would give us a super-linear lower bound on the size of log-depth circuits for this function. This question remains open for more than 40 years.
Alex Golovnev
CC BY-SA 4.0
2018-09-18T23:14:14.987Z
Also, there are two types of layered circuits: one where all inputs must be at the lowest layer, and one where inputs can be at arbitrary layers. There are $n\log{n}$ vs $n$ separations between all three types of circuits. I recommend reading the first 1.5 pages of this paper for a short overview of the known separations: https://link.springer.com/chapter/10.1007/3-540-51498-8_45
Alex Golovnev
CC BY-SA 4.0
2018-09-19T07:35:06.807Z
If you want to synthesize your comments into an answer, I'll accept it. Thanks!
Geoffroy Couteau
CC BY-SA 4.0
2018-09-19T14:21:20.643Z
To elaborate a bit, the case I'm interested it is where inputs can be at any level, and can also appear several time (the same input can be reused across many different layers). This is more powerful that the "locally synchronous circuits" studied in the paper you point to. Anyway, all of this provide me sufficient pointers and indications to get reasonable intuitions about my problem.
Geoffroy Couteau
<circuit-complexity><circuits>
How small can be a layered boolean circuit for a function with circuit complexity $s$?
Geoffroy Couteau
# How small can be a layered boolean circuit for a function with circuit complexity $s$?

(Asked by: username_0 on 2018-09-17)

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.

**Tags:** circuit-complexity, circuits
> **Comments:**
> **username_1**: Here's an example of a circuit that seems hard to convert to a layered circuit without a significant blowup in size.  Define $f:\{0,1\}^{n-1} \to \{0,1\}$ to be some function that can be computed in size $u$.  Define $g(x_1,\dots,x_n) = (x_2,\dots,x_n,x_1 \oplus f(x_2,\dots,x_n))$, and let $C$ be $t$ iterations of $g$.  Then $C$ has size $O(tu)$.  It seems hard to build a layered circuit with size less than $\Theta(nt)$. So, if $u=o(n)$, maybe we should expect a gap between the size of a circuit vs size of a layered circuit.  Not a proof, just a suggestive example to maybe drive the intuition.  
> **username_2**: As far as I remember, for layered circuits the best known lower bound is of the form $\Omega(n \log n)$. It is particularly easy to prove for an $n$-to-$n$ function. Take, for example, a linear map $Ax$ where $A \in \{0,1\}^{n \times n}$ has zeroes on the main diagonal only. Then it must have at least $n$ gates on every layer and the number of layers is at least $\log_2 n$. Note that this function can be easily computed by a regular circuit of size $O(n)$. For single-output functions, it is also possible to prove the same lower bound, but I don't remember the argument.  
> **username_0**: Thanks a lot for the comments. @AlexanderS.Kulikov, is your argument folklore, or do you have some pointer to works on layered circuits? The $\Omega(n \log n)$ makes sense - I would have been very surprise by something smaller - but is $O(n^2)$ the only known upper bound?  
> **username_2**: I guess it is a folklore, yes. I'm not sure I get the question about $O(n^2)$ upper bound. You may want to take a look at the following paper: https://www.cs.utexas.edu/~panni/sizedepth.pdf  
> **username_0**: My question is the following: some functions with size-$n$ circuit require size-$\Omega(n\log n)$ layered circuit (by your comment); all functions with size-$n$ circuit have a size-$O(n^2)$ layered circuit. Are there functions with size-$n$ circuit and no size $O(n\log n)$ layered circuit? Or can all functions with size-$n$ circuit be computed by size-$o(n^2)$ layered circuits?  I saw the paper (it's essentially the only one I've found on layered boolean circuits). It might have implications for my question, but I don't see which ones. Thanks for your remarks anyway, it already helps a lot.  
> **username_3**: I think that we don't know a better than $O(s^2)$ transformation in general. Note that a circuit of size $s$ and depth $d$ can be transformed into a layered circuit of size at most $ds$. (Which in the worst case gives us a circuit of size $O(s^2)$.) I just wanted to point out that if we could prove a lower bound of $\omega(n\log{n})$ on the size of a layered circuit, this would give us a super-linear lower bound on the size of log-depth circuits for this function. This question remains open for more than 40 years.  
> **username_3**: Also, there are two types of layered circuits: one where all inputs must be at the lowest layer, and one where inputs can be at arbitrary layers. There are $n\log{n}$ vs $n$ separations between all three types of circuits. I recommend reading the first 1.5 pages of this paper for a short overview of the known separations: https://link.springer.com/chapter/10.1007/3-540-51498-8_45  
> **username_0**: If you want to synthesize your comments into an answer, I'll accept it. Thanks!  
> **username_0**: To elaborate a bit, the case I'm interested it is where inputs can be at any level, and can also appear several time (the same input can be reused across many different layers). This is more powerful that the "locally synchronous circuits" studied in the paper you point to. Anyway, all of this provide me sufficient pointers and indications to get reasonable intuitions about my problem.  

---

## 1 answers

### Answer by username_3 on 2018-09-24. Score: 9 | Accepted answer

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](https://www.ams.org/journals/proc/1977-064-02/S0002-9939-1977-0456962-7/S0002-9939-1977-0456962-7.pdf)) 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](https://link.springer.com/chapter/10.1007%2F3-540-12920-0_12)) if each input occurs exactly once but at an arbitrary layer.
3. A circuit is **layered** ([Gál, Jang 2010](https://www.cs.utexas.edu/~panni/sizedepth.pdf)) 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](https://eccc.weizmann.ac.il/resources/pdf/cobf.pdf)).
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](https://eccc.weizmann.ac.il/resources/pdf/cobf.pdf)). 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](https://link.springer.com/chapter/10.1007/3-540-08353-7_135)).
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](https://link.springer.com/chapter/10.1007/3-540-51498-8_45)).

   3.2. with $\Omega(n\log{n})$ lower bound for *locally synchronous* circuits but $O(n)$ upper bound for *layered* circuits ([Turán 1989](https://link.springer.com/chapter/10.1007/3-540-51498-8_45)).

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$.


---

