DIMACS TR: 97-51

The Permanent Requires Large Uniform Threshold Circuits

Author: Eric Allender


A recent paper by Caussinus, McKenzie, Therien, and Vollmer shows that there are problems in the counting hierarchy that require superpolynomial-size uniform TC^0 circuits. Their proof uses ``leaf languages'' as a tool in obtaining their separations, and 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 some level.) In this paper, we give a simple direct proof, showing that any problem that is hard for the complexity class C_=P requires more than size T(n), if for all k, T^{(k)}(n) = o(2^n). Thus, in particular, the permanent, and any problem hard for PP or #P require circuits of this size. Related and somewhat weaker lower bounds are also presented, extending the theorem of (Caussinus et al.) showing that ACC^0 is properly contained in ModPH.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-51.ps.gz
DIMACS Home Page