2 Permanent Member.pdfVIP

DIMACS Technical Report 97-51September 1997 The Permanent Requires Large Uniform ThresholdCircuits1byEric Allender2;3Department of Computer ScienceRutgers UniversityP.O. Box 1179Piscataway, NJ 08855-1179allender@cs.rutgers.edu.1A preliminary version of this work appeared in Proc. 2nd International Computing and Combina-torics Conference (COCOON 96).2Permanent Member3Supported in part by NSF grant CCR-9509603.DIMACS is a partnership of Rutgers University, Princeton University, ATT Labs, Bellcore,and Bell Labs.DIMACS is an NSF Science and Technology Center, funded under contract STC{91{19999;and also receives support from the New Jersey Commission on Science and Technology. ABSTRACTA recent paper by Caussinus, McKenzie, Therien, and Vollmer [CMTV96] shows that thereare problems in the counting hierarchy that require superpolynomial-size uniform TC0 cir-cuits. The proof in [CMTV96] uses \leaf languages as a tool in obtaining their separations,and their proof does not immediately yield larger lower bounds for the complexity of theseproblems, and it also does not yield a lower bound for any particular problem at any xedlevel 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 thecomplexity class C=P requires more than size T (n), if for all k, T (k)(n) = o(2n). Thus, inparticular, 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[CMTV96] showing that ACC0 is properly contained in ModPH. 1 Introduction1.1 Motivation and BackgroundThe central problem in complexity theory is the task of proving lower bounds on the com-plexity of specic problems. Circuit complexity, in particular the study of constant-depthcircuits, is one of the (few) areas where complexity theory has succeeded in actually pro-viding lower bounds, and even in the study o