<p>If I am not making a mistake, it seems that proving that the $\mathsf{TC^0_d}$ hierarchy does not collapse is at least as difficult as separating $\mathsf{NC^1}$ from $\mathsf{TC^0}$:</p>

<p>Let's denote the Boolean Formula Evaluation problem by $BFE$. $BFE$ is complete for $\mathsf{NC^1}$ under $\mathsf{AC^0}$ reductions.</p>

<p>By Manindra Agrawal, Eric Allender, and Steven Rudich, "<a href="http://ftp.cs.rutgers.edu/pub/allender/switch3.pdf">Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem</a>", 1999, $BFE$ is complete for $\mathsf{NC^1}$ under $\mathsf{AC^0_2}$ reductions. </p>

<p>Assume $\mathsf{NC^1}=\mathsf{TC^0}$. 
Then $BFE \in \mathsf{TC^0_d}$ for some $d$.
Therefore $\mathsf{NC^1} \subseteq \mathsf{TC^0_{d+2}}$.
Which means that $\mathsf{TC^0} \subseteq \mathsf{TC^0_{d+2}}$.</p>

<p>So for all $d$ we have</p>

<blockquote>
  <p>$\mathsf{TC^0} \not\subseteq \mathsf{TC^0_d}$ implies $\mathsf{NC^1} \not\subseteq \mathsf{TC^0_{d+2}}$ and $BFE \notin \mathsf{TC^0_d}$.</p>
</blockquote>

CC BY-SA 3.0
2013-06-11T21:22:43.933Z
2013-06-11T21:54:25.820Z
2013-06-11T21:54:25.820Z
Kaveh
<p>We know of no good lower bounds (meaning, say, a superpolynomial lower bound for a language in $\mathsf{NEXP}$) for depth 2 threshold circuits (unbounded weights). Depth 3 circuits built from majority gates, i.e. $\mathsf{TC}^0_3$ contains this class, and thus we know no good lower bounds for this class either.</p>

CC BY-SA 3.0
2013-07-24T13:38:59.797Z
@Dilworth, I think that is because it is defined using Majority not Threshold.
Kaveh
CC BY-SA 3.0
2013-06-11T21:46:26.597Z
This answers my question. Thank you Kristoffer.
Kaveh
CC BY-SA 3.0
2013-06-11T20:43:29.317Z
2013-06-11T20:43:29.317Z
Kristoffer Arnsfelt Hansen
<p>Do we know that the $\mathsf{TC^0}$ hierarchy does not collapse ($\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}$ for all $d$)?</p>

<p><a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aT#tc0">The Zoo entry for $\mathsf{TC^0}$</a> only mentions the separation between depth 2 and 3.</p>

<p>Also is there a standard reference for the fact that $\mathsf{AC^0_d}$ hierarchy does not collapse?</p>

CC BY-SA 3.0
2013-07-24T13:36:20.913Z
@Dilworth, nonuniform. Counting doesn't seem to work, otherwise as I noted below we could then separate $\mathsf{TC^0}$ from $\mathsf{NC^1}$ which is open.
Kaveh
CC BY-SA 3.0
2013-06-11T18:34:02.643Z
A related question would be, how many distinct functions are there in $AC_d^0$ / $TC_d^0$ ? A reasonable lower bound on these quantities would answer your questions. Also a proof of tightness for Hastad's switching lemma would perhaps answer your second question.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-06-11T19:03:55.557Z
For the second question, I believe it was first proved in [Sipser's STOC '83 paper "Borel sets and circuit complexity"](http://dl.acm.org/citation.cfm?id=808733). This only gives super-polynomial lower bounds though. The first exponential lower bounds were given by Yao, later improved by Håstad.
Robin Kothari
CC BY-SA 3.0
2013-06-11T21:34:45.080Z
@MCH, did you mean to write $\mathsf{TC^0_d}/\mathsf{AC^0_d}$? Or do you mean the number of equivalence classes of problems in $\mathsf{TC^0_d}$ w.r.t. $\mathsf{AC^0_d}$ reductions?
Kaveh
CC BY-SA 3.0
2013-06-12T17:53:41.937Z
What I mean is very simple: How many distinct functions can the class of $AC_d^0$ circuits of size $s$ represent? (We can estimate the number of circuits very easily but we should be careful that some of them may compute the same function.) Once you show that this quantity grows with $d$, you are done.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-06-12T19:24:26.867Z
@MCH, the / confused me. :)
Kaveh
<cc.complexity-theory><reference-request><complexity-classes><circuit-complexity><bounded-depth>
Does the $\mathsf{TC^0}$ hierarchy collapse?
Kaveh
# Does the $\mathsf{TC^0}$ hierarchy collapse?

(Asked by: username_0 on 2013-06-11)

Do we know that the $\mathsf{TC^0}$ hierarchy does not collapse ($\mathsf{TC^0\_d} \subsetneq \mathsf{TC^0\_{d+1}}$ for all $d$)?

[The Zoo entry for $\mathsf{TC^0}$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aT#tc0) only mentions the separation between depth 2 and 3.

Also is there a standard reference for the fact that $\mathsf{AC^0\_d}$ hierarchy does not collapse?

**Tags:** cc.complexity-theory, reference-request, complexity-classes, circuit-complexity, bounded-depth

> **Comments:**
> **username_1**: A related question would be, how many distinct functions are there in $AC_d^0$ / $TC_d^0$ ? A reasonable lower bound on these quantities would answer your questions. Also a proof of tightness for Hastad's switching lemma would perhaps answer your second question.  
> **username_2**: For the second question, I believe it was first proved in [Sipser's STOC '83 paper "Borel sets and circuit complexity"](http://dl.acm.org/citation.cfm?id=808733). This only gives super-polynomial lower bounds though. The first exponential lower bounds were given by Yao, later improved by Håstad.  
> **username_0**: @MCH, did you mean to write $\mathsf{TC^0_d}/\mathsf{AC^0_d}$? Or do you mean the number of equivalence classes of problems in $\mathsf{TC^0_d}$ w.r.t. $\mathsf{AC^0_d}$ reductions?  
> **username_1**: What I mean is very simple: How many distinct functions can the class of $AC_d^0$ circuits of size $s$ represent? (We can estimate the number of circuits very easily but we should be careful that some of them may compute the same function.) Once you show that this quantity grows with $d$, you are done.  
> **username_0**: @MCH, the / confused me. :)  
> **username_0**: @Dilworth, nonuniform. Counting doesn't seem to work, otherwise as I noted below we could then separate $\mathsf{TC^0}$ from $\mathsf{NC^1}$ which is open.  

---

## 2 answers

### Answer by username_3 on 2013-06-11. Score: 16 | Accepted answer

We know of no good lower bounds (meaning, say, a superpolynomial lower bound for a language in $\mathsf{NEXP}$) for depth 2 threshold circuits (unbounded weights). Depth 3 circuits built from majority gates, i.e. $\mathsf{TC}^0\_3$ contains this class, and thus we know no good lower bounds for this class either.

> **Comments:**
> **username_0**: This answers my question. Thank you Kristoffer.  
> **username_0**: @Dilworth, I think that is because it is defined using Majority not Threshold.  

---

### Answer by username_0 on 2013-06-11. Score: 13

If I am not making a mistake, it seems that proving that the $\mathsf{TC^0\_d}$ hierarchy does not collapse is at least as difficult as separating $\mathsf{NC^1}$ from $\mathsf{TC^0}$:

Let's denote the Boolean Formula Evaluation problem by $BFE$. $BFE$ is complete for $\mathsf{NC^1}$ under $\mathsf{AC^0}$ reductions.

By Manindra Agrawal, Eric Allender, and Steven Rudich, "[Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem](http://ftp.cs.rutgers.edu/pub/allender/switch3.pdf)", 1999, $BFE$ is complete for $\mathsf{NC^1}$ under $\mathsf{AC^0\_2}$ reductions.

Assume $\mathsf{NC^1}=\mathsf{TC^0}$.
Then $BFE \in \mathsf{TC^0\_d}$ for some $d$.
Therefore $\mathsf{NC^1} \subseteq \mathsf{TC^0\_{d+2}}$.
Which means that $\mathsf{TC^0} \subseteq \mathsf{TC^0\_{d+2}}$.

So for all $d$ we have

> $\mathsf{TC^0} \not\subseteq \mathsf{TC^0\_d}$ implies $\mathsf{NC^1} \not\subseteq \mathsf{TC^0\_{d+2}}$ and $BFE \notin \mathsf{TC^0\_d}$.


---

