19
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ I modified my answer to also include the latest edit. $\endgroup$ – Kristoffer Arnsfelt Hansen Oct 9 '12 at 15:49
22
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Thanks Kristoffer. I added a slightly stronger question. $\endgroup$ – Kaveh Oct 9 '12 at 15:00
  • 2
    $\begingroup$ Just to make sure I get the big picture correctly: up to depth $\lg n / \lg \lg n$ these circuits cannot compute parity, at this depth they suddenly become capable of computing $\mathsf{NC^1}$. $\endgroup$ – Kaveh Oct 9 '12 at 15:56
  • 2
    $\begingroup$ That's right (upto constant factors in the depth). $\endgroup$ – Kristoffer Arnsfelt Hansen Oct 9 '12 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.