2
$\begingroup$

The Complexity Zoo states that ACC$^0$ is contained in TC$^0$ and links to the paper On ACC and Threshold Circuits. However, what the linked paper proves is that depth-3 threshold circuits of quasipolynomial size can simulate ACC$^0$ circuits.

Wouldn't it be necessary to prove that constant depth threshold circuits of polynomial size simulate them rather than quasipolynomial? Is it obvious how to do the simulation with just a polynomial number of gates?

$\endgroup$

1 Answer 1

1
$\begingroup$

You can show directly how to simulate a polynomial fan-in modular gate using polynomially many threshold gates. The idea is that given inputs $x_1,\ldots,x_m$, you can use two threshold gates and an AND gate to determine whether $x_1 + \cdots + x_m = w$ for any $w$. Taking at most $m+1$ copies of this gadget and ORing them, we can simulate a single modular gate.

$\endgroup$
2
  • $\begingroup$ Is there a paper that fills in the details of how to perform the construction you described? $\endgroup$ Dec 18, 2017 at 14:36
  • $\begingroup$ It's at the level of an exercise. Perhaps you can find it in textbooks. $\endgroup$ Dec 18, 2017 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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