# Tag Info

15

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.

12

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

4

I am not sure about specifically depth-three lower bounds, but there has been a lot of depth-4 (and 5) lower bounds, usually assuming other constraints as well. For instance (and without any claim of exhaustivity): Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower Bounds for Depth-4 Formulas Computing Iterated Matrix ...

1

After re-reading Barrington et al., it seems that the case of $CC^0$ can be handled by using "group quantifiers", which allow for quantifiers to act over finite groups (i.e. $\mathbb{Z}/m\mathbb{Z}$) directly, while still using a binary representation under the hood so that the original definition of $DLOGTIME$-uniformity can still be used. With ...

Only top voted, non community-wiki answers of a minimum length are eligible