Most efficient way to convert an $\text{AC}^0$ circuit to a circuit (of any depth) with gate fanout 1

Question

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 Stasys Jukna and Ryan O'Donnell for partially answering the original question!)

---

Background:

Given an AC⁰ circuit with depth k and size S, there exists another AC⁰ 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 AC⁰ circuits to AC⁰ circuits with fanout 1? I read the following in Lecture 14 of Ryan O'Donnell's course notes:

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 AC⁰ circuit of size S and convert it to an AC⁰ 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 AC⁰ 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⁰ 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 AC⁰ 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 AC⁰ 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?

Answer 1

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