Published by MIT Press. Copyright 1999 Massachusetts Institute of Technology.

Your institution may already be a
subscriber to CJTCS. If not,
**please subscribe**.

We show that the permanent cannot be computed by uniform constant-depth threshold circuits of size T(n) for any function T such that for all k, T^(k)(n) = o(2^n). More generally, we show that any problem that is hard for the complexity class C_=P requires circuits of this size (on the uniform constant-depth threshold circuit model). In particular, this lower bound applies to any problem that is hard for the complexity classes PP or #P.

This extends a
recent result by Caussinus, McKenzie, Therien, and Vollmer,
showing that there are problems in
the counting hierarchy that require superpolynomial-size uniform TC0
circuits. Their
proof uses ``leaf languages'' as a tool in obtaining their
separations. Their proof does not immediately yield larger lower bounds
for the complexity of these problems, and it also does not yield a lower
bound for any particular problem at any fixed level of the counting
hierarchy. (It only shows that hard problems must exist at

We also present related and somewhat weaker lower bounds, extending the theorem of Caussinus et al. showing that ACC^0 is properly contained in ModPH.

- Preformatted versions of the article
- DVI (62,392 bytes)
**PostScript**(314,969 bytes)- PDF (283,471 bytes)
- Audio by
**AsTeR**(to appear)

- Source materials for custom formatting
**LaTeX**(`cj99-07.tex`, 41,343 bytes)**BIBTeX**(`cj99-07.bib`, 9,247 bytes)- Parameter settings for custom
formatting (
`cjropts.tex`, 165 bytes) - Self citation in
**BIBTeX**(302 bytes)

- Online discussion
- Instructions for Readers

DOI: 10.4086/cjtcs.1999.007

Article 6 Article 8

Volume 1999 Published articles

Article 6 Article 8

Volume 1999 Published articles

Last modified: Sat Mar 20 09:32:31 CST 1999