19

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?

Robin Kothari
  • 13,617
  • 2
  • 60
  • 116
  • 5
    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 Aug 10 '11 at 14:29
  • 2
    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 Aug 10 '11 at 14:38
  • 4
    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 Aug 10 '11 at 20:08
  • 2
    @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 Aug 11 '11 at 08:20
  • @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 Aug 15 '11 at 21:50
  • 2
    @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 Aug 15 '11 at 22:05
  • @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 Aug 16 '11 at 18:48
  • @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 Aug 16 '11 at 19:10
  • @Robin: you are right, the depth is $O(D\log S)$, sorry. – Stasys Aug 16 '11 at 19:19
  • @Stasys: Alright. Thanks for the comments and the references. – Robin Kothari Aug 16 '11 at 19:36
  • 1
    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 Aug 23 '11 at 04:45
  • 2
    @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 Aug 23 '11 at 14:21
  • 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".] – Stasys Aug 28 '11 at 18:31
  • 1
    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 Aug 28 '11 at 19:01
  • 2
    @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 Aug 28 '11 at 20:08
  • 2
    @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 Aug 28 '11 at 21:22
  • 1
    @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 Aug 29 '11 at 00:18

1 Answers1

11

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

Stasys
  • 6,765
  • 29
  • 54