Skip to main content
Tweeted twitter.com/StackCSTheory/status/1521686114360246274
Another TeX fix. \text is for actual text in a human language, not for mathematical symbols in an upright font.
Link
Emil Jeřábek
  • 18.6k
  • 3
  • 64
  • 97

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

Don't link directly to a pdf, but to an informative meta page. Better, include a proper reference. Also, fix TeX abuse.
Source Link
Emil Jeřábek
  • 18.6k
  • 3
  • 64
  • 97

Consider Theorem $11$11 of thisthis 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 $\text{exp}[\Omega(n^{1/(d-1)})].$$\exp[\Omega(n^{1/(d-1)})]$.

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

Consider Theorem $11$ of this paper, 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 $\text{exp}[\Omega(n^{1/(d-1)})].$

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

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?

Source Link

$\text{AC}[0]$ upper bound for Hamming weight

Consider Theorem $11$ of this paper, 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 $\text{exp}[\Omega(n^{1/(d-1)})].$

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