A fixed-depth characterization of $TC^0$? $NC^1$?

Question

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

Answer 1

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

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

Answer 3

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