<p>Yes, the bound is essentially tight. The following is a straightforward construction of depth-<span class="math-container">$d$</span> Majority circuits of size
<span class="math-container">$$2^{(1-d^{-1})(n^{1/(d-1)}+O(1))\log n}\le2^{n^{1/(d-1)}\log n}=n^{n^{1/(d-1)}}.$$</span>
It works even for nonconstant <span class="math-container">$d$</span>, up to <span class="math-container">$d\le\log n$</span> or so (at which point the bound becomes polynomial in <span class="math-container">$n$</span>). We will compute more generally the Hamming weight function <span class="math-container">$h\colon\{0,1\}^n\to\{0,1\}^{\log n}$</span>, with result represented in binary in such a way that the most significant bit gives Majority.</p>
<p>Thinking of <span class="math-container">$h(x_0,\dots,x_{n-1})$</span> as <span class="math-container">$\sum_{i&lt;n}x_i$</span>, we arrange the sum into a depth-<span class="math-container">$d$</span> <span class="math-container">$\lceil n^{1/(d-1)}\rceil$</span>-ary tree (i.e., with <span class="math-container">$d-1$</span> layers of inner nodes computing <span class="math-container">$\lceil n^{1/(d-1)}\rceil$</span>-ary sums, and a bottom layer of leaves attached to the original inputs). The sums computed at each node are functions with <span class="math-container">$\lceil n^{1/(d-1)}\rceil$</span> inputs of at most <span class="math-container">$(1-d^{-1})\log n$</span> bits each, and at most <span class="math-container">$\log n$</span> output bits. Since any function <span class="math-container">$\{0,1\}^m\to\{0,1\}^k$</span> has depth-<span class="math-container">$2$</span> circuits (CNF or DNF) of size <span class="math-container">$2^m+k$</span>, we obtain a circuit computing Hamming weight (and Majority) of size
<span class="math-container">$$n^{O(1)}2^{(1-d^{-1})\lceil n^{1/(d-1)}\rceil\log n}=2^{(1-d^{-1})(n^{1/(d-1)}+O(1))\log n}$$</span>
as claimed, of depth <span class="math-container">$O(d)$</span>.</p>
<p>In order to make the depth exactly <span class="math-container">$d$</span>, we can use double-rail logic to avoid negations in the depth-<span class="math-container">$2$</span> subcircuits (i.e., in parallel with each of the intermediate output nodes, we separately compute its negation), and then express the functions computed on even layers of the tree using CNF, and on odd layers using DNF. This allows us to merge the top gates on each layer (except for the final output) with the bottom gates on the next layer. Thus, we reduce the depth of the resulting circuit from <span class="math-container">$2(d-1)$</span> to <span class="math-container">$(d-2)+2=d$</span>.</p>
<hr />
<p>Actually, since the question only asks for distinguishing strings of Hamming weight <span class="math-container">$n/2$</span> from <span class="math-container">$n/2+1$</span>, this does not require computing Majority—it can be accomplished with Parity. Then the bound above can be simplified: we only need to compute sums modulo <span class="math-container">$2$</span> at each node in the tree, which is a function <span class="math-container">$\{0,1\}^{n^{1/(d-1)}}\to\{0,1\}$</span>, thus overall the same strategy gives depth-<span class="math-container">$d$</span> Parity circuits of size
<span class="math-container">$$n2^{n^{1/(d-1)}},$$</span>
matching even more closely the lower bound. The same argument also gives depth-<span class="math-container">$d$</span> circuits of size <span class="math-container">$2^{O(n^{1/(d-1)})}$</span> for the <span class="math-container">$\mathrm{MOD}_k$</span> functions for any constant <span class="math-container">$k$</span>.</p>

CC BY-SA 4.0
2022-05-03T10:08:44.357Z
2022-05-03T11:05:13.543Z
2022-05-03T11:05:13.543Z
Emil Jeřábek
<p>Consider Theorem 11 of <a href="https://arxiv.org/abs/0910.4698" rel="nofollow noreferrer">this</a> paper (S. Aaronson, BQP and the Polynomial Hierarchy), which says:</p>
<blockquote>
<p>Any depth <span class="math-container">$d$</span> circuit that accepts all <span class="math-container">$n$</span> bit strings of Hamming
weight <span class="math-container">$\frac{n}{2} + 1$</span> and rejects all strings of Hamming weight
<span class="math-container">$\frac{n}{2}$</span> has size <span class="math-container">$\exp[\Omega(n^{1/(d-1)})]$</span>.</p>
</blockquote>
<p>Is there a matching upper bound to the given lower bound for the same problem?</p>

<cc.complexity-theory><circuit-complexity><circuit-families><ac0>
$\mathrm{AC}^0$ upper bound for Hamming weight
AngryLion
# $\mathrm{AC}^0$ upper bound for Hamming weight

(Asked by: username_0 on 2022-05-03)

Consider Theorem 11 of [this](https://arxiv.org/abs/0910.4698) paper (S. Aaronson, BQP and the Polynomial Hierarchy), which says:

> Any depth $d$ circuit that accepts all $n$ bit strings of Hamming
> weight $\frac{n}{2} + 1$ and rejects all strings of Hamming weight
> $\frac{n}{2}$ has size $\exp[\Omega(n^{1/(d-1)})]$.

Is there a matching upper bound to the given lower bound for the same problem?

**Tags:** cc.complexity-theory, circuit-complexity, circuit-families, ac0

---

## 1 answers

### Answer by username_1 on 2022-05-03. Score: 2 | Accepted answer

Yes, the bound is essentially tight. The following is a straightforward construction of depth-$d$ Majority circuits of size
$$2^{(1-d^{-1})(n^{1/(d-1)}+O(1))\log n}\le2^{n^{1/(d-1)}\log n}=n^{n^{1/(d-1)}}.$$
It works even for nonconstant $d$, up to $d\le\log n$ or so (at which point the bound becomes polynomial in $n$). We will compute more generally the Hamming weight function $h\colon\{0,1\}^n\to\{0,1\}^{\log n}$, with result represented in binary in such a way that the most significant bit gives Majority.

Thinking of $h(x\_0,\dots,x\_{n-1})$ as $\sum\_{i, we arrange the sum into a depth-$d$ $\lceil n^{1/(d-1)}\rceil$-ary tree (i.e., with $d-1$ layers of inner nodes computing $\lceil n^{1/(d-1)}\rceil$-ary sums, and a bottom layer of leaves attached to the original inputs). The sums computed at each node are functions with $\lceil n^{1/(d-1)}\rceil$ inputs of at most $(1-d^{-1})\log n$ bits each, and at most $\log n$ output bits. Since any function $\{0,1\}^m\to\{0,1\}^k$ has depth-$2$ circuits (CNF or DNF) of size $2^m+k$, we obtain a circuit computing Hamming weight (and Majority) of size
$$n^{O(1)}2^{(1-d^{-1})\lceil n^{1/(d-1)}\rceil\log n}=2^{(1-d^{-1})(n^{1/(d-1)}+O(1))\log n}$$
as claimed, of depth $O(d)$.

In order to make the depth exactly $d$, we can use double-rail logic to avoid negations in the depth-$2$ subcircuits (i.e., in parallel with each of the intermediate output nodes, we separately compute its negation), and then express the functions computed on even layers of the tree using CNF, and on odd layers using DNF. This allows us to merge the top gates on each layer (except for the final output) with the bottom gates on the next layer. Thus, we reduce the depth of the resulting circuit from $2(d-1)$ to $(d-2)+2=d$.

---

Actually, since the question only asks for distinguishing strings of Hamming weight $n/2$ from $n/2+1$, this does not require computing Majority—it can be accomplished with Parity. Then the bound above can be simplified: we only need to compute sums modulo $2$ at each node in the tree, which is a function $\{0,1\}^{n^{1/(d-1)}}\to\{0,1\}$, thus overall the same strategy gives depth-$d$ Parity circuits of size
$$n2^{n^{1/(d-1)}},$$
matching even more closely the lower bound. The same argument also gives depth-$d$ circuits of size $2^{O(n^{1/(d-1)})}$ for the $\mathrm{MOD}\_k$ functions for any constant $k$.


---

