Can we count in depth $\frac{\lg n}{\lg \lg n}$?

Question

Can we compute an $n$-bit threshold gate by polynomial size (unbounded fan-in) circuits of depth $\frac{\lg n}{\lg \lg n}$? Alternatively, can we count the number of 1s in the input bits using these circuits?

Is $\mathsf{TC^0} \subseteq \mathsf{AltTime}(O(\frac{\lg n}{\lg \lg n}), O(\lg n))$?

---

Note that $\mathsf{TC^0} \subseteq \mathsf{NC^1} = \mathsf{ALogTime} = \mathsf{AltTime}(O(\lg n), O(\lg n))$. So the question is essentially asking if we can save a $\lg \lg n$ factor in the depth of circuits when computing threshold gates.

---

Edit:

As Kristoffer wrote in his answer we can save a $\lg \lg n$ factor. But can we save a little bit more? Can we replace $O(\frac{\lg n}{\lg \lg n})$ with $o(\frac{\lg n}{\lg \lg n})$?

It seems to me that the layered brute-force trick doesn't work for saving even $2 \lg \lg n$ (more generally any function in $\lg \lg n + \omega(1)$).

Answer 1

Consider a fanin 2 circuit of $C$ depth $O(\log n)$. Divide the layers of $C$ into $O(\log n/\log\log n)$ blocks each of $\log\log n$ consecutive layers. We now wish to replace each block by a depth 2 circuit. Namely, each gate in the last layer of a block depends on at most $2^{\log\log n} = \log n$ gates of the last layer in the block below. We can thus replace each gate in the last layer by a DNF of polynomial size with inputs being the gates in the last layer of the block below. Doing this for all gates in the last layers for all blocks and connecting these should yield the desired circuit.

Let me note this is essentially the best one can obtain: the switching lemma allows for lower bounds all the way to depth $\log n/ \log\log n$.