Skip to main content
3 of 3
Another TeX fix. \text is for actual text in a human language, not for mathematical symbols in an upright font.
Emil Jeřábek
  • 18.6k
  • 3
  • 64
  • 97

$\mathrm{AC}^0$ upper bound for Hamming weight

Consider Theorem 11 of this 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?