12
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – D.W. Sep 18 '18 at 1:05
  • 2
    $\begingroup$ 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. $\endgroup$ – Alexander S. Kulikov Sep 18 '18 at 8:58
  • 1
    $\begingroup$ 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? $\endgroup$ – Geoffroy Couteau Sep 18 '18 at 9:20
  • 1
    $\begingroup$ 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: cs.utexas.edu/~panni/sizedepth.pdf $\endgroup$ – Alexander S. Kulikov Sep 18 '18 at 14:04
  • 1
    $\begingroup$ 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. $\endgroup$ – Alex Golovnev Sep 18 '18 at 23:12
8
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.