Abstract
A very recent paper by Caussinus, McKenzie, Thérien, and Vollmer [CMTV95] shows that ACC0 is properly contained in ModPH, and TC0 is properly contained in the counting hierarchy. Thus, [CMTV95] shows that there are problems in ModPH that require superpolynomialsize uniform ACC0 circuits, and problems in the counting hierarchy that require superpolynomial-size uniform TC0 circuits. The proof in [CMTV95] 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. In this paper, we give a simple direct proof of these same separations, and use it to provide “sub-subexponential” size lower bounds on the size of uniform circuits for these problems.