<p>Barrington's Theorem ought to get you poly-size depth-3 circuits for $NC^1$ with a top gate that's not too strange (multiplies 5 cycles). </p>

CC BY-SA 2.5
2010-10-21T02:22:08.800Z
I agree that Barrington's theorem implies something interesting here. But this output gate is a very "non-symmetric" function :)
Ryan Williams
CC BY-SA 2.5
2010-10-30T06:50:17.030Z
Actually it seems that you get a depth 1 circuit...  Representing a permutation as (say) a 5x5 Boolean matrix, it's just projections to the permutation-multiplication gate.
Noam
CC BY-SA 2.5
2010-10-21T02:15:45.150Z
2010-10-21T02:15:45.150Z
Lance Fortnow
<p>I don't know an answer, and am guessing it's an open question. There are very few known examples of such "surprising simulations" similar to Yao/Beigel-Tarui and Barrington. One thing along these lines that springs to mind is Valiant's result that for every $f:{0,1}^n\rightarrow{0,1}^n$ that can be computed by  $O(\log n)$-depth $O(n)$-size circuit, there exists $g$ in $NC_0[n^{\epsilon}]$ that agrees with $f$ on $2^{n-o(n)}$ inputs. (And if the circuit for $f$ uses only linear operations than so does the circuit for $g$, leading to the lower bounds / matrix rigidity connection). But unlike $NC^1$ this is about multiple-output functions, and also only for linear sized circuits. Note also that a <a href="http://www.cse.iitk.ac.in/users/manindra/algebra/depth-four.pdf">non-trivial reduction to depth 4</a> is known for arithmetic circuits.</p>

CC BY-SA 2.5
2010-10-31T16:41:22.963Z
Interestingly there is also a characterization of $TC^0$ in terms of arithmetic circuits: http://www.cse.iitk.ac.in/users/manindra/other/Constant-Depth-Arithmetic-Circuits.pdf
Kristoffer Arnsfelt Hansen
CC BY-SA 2.5
2010-10-31T16:46:40.313Z
The arithmetic circuit reduction to depth 4 is another good example. I know Valiant showed that you can cut $O(n/(\varepsilon \log \log n))$ wires of any linear size, log-depth circuit so that the remaining circuit has only $\varepsilon \log n$ depth. I guess this entails the "$g$ that agrees with $f$"?
Ryan Williams
CC BY-SA 2.5
2010-10-31T16:47:46.383Z
Kristoffer, can you add your link as a separate answer? Thanks!
Ryan Williams
CC BY-SA 2.5
2010-11-01T02:34:47.170Z
@Ryan Yes, by fixing these $o(n)$ wires to a typical value, we see that the remaining circuit (where every output depends on at most $n^{\epsilon}$ inputs) agrees with the original function on $2^{n-o(n)}$ inputs.
Boaz Barak
CC BY-SA 2.5
2010-10-31T02:42:46.363Z
2010-10-31T02:42:46.363Z
Boaz Barak
<p>Here is a slight expansion of my comment to the answer by Boaz. Agrawal, Allender and Datta in their paper <a href="http://www.cse.iitk.ac.in/users/manindra/other/Constant-Depth-Arithmetic-Circuits.pdf">On $TC^0$, $AC^0$, and Arithmetic Circuits</a> give a characterization of $TC^0$ in terms of arithmetic circuits. Namely, they show that a language $A$ is in $TC^0$ if and only there is a function $f$ in $\sharp AC^0$ and an integer $k$ such that</p>

<p>$x \in A$ if and only if $f(x) = 2^{|x|^k}$.</p>

<p>Note that $\sharp AC^0$ is a special form of constant depth arithmetic circuit over $Z$ (only constants 0 and 1 are allowed, and variable inputs can be $x_i$ or $1-x_i$).</p>

<p>Given that, as Boaz points out in his answer, there is a non-trivial depth reduction for arithmetic circuits, this might be something to look into.</p>

CC BY-SA 2.5
2010-10-31T19:07:29.467Z
2010-10-31T19:07:29.467Z
Kristoffer Arnsfelt Hansen
<p>This is a question about circuit complexity. (Definitions are at the bottom.)</p>

<p>Yao and Beigel-Tarui showed that every $ACC^0$ circuit family of size $s$ has an equivalent circuit family of size $s^{poly(\log s)}$ of depth <strong>two</strong>, where the output gate is a symmetric function and the second level consists of $AND$ gates of $poly(\log s)$ fan-in. This is a fairly remarkable "depth collapse" of a circuit family: from a depth 100 circuit you can reduce the depth to 2, with only a quasi-polynomial blowup (and one fancy but still restricted gate at the top).</p>

<p>My question: is there any known way to express a $TC^0$ circuit family, similarly? More ambitiously, what about an $NC^1$ circuit family? Potential answers would have the form: <em>"Every $TC^0$ circuit of size $s$ can be recognized by a depth-two family of size $f(s)$, where the output gate is a function of type $X$ and the second level of gates have type $Y$"</em>. </p>

<p>It doesn't <em>have</em> to be depth-two, any sort of fixed-depth result would be interesting. Proving that every $TC^0$ circuit can be represented in depth 3 by a circuit consisting of only symmetric function gates would be very interesting.</p>

<p>Some minor observations:</p>

<ol>
<li><p>If $f(n)=2^n$ the answer is trivial for <em>any</em> Boolean function (we can express any function as an $OR$ of $2^n$ $AND$s). For concreteness, let's require $f(n) = 2^{n^{o(1)}}$.</p></li>
<li><p>The answer is also trivial if either $X$ or $Y$ is allowed to be an arbitrary function computable in $TC^0$... :)
I'm obviously interested in "simpler" functions, whatever this means. It's a bit slippery to define because there are symmetric function families which are uncomputable. (There are unary languages which are uncomputable.) If you like, you may simply replace $X$ and $Y$ with symmetric functions in the statement, however I'd be interested in any other neat choices of gates.</p></li>
</ol>

<p>(Now for some brief recollections of notation: </p>

<p>$ACC^0$ is the class recognized by a family of unbounded fan-in constant-depth circuits with $AND$, $OR$, and $MOD_m$ gates for a constant $m > 1$ independent of the circuit size. A $MOD_m$ gate returns $1$ iff the sum of its inputs is divisible by $m$. </p>

<p>$TC^0$ is the class recognized by constant-depth circuits with $MAJORITY$ gates of unbounded fan-in.</p>

<p>$NC^1$ is the class recognized by logarithmic-depth circuits with $AND$, $OR$, $NOT$ gates of bounded fan-in.</p>

<p>It is known that $ACC^0 \subseteq TC^0 \subseteq NC^1$ when the circuit size is restricted to be polynomial in the number of inputs.)</p>

CC BY-SA 2.5
2010-10-21T12:47:19.497Z
Note that a polynomial size depth $k$ circuit consisting of symmetric gates can be computed by a polynomial size depth $k+1$ circuit consisting of MAJ gates. (Here as usual size is the number of wires). So basically you are asking if $TC^0$ can be depth reduced to itself?
Kristoffer Arnsfelt Hansen
CC BY-SA 2.5
2010-10-21T17:32:22.513Z
Yes, that's one way of looking at it! In general, I'm looking for any interesting fixed-depth simulations of $TC^0$ or $NC^1$.
Ryan Williams
CC BY-SA 2.5
2010-10-30T05:40:48.303Z
Ryan, I don't see what kind of answer you are seeking here.  If you are really talking about symmetric gates then (since these can be simulated by majority in depth two) your question is equivalent to the collapse of TC0 to constant depth (perhaps with some mild super-polynomial increase in size) -- a well known open problem.  If you are willing to "relax" symmetry, then Barrington's result seems as good as you can hope for?
Noam
CC BY-SA 2.5
2010-10-30T06:16:48.300Z
@Noam: I'd like to see if there are any other interesting answers; if there aren't, then I'll give the 300 to Lance. There are also intermediate possibilities, e.g. depth-three circuits with a symmetric function at the output but not necessarily symmetric on the other two layers. Anyway, getting you to think about it for 5 minutes is already worth the 300 bounty.
Ryan Williams
CC BY-SA 2.5
2010-11-10T08:54:34.293Z
And now (after Nov 8) we know the origin of this question...
slimton
<cc.complexity-theory><circuit-complexity><upper-bounds>
A fixed-depth characterization of $TC^0$? $NC^1$?
Ryan Williams
# A fixed-depth characterization of $TC^0$? $NC^1$?

(Asked by: username_0 on 2010-10-21)

This is a question about circuit complexity. (Definitions are at the bottom.)

Yao and Beigel-Tarui showed that every $ACC^0$ circuit family of size $s$ has an equivalent circuit family of size $s^{poly(\log s)}$ of depth **two**, where the output gate is a symmetric function and the second level consists of $AND$ gates of $poly(\log s)$ fan-in. This is a fairly remarkable "depth collapse" of a circuit family: from a depth 100 circuit you can reduce the depth to 2, with only a quasi-polynomial blowup (and one fancy but still restricted gate at the top).

My question: is there any known way to express a $TC^0$ circuit family, similarly? More ambitiously, what about an $NC^1$ circuit family? Potential answers would have the form: *"Every $TC^0$ circuit of size $s$ can be recognized by a depth-two family of size $f(s)$, where the output gate is a function of type $X$ and the second level of gates have type $Y$"*.

It doesn't *have* to be depth-two, any sort of fixed-depth result would be interesting. Proving that every $TC^0$ circuit can be represented in depth 3 by a circuit consisting of only symmetric function gates would be very interesting.

Some minor observations:

1. If $f(n)=2^n$ the answer is trivial for *any* Boolean function (we can express any function as an $OR$ of $2^n$ $AND$s). For concreteness, let's require $f(n) = 2^{n^{o(1)}}$.
2. The answer is also trivial if either $X$ or $Y$ is allowed to be an arbitrary function computable in $TC^0$... :)
   I'm obviously interested in "simpler" functions, whatever this means. It's a bit slippery to define because there are symmetric function families which are uncomputable. (There are unary languages which are uncomputable.) If you like, you may simply replace $X$ and $Y$ with symmetric functions in the statement, however I'd be interested in any other neat choices of gates.

(Now for some brief recollections of notation:

$ACC^0$ is the class recognized by a family of unbounded fan-in constant-depth circuits with $AND$, $OR$, and $MOD\_m$ gates for a constant $m > 1$ independent of the circuit size. A $MOD\_m$ gate returns $1$ iff the sum of its inputs is divisible by $m$.

$TC^0$ is the class recognized by constant-depth circuits with $MAJORITY$ gates of unbounded fan-in.

$NC^1$ is the class recognized by logarithmic-depth circuits with $AND$, $OR$, $NOT$ gates of bounded fan-in.

It is known that $ACC^0 \subseteq TC^0 \subseteq NC^1$ when the circuit size is restricted to be polynomial in the number of inputs.)

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

> **Comments:**
> **username_1**: Note that a polynomial size depth $k$ circuit consisting of symmetric gates can be computed by a polynomial size depth $k+1$ circuit consisting of MAJ gates. (Here as usual size is the number of wires). So basically you are asking if $TC^0$ can be depth reduced to itself?  
> **username_0**: Yes, that's one way of looking at it! In general, I'm looking for any interesting fixed-depth simulations of $TC^0$ or $NC^1$.  
> **username_2**: Ryan, I don't see what kind of answer you are seeking here.  If you are really talking about symmetric gates then (since these can be simulated by majority in depth two) your question is equivalent to the collapse of TC0 to constant depth (perhaps with some mild super-polynomial increase in size) -- a well known open problem.  If you are willing to "relax" symmetry, then Barrington's result seems as good as you can hope for?  
> **username_0**: @username_2: I'd like to see if there are any other interesting answers; if there aren't, then I'll give the 300 to Lance. There are also intermediate possibilities, e.g. depth-three circuits with a symmetric function at the output but not necessarily symmetric on the other two layers. Anyway, getting you to think about it for 5 minutes is already worth the 300 bounty.  
> **username_3**: And now (after Nov 8) we know the origin of this question...  

---

## 3 answers

### Answer by username_1 on 2010-10-31. Score: 17 | Accepted answer

Here is a slight expansion of my comment to the answer by Boaz. Agrawal, Allender and Datta in their paper [On $TC^0$, $AC^0$, and Arithmetic Circuits](http://www.cse.iitk.ac.in/users/manindra/other/Constant-Depth-Arithmetic-Circuits.pdf) give a characterization of $TC^0$ in terms of arithmetic circuits. Namely, they show that a language $A$ is in $TC^0$ if and only there is a function $f$ in $\sharp AC^0$ and an integer $k$ such that

$x \in A$ if and only if $f(x) = 2^{|x|^k}$.

Note that $\sharp AC^0$ is a special form of constant depth arithmetic circuit over $Z$ (only constants 0 and 1 are allowed, and variable inputs can be $x\_i$ or $1-x\_i$).

Given that, as Boaz points out in his answer, there is a non-trivial depth reduction for arithmetic circuits, this might be something to look into.


---

### Answer by username_4 on 2010-10-21. Score: 18

Barrington's Theorem ought to get you poly-size depth-3 circuits for $NC^1$ with a top gate that's not too strange (multiplies 5 cycles).

> **Comments:**
> **username_0**: I agree that Barrington's theorem implies something interesting here. But this output gate is a very "non-symmetric" function :)  
> **username_2**: Actually it seems that you get a depth 1 circuit...  Representing a permutation as (say) a 5x5 Boolean matrix, it's just projections to the permutation-multiplication gate.  

---

### Answer by username_5 on 2010-10-31. Score: 11

I don't know an answer, and am guessing it's an open question. There are very few known examples of such "surprising simulations" similar to Yao/Beigel-Tarui and Barrington. One thing along these lines that springs to mind is Valiant's result that for every $f:{0,1}^n\rightarrow{0,1}^n$ that can be computed by $O(\log n)$-depth $O(n)$-size circuit, there exists $g$ in $NC\_0[n^{\epsilon}]$ that agrees with $f$ on $2^{n-o(n)}$ inputs. (And if the circuit for $f$ uses only linear operations than so does the circuit for $g$, leading to the lower bounds / matrix rigidity connection). But unlike $NC^1$ this is about multiple-output functions, and also only for linear sized circuits. Note also that a [non-trivial reduction to depth 4](http://www.cse.iitk.ac.in/users/manindra/algebra/depth-four.pdf) is known for arithmetic circuits.

> **Comments:**
> **username_1**: Interestingly there is also a characterization of $TC^0$ in terms of arithmetic circuits: http://www.cse.iitk.ac.in/users/manindra/other/Constant-Depth-Arithmetic-Circuits.pdf  
> **username_0**: The arithmetic circuit reduction to depth 4 is another good example. I know Valiant showed that you can cut $O(n/(\varepsilon \log \log n))$ wires of any linear size, log-depth circuit so that the remaining circuit has only $\varepsilon \log n$ depth. I guess this entails the "$g$ that agrees with $f$"?  
> **username_0**: Kristoffer, can you add your link as a separate answer? Thanks!  
> **username_5**: @Ryan Yes, by fixing these $o(n)$ wires to a typical value, we see that the remaining circuit (where every output depends on at most $n^{\epsilon}$ inputs) agrees with the original function on $2^{n-o(n)}$ inputs.  

---

