DIMACS TR: 97-51
The Permanent Requires Large Uniform Threshold Circuits
Author: Eric Allender
ABSTRACT
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