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

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

CC BY-SA 3.0
2012-10-09T15:00:44.707Z
Thanks Kristoffer. I added a slightly stronger question.
Kaveh
CC BY-SA 3.0
2012-10-09T15:56:45.010Z
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}$.
Kaveh
CC BY-SA 3.0
2012-10-09T15:58:15.650Z
That's right (upto constant factors in the depth).
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2012-10-09T09:26:06.263Z
2012-10-09T15:49:47.797Z
2012-10-09T15:49:47.797Z
Kristoffer Arnsfelt Hansen
<p>Can we compute an <span class="math-container">$n$</span>-bit threshold gate by polynomial size (unbounded fan-in) circuits of depth <span class="math-container">$\frac{\lg n}{\lg \lg n}$</span>? Alternatively, can we count the number of 1s in the input bits using these circuits?</p>
<p>Is <span class="math-container">$\mathsf{TC^0} \subseteq \mathsf{AltTime}(O(\frac{\lg n}{\lg  \lg n}), O(\lg n))$</span>?</p>
<hr />
<p>Note that <span class="math-container">$\mathsf{TC^0} \subseteq \mathsf{NC^1} = \mathsf{ALogTime} = \mathsf{AltTime}(O(\lg n), O(\lg n))$</span>. So the question is essentially asking if we can save a <span class="math-container">$\lg \lg n$</span> factor in the depth of circuits when computing threshold gates.</p>
<hr />
<h3>Edit:</h3>
<p>As Kristoffer wrote in his answer we can save a <span class="math-container">$\lg \lg n$</span> factor. But can we save a little bit more? Can we replace <span class="math-container">$O(\frac{\lg n}{\lg \lg n})$</span> with <span class="math-container">$o(\frac{\lg n}{\lg \lg n})$</span>?</p>
<p>It seems to me that the layered brute-force trick doesn't work for saving even <span class="math-container">$2 \lg \lg n$</span> (more generally any function in <span class="math-container">$\lg \lg n + \omega(1)$</span>).</p>

CC BY-SA 3.0
2012-10-09T15:49:23.803Z
I modified my answer to also include the latest edit.
Kristoffer Arnsfelt Hansen
<cc.complexity-theory><circuit-complexity><circuit-depth>
Can we count in depth $\frac{\lg n}{\lg \lg n}$?
Kaveh
# Can we count in depth $\frac{\lg n}{\lg \lg n}$?

(Asked by: username_0 on 2012-10-09)

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

**Tags:** cc.complexity-theory, circuit-complexity, circuit-depth
> **Comments:**
> **username_1**: I modified my answer to also include the latest edit.  

---

## 1 answers

### Answer by username_1 on 2012-10-09. Score: 22 | Accepted answer

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

> **Comments:**
> **username_0**: Thanks Kristoffer. I added a slightly stronger question.  
> **username_0**: 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}$.  
> **username_1**: That's right (upto constant factors in the depth).  

---

