<p>I will try to summarize my previous comments.</p>

<p>Let us first ignore the fact that your original circuit has (constant) depth $k$; just assume it has size $S$. Let $A$ be the smallest number such that every unbounded fanin circuit size $S$ can be transformed into an unbounded fanin formula $F$ of size $O(S^A)$. I claim that the best we can do so far is to achieve $A=O(S/\log^2 S)$. Say, it is even not known whether whether any (fanin-2) circuit of size $S=O(n)$ can be simulated by a formula of size smaller than $\exp(n/\log n)$.</p>

<p>To show the claim, we transform the formula $F$ into a fanin-2 formula $F′$ of size $M=O(S^{2A})$. It is well known that the depth $D$ of every formula $F′$ can be made logarithmic in its size, that is $D=O(\log M)=O(A\log S)$. [This was first shown by Khrapchenko 1968, and then the constant under big-O was improved to $D\leq 1.73\log_2M$ by several authors.] On the other hand, the best known result for fanin-2 circuits [Paterson and Valiant, TCS 2(3), 397-400] says that $Depth=O(Size/\log Size)$. Thus, having a simulation with $A$ much smaller than $S/\log^2 S$ would improve the best known Size-Depth simulation for circuits.</p>

<p>This, however, is only a "word of caution" - it does not answer your question because you assume that your original circuit has <strong>constant</strong> depth $k$, implying that in this case we can just take $A=k$ (or $A=k−1$ if we have a single output gate). The power of Paterson-Valiant simulation is that it applies to arbitrary, even very unbalanced circuits whose depth is almost the entire size! But in your bounded-depth setting, even the case $k=3$ is not clear: can every depth-3 circuit of size $S$ be transformed into a depth-3 formula of size much smaller than $S^2$? I guess the answer should be "no" (could be an interesting exercise for students). A depth-3 formula is just a big OR of CNFs. The question is to find an OR of CNFs that share many clauses in common, but otherwise are "very different" to force a large depth-3 formula.</p>

<p>The problem is that we want to obtain a <strong>formula</strong> (a fanout-1 circuit). As was pointed above, allowing gates of <strong>fanout-2</strong> makes simulation simpler: Hoover, Klawe and Pippenger [JACM 31(1), 1980] show that any fanin-2 circuit of size $S$ and depth $D$ has an equivalent fanin-2 and fanout-2 circuit of size $3S−2n$ and depth $2D$. Thus, if fanin is unbounded, then the resulting circuit will have size $O(S^2)$ and depth $O(D\log S)$. </p>

<p>There is yet another result somehow related to your question. Lozhkin (1981) proved that if a boolean function $f$ can be computed by an $AC^0$ <strong>formula</strong> of depth $k$ and size $S$, then $f$ can be computed by fanin-2 formula of depth $D\leq k-1+\lceil\log_2S\rceil$ (this follows from Theorem 6.2 in my book). Note that a trivial upper bound would only be $D\leq k\log S$ (if we would simulate each single gate by a tree of depth $\log S$).</p>

CC BY-SA 3.0
2011-08-29T10:44:05.483Z
2011-08-29T10:44:05.483Z
Stasys
<p><strong>EDIT (Aug 22, 2011):</strong></p>

<p>I am further simplifying the question and putting a bounty on the question. Perhaps this simpler question will have an easy answer. I'm also going to strikethrough all the parts of the original question that are no longer relevant. (Thanks to Stasys Jukna and Ryan O'Donnell for partially answering the original question!)</p>

<hr>

<p><strong>Background:</strong></p>

<p>Given an AC<sup>0</sup> circuit with depth k and size S, there exists another AC<sup>0</sup> circuit computing the same function with depth k and size $O(S^k)$ such that the new circuit has fanout = 1 for all gates. In other words, the circuit looks like a tree (except at the inputs, since the inputs may fanout to more than one gate). One way to do this is by duplicating all the gates that have fanout > 1 until all gates have fanout = 1.</p>

<p><strike> But is this the most efficient way to convert AC<sup>0</sup> circuits to AC<sup>0</sup> circuits with fanout 1? I read the following in <a href="http://www.cs.cmu.edu/~odonnell/complexity/lecture14.pdf" rel="noreferrer">Lecture 14 of Ryan O'Donnell's course notes</a>:</p>

<blockquote>
  <p>Suppose C is any depth-k circuit of size S which computes Parity. It
  is an exercise to show that C can be converted into a leveled  depth-k
  circuit, where the levels alternate AND and OR gates, the inputs wires
  are the 2n literals, and each gate has fan-out 1 (i.e., it’s a tree) —
  and the size increases to at most $(2kS)^2 \leq O(S^4)$.</p>
  
  <p>Footnote: Actually, this is a slightly tricky exercise. It’s easier if
  you only have to get size $O(S^k)$, which is almost the same for our
  purposes if you think of k as a “constant”.</p>
</blockquote>

<p>Does this mean there is a way to take any depth k AC<sup>0</sup> circuit of size S and convert it to an AC<sup>0</sup> circuit with fanout 1, depth k and size $(2kS)^2$? If so, how is this done and is this the best-known method?
</strike></p>

<p><strong>Original Question:</strong></p>

<blockquote>
  <p>Given an AC<sup>0</sup> circuit with depth k and size S, what's the best-known method (in terms of minimizing the circuit size of the resultant circuit) of converting this to an AC<sup>0</sup> circuit of depth k and gate fanout 1? Are there any lower bounds known for this?</p>
</blockquote>

<hr>

<p><strong>Newer, simpler question:</strong></p>

<p>This question is a relaxation of the original one where I don't insist that the resultant circuit be constant depth. As explained above, there is a way to convert an AC<sup>0</sup> circuit with depth k, size S into a circuit with size $O(S^k)$ such that the new circuit has fanout = 1 for all gates. Is there a better construction?</p>

<blockquote>
  <p>Given an AC<sup>0</sup> circuit with depth k and size S, what's the best-known method (in terms of minimizing the circuit size of the resultant circuit) of converting this to a circuit of any depth with gate fanout 1?</p>
</blockquote>

CC BY-SA 3.0
2011-08-10T14:29:06.940Z
The $O(S^k)$ bound is o.k. But if the bound $(2kS)^2$ would hold for **arbitrary** circuits (not only those computing the Parity function), then one could simulate **every** fanin-2 circuit of size $S$ by a fanin-2 formula of size $O(S^5)$: $S$ fanin-2 gates are enough to simulate one gate of unbounded fanin. Then the **formula** could be transformed into one of depth $O(\log S)$ (a well known result, wrongly attributed to Spira). Thus, we would get that circuit depth is a most $O(\log S)$. But this is too nice to be true: the best known upper bound for circuit-depth is only $O(S/\log S)$.
Stasys
CC BY-SA 3.0
2011-08-10T14:38:17.240Z
B.t.w. $O(kS)^2)$ indeed holds also for **arbitrary** circuits, but only if we allow gates of **fanin-2** (see, e.g., Thm. 4.1 in Wegener's book); then circuits still can remember intermediate results. The situation with fanin-1 is very different: here circuits have no memory at all. But Robin's question is very interesting. It would be even interesting to show that **depth-3** circuits of size $S$ can be simulated by depth-3 formulas of size smaller than $S^2$.
Stasys
CC BY-SA 3.0
2011-08-10T20:08:14.417Z
I would trust whatever Stas says above; I wasn't being very careful in those notes (sorry).  On the other hand, I remember when writing them being quite frustrated about sourcing the fact -- mentioned in many many papers but almost never with citation -- that one can convert arbitrary $AC^0$ circuits into layered ones without blowing up size "much".  I would love to see a pointer to the best known result on this subject.
Ryan O'Donnell
CC BY-SA 3.0
2011-08-11T08:20:03.813Z
@Ryan O'Donnell: indeed, one can easily make a circuit **layered** with blow-up $O(kS)$. We use associativity to achieve that every AND gate has only OR gates as inputs, and vice versa; the depth remains unchanged. Then arrange gates by their depth, and add if necessary trivial fanin-1 OR and AND gates to get a layered circuit; the depth remains the same and the size increases by only a factor of k. But I understood that Robin wants a **circuit** be converted into a **formula** (a tree-like circuit, except that input literals may have large fanout).
Stasys
CC BY-SA 3.0
2011-08-15T21:50:57.913Z
@Stasys Jukna: Thanks for the responses. Does the result you cite (Wegener's book, 4.1) convert depth k circuits to circuits with fanout 2 preserving the depth too? It seems like the depth goes up. Since this question seems hard, I'll edit my question to ask a simpler version of it.. and I'll be happy to accept any answers to that question too.
Robin Kothari
CC BY-SA 3.0
2011-08-15T22:05:24.303Z
@Ryan O'Donnell: Thanks for the response and for putting up your lecture notes online! In particular, your lecture notes on the analysis of Boolean functions have been super helpful.
Robin Kothari
CC BY-SA 3.0
2011-08-16T18:48:23.977Z
@Robin: yes, the depth increases. Hoover, Klawe and Pippenger [JACM 31(1), 1980] have a tighter estimate: any fanin-2 circuit of size $S$ and depth $D$ has an equivalent fanin-2 and fanout-2 circuit of size $3S-2n$ and depth $2D$. Thus, if fanin is **unbounded**, then resulting circuit will have size $O(S^2)$ and depth $O(D\log D)$. These are, of course, very rough estimates. And I join you: Ryan's lecture notes on the analysis are really useful for anyone.
Stasys
CC BY-SA 3.0
2011-08-16T19:10:03.130Z
@Stasys: Thanks. I understand how the Hoover-Klawe-Pippenger result gives a circuit of size $O(S^2)$, but it seems to me that the depth goes up to $O(D \log S)$. How does one achieve $O(D \log D)$? (The paper says that the new circuit's depth is like $O(D \log_t s)$ where $s$ is the fanin of the original circuit and $t$ is the desired fanout. Putting s = S and t = 2 gives a new depth of $O(D \log S)$.)
Robin Kothari
CC BY-SA 3.0
2011-08-16T19:19:32.283Z
@Robin: you are right, the depth is $O(D\log S)$, sorry.
Stasys
CC BY-SA 3.0
2011-08-16T19:36:09.747Z
@Stasys: Alright. Thanks for the comments and the references.
Robin Kothari
CC BY-SA 3.0
2011-08-23T04:45:14.247Z
I would not call this a simplification, you have removed the requirement that the final circuit is of bounded-depth, so there are more possibilities, and you are asking for the best of them. It might be easier to answer negatively (i.e. this the best possible) in the case where the final circuit is of bounded depth. :)
Kaveh
CC BY-SA 3.0
2011-08-23T14:21:22.907Z
@Kaveh: From the point of view of a better construction, I think it's a simplification. It should be easier to improve on the $S^k$ bound when there are fewer restrictions on the final circuit. The reason I removed the constant-depth restriction is that some techniques (like Hoover-Klawe-Pippenger) increase the depth. But you're right, if $S^k$ is believed to be optimal, then the question isn't a simplification.
Robin Kothari
CC BY-SA 3.0
2011-08-28T18:31:31.223Z
@Robin: By what I've wrote in comments, one cannot expect to transform a circuit of size $S$ into a fanout-1 circuit of size much smaller than $S^K$ for $K$ smaller than $S/\log^2S$. Any such transformation would improve the best known result that a fanin-2 circuit of size $S$ can be transformed into a circuit of depth $O(S/\log S)$. Any improvement of this would be a great event. So, your +200 points are in no danger. [Sorry, I wanted this to appear as a comment, not as an "answer".]
Stasys
CC BY-SA 3.0
2011-08-28T19:01:48.850Z
Oh, I hadn't noticed that your argument gave such lower bounds. So for example, a technique that converted any depth k, size S circuit to a fanout-1 circuit of size $S^\sqrt{k}$ would give us much better upper bounds for circuit depth. But this doesn't rule out a technique that maps size S, depth k circuits to fanout-1 circuits of size $2^k S$, right? (It would be better if you posted your comments as an answer, since I would like to award the bounty to you. Also, if no one posts an answer by tomorrow, I will lose 200 points and no one will receive them. This bounty system works strangely.)
Robin Kothari
CC BY-SA 3.0
2011-08-28T20:08:43.373Z
@Robin: Having a $2^kS$ upper bound you could simulate special circuits size $S$ (with at most $k$ AND-OR alternations) by circuits of depth $k+O(\log S)$. Too good to be true. Concerning answers: you could just make an extract (of whomever) as an answer. Circuit size vs. circuit depth problem is a big one. No "bounties" can make it easier ...
Stasys
CC BY-SA 3.0
2011-08-28T21:22:24.043Z
@Stasys Jukna: Robin can't award the bounty to an answer he creates.  The system prohibits it.  I'm sure everyone would be happy if the reputation points went to you.
Aaron Sterling
CC BY-SA 3.0
2011-08-29T00:18:36.647Z
@Stasys: Your comments have been very informative for me (and others interested in this question). It is only fair that you should receive the bounty.
Robin Kothari
<cc.complexity-theory><lower-bounds><circuit-complexity>
Most efficient way to convert an $\text{AC}^0$ circuit to a circuit  (of any depth) with gate fanout 1
Robin Kothari
# Most efficient way to convert an $\text{AC}^0$ circuit to a circuit  (of any depth) with gate fanout 1

(Asked by: username_0 on 2011-08-08)

**EDIT (Aug 22, 2011):**

I am further simplifying the question and putting a bounty on the question. Perhaps this simpler question will have an easy answer. I'm also going to strikethrough all the parts of the original question that are no longer relevant. (Thanks to username_1 Jukna and username_2 for partially answering the original question!)

---

**Background:**

Given an AC0 circuit with depth k and size S, there exists another AC0 circuit computing the same function with depth k and size $O(S^k)$ such that the new circuit has fanout = 1 for all gates. In other words, the circuit looks like a tree (except at the inputs, since the inputs may fanout to more than one gate). One way to do this is by duplicating all the gates that have fanout > 1 until all gates have fanout = 1.

But is this the most efficient way to convert AC0 circuits to AC0 circuits with fanout 1? I read the following in [Lecture 14 of username_2's course notes](http://www.cs.cmu.edu/~odonnell/complexity/lecture14.pdf):

> Suppose C is any depth-k circuit of size S which computes Parity. It
> is an exercise to show that C can be converted into a leveled depth-k
> circuit, where the levels alternate AND and OR gates, the inputs wires
> are the 2n literals, and each gate has fan-out 1 (i.e., it’s a tree) —
> and the size increases to at most $(2kS)^2 \leq O(S^4)$.
>
> Footnote: Actually, this is a slightly tricky exercise. It’s easier if
> you only have to get size $O(S^k)$, which is almost the same for our
> purposes if you think of k as a “constant”.

Does this mean there is a way to take any depth k AC0 circuit of size S and convert it to an AC0 circuit with fanout 1, depth k and size $(2kS)^2$? If so, how is this done and is this the best-known method?

**Original Question:**

> Given an AC0 circuit with depth k and size S, what's the best-known method (in terms of minimizing the circuit size of the resultant circuit) of converting this to an AC0 circuit of depth k and gate fanout 1? Are there any lower bounds known for this?

---

**Newer, simpler question:**

This question is a relaxation of the original one where I don't insist that the resultant circuit be constant depth. As explained above, there is a way to convert an AC0 circuit with depth k, size S into a circuit with size $O(S^k)$ such that the new circuit has fanout = 1 for all gates. Is there a better construction?

> Given an AC0 circuit with depth k and size S, what's the best-known method (in terms of minimizing the circuit size of the resultant circuit) of converting this to a circuit of any depth with gate fanout 1?

**Tags:** cc.complexity-theory, lower-bounds, circuit-complexity

> **Comments:**
> **username_1**: The $O(S^k)$ bound is o.k. But if the bound $(2kS)^2$ would hold for **arbitrary** circuits (not only those computing the Parity function), then one could simulate **every** fanin-2 circuit of size $S$ by a fanin-2 formula of size $O(S^5)$: $S$ fanin-2 gates are enough to simulate one gate of unbounded fanin. Then the **formula** could be transformed into one of depth $O(\log S)$ (a well known result, wrongly attributed to Spira). Thus, we would get that circuit depth is a most $O(\log S)$. But this is too nice to be true: the best known upper bound for circuit-depth is only $O(S/\log S)$.  
> **username_1**: B.t.w. $O(kS)^2)$ indeed holds also for **arbitrary** circuits, but only if we allow gates of **fanin-2** (see, e.g., Thm. 4.1 in Wegener's book); then circuits still can remember intermediate results. The situation with fanin-1 is very different: here circuits have no memory at all. But Robin's question is very interesting. It would be even interesting to show that **depth-3** circuits of size $S$ can be simulated by depth-3 formulas of size smaller than $S^2$.  
> **username_2**: I would trust whatever Stas says above; I wasn't being very careful in those notes (sorry).  On the other hand, I remember when writing them being quite frustrated about sourcing the fact -- mentioned in many many papers but almost never with citation -- that one can convert arbitrary $AC^0$ circuits into layered ones without blowing up size "much".  I would love to see a pointer to the best known result on this subject.  
> **username_1**: @username_2: indeed, one can easily make a circuit **layered** with blow-up $O(kS)$. We use associativity to achieve that every AND gate has only OR gates as inputs, and vice versa; the depth remains unchanged. Then arrange gates by their depth, and add if necessary trivial fanin-1 OR and AND gates to get a layered circuit; the depth remains the same and the size increases by only a factor of k. But I understood that Robin wants a **circuit** be converted into a **formula** (a tree-like circuit, except that input literals may have large fanout).  
> **username_0**: @username_1 Jukna: Thanks for the responses. Does the result you cite (Wegener's book, 4.1) convert depth k circuits to circuits with fanout 2 preserving the depth too? It seems like the depth goes up. Since this question seems hard, I'll edit my question to ask a simpler version of it.. and I'll be happy to accept any answers to that question too.  
> **username_0**: @username_2: Thanks for the response and for putting up your lecture notes online! In particular, your lecture notes on the analysis of Boolean functions have been super helpful.  
> **username_1**: @Robin: yes, the depth increases. Hoover, Klawe and Pippenger [JACM 31(1), 1980] have a tighter estimate: any fanin-2 circuit of size $S$ and depth $D$ has an equivalent fanin-2 and fanout-2 circuit of size $3S-2n$ and depth $2D$. Thus, if fanin is **unbounded**, then resulting circuit will have size $O(S^2)$ and depth $O(D\log D)$. These are, of course, very rough estimates. And I join you: Ryan's lecture notes on the analysis are really useful for anyone.  
> **username_0**: @username_1: Thanks. I understand how the Hoover-Klawe-Pippenger result gives a circuit of size $O(S^2)$, but it seems to me that the depth goes up to $O(D \log S)$. How does one achieve $O(D \log D)$? (The paper says that the new circuit's depth is like $O(D \log_t s)$ where $s$ is the fanin of the original circuit and $t$ is the desired fanout. Putting s = S and t = 2 gives a new depth of $O(D \log S)$.)  
> **username_1**: @Robin: you are right, the depth is $O(D\log S)$, sorry.  
> **username_0**: @username_1: Alright. Thanks for the comments and the references.  
> **username_3**: I would not call this a simplification, you have removed the requirement that the final circuit is of bounded-depth, so there are more possibilities, and you are asking for the best of them. It might be easier to answer negatively (i.e. this the best possible) in the case where the final circuit is of bounded depth. :)  
> **username_0**: @username_3: From the point of view of a better construction, I think it's a simplification. It should be easier to improve on the $S^k$ bound when there are fewer restrictions on the final circuit. The reason I removed the constant-depth restriction is that some techniques (like Hoover-Klawe-Pippenger) increase the depth. But you're right, if $S^k$ is believed to be optimal, then the question isn't a simplification.  
> **username_1**: @Robin: By what I've wrote in comments, one cannot expect to transform a circuit of size $S$ into a fanout-1 circuit of size much smaller than $S^K$ for $K$ smaller than $S/\log^2S$. Any such transformation would improve the best known result that a fanin-2 circuit of size $S$ can be transformed into a circuit of depth $O(S/\log S)$. Any improvement of this would be a great event. So, your +200 points are in no danger. [Sorry, I wanted this to appear as a comment, not as an "answer".]  
> **username_0**: Oh, I hadn't noticed that your argument gave such lower bounds. So for example, a technique that converted any depth k, size S circuit to a fanout-1 circuit of size $S^\sqrt{k}$ would give us much better upper bounds for circuit depth. But this doesn't rule out a technique that maps size S, depth k circuits to fanout-1 circuits of size $2^k S$, right? (It would be better if you posted your comments as an answer, since I would like to award the bounty to you. Also, if no one posts an answer by tomorrow, I will lose 200 points and no one will receive them. This bounty system works strangely.)  
> **username_1**: @Robin: Having a $2^kS$ upper bound you could simulate special circuits size $S$ (with at most $k$ AND-OR alternations) by circuits of depth $k+O(\log S)$. Too good to be true. Concerning answers: you could just make an extract (of whomever) as an answer. Circuit size vs. circuit depth problem is a big one. No "bounties" can make it easier ...  
> **username_4**: @username_1 Jukna: Robin can't award the bounty to an answer he creates.  The system prohibits it.  I'm sure everyone would be happy if the reputation points went to you.  
> **username_0**: @username_1: Your comments have been very informative for me (and others interested in this question). It is only fair that you should receive the bounty.  

---

## 1 answers

### Answer by username_1 on 2011-08-29. Score: 11 | Accepted answer

I will try to summarize my previous comments.

Let us first ignore the fact that your original circuit has (constant) depth $k$; just assume it has size $S$. Let $A$ be the smallest number such that every unbounded fanin circuit size $S$ can be transformed into an unbounded fanin formula $F$ of size $O(S^A)$. I claim that the best we can do so far is to achieve $A=O(S/\log^2 S)$. Say, it is even not known whether whether any (fanin-2) circuit of size $S=O(n)$ can be simulated by a formula of size smaller than $\exp(n/\log n)$.

To show the claim, we transform the formula $F$ into a fanin-2 formula $F′$ of size $M=O(S^{2A})$. It is well known that the depth $D$ of every formula $F′$ can be made logarithmic in its size, that is $D=O(\log M)=O(A\log S)$. [This was first shown by Khrapchenko 1968, and then the constant under big-O was improved to $D\leq 1.73\log\_2M$ by several authors.] On the other hand, the best known result for fanin-2 circuits [Paterson and Valiant, TCS 2(3), 397-400] says that $Depth=O(Size/\log Size)$. Thus, having a simulation with $A$ much smaller than $S/\log^2 S$ would improve the best known Size-Depth simulation for circuits.

This, however, is only a "word of caution" - it does not answer your question because you assume that your original circuit has **constant** depth $k$, implying that in this case we can just take $A=k$ (or $A=k−1$ if we have a single output gate). The power of Paterson-Valiant simulation is that it applies to arbitrary, even very unbalanced circuits whose depth is almost the entire size! But in your bounded-depth setting, even the case $k=3$ is not clear: can every depth-3 circuit of size $S$ be transformed into a depth-3 formula of size much smaller than $S^2$? I guess the answer should be "no" (could be an interesting exercise for students). A depth-3 formula is just a big OR of CNFs. The question is to find an OR of CNFs that share many clauses in common, but otherwise are "very different" to force a large depth-3 formula.

The problem is that we want to obtain a **formula** (a fanout-1 circuit). As was pointed above, allowing gates of **fanout-2** makes simulation simpler: Hoover, Klawe and Pippenger [JACM 31(1), 1980] show that any fanin-2 circuit of size $S$ and depth $D$ has an equivalent fanin-2 and fanout-2 circuit of size $3S−2n$ and depth $2D$. Thus, if fanin is unbounded, then the resulting circuit will have size $O(S^2)$ and depth $O(D\log S)$.

There is yet another result somehow related to your question. Lozhkin (1981) proved that if a boolean function $f$ can be computed by an $AC^0$ **formula** of depth $k$ and size $S$, then $f$ can be computed by fanin-2 formula of depth $D\leq k-1+\lceil\log\_2S\rceil$ (this follows from Theorem 6.2 in my book). Note that a trivial upper bound would only be $D\leq k\log S$ (if we would simulate each single gate by a tree of depth $\log S$).


---

