18
$\begingroup$

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 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 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 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?

$\endgroup$
  • 5
    $\begingroup$ 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)$. $\endgroup$ – Stasys Aug 10 '11 at 14:29
  • 2
    $\begingroup$ 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$. $\endgroup$ – Stasys Aug 10 '11 at 14:38
  • 4
    $\begingroup$ 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. $\endgroup$ – Ryan O'Donnell Aug 10 '11 at 20:08
  • 2
    $\begingroup$ @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). $\endgroup$ – Stasys Aug 11 '11 at 8:20
  • 2
    $\begingroup$ @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. $\endgroup$ – Robin Kothari Aug 15 '11 at 22:05
11
+200
$\begingroup$

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

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