share
Theoretical Computer ScienceA fixed-depth characterization of $TC^0$? $NC^1$?
[+42] [3] Ryan Williams
[2010-10-21 01:18:09]
[ cc.complexity-theory circuit-complexity upper-bounds ]
[ https://cstheory.stackexchange.com/questions/2347/a-fixed-depth-characterization-of-tc0-nc1 ]

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

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
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
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
(3) @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
(5) And now (after Nov 8) we know the origin of this question... - slimton
[+18] [2010-10-21 02:15:45] Lance Fortnow

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


I agree that Barrington's theorem implies something interesting here. But this output gate is a very "non-symmetric" function :) - Ryan Williams
(3) 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
1
[+17] [2010-10-31 19:07:29] Kristoffer Arnsfelt Hansen [ACCEPTED]

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 [1] 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.

[1] http://www.cse.iitk.ac.in/users/manindra/other/Constant-Depth-Arithmetic-Circuits.pdf

2
[+11] [2010-10-31 02:42:46] Boaz Barak

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 [1] is known for arithmetic circuits.

[1] http://www.cse.iitk.ac.in/users/manindra/algebra/depth-four.pdf

(2) Interestingly there is also a characterization of $TC^0$ in terms of arithmetic circuits: cse.iitk.ac.in/users/manindra/other/… - Kristoffer Arnsfelt Hansen
(1) 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
Kristoffer, can you add your link as a separate answer? Thanks! - Ryan Williams
@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
3