Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-023 | 21st March 1996 00:00

A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy


Authors: Eric Allender
Publication: 22nd March 1996 14:12
Downloads: 1124


A very recent paper by Caussinus, McKenzie, Therien, and Vollmer
[CMTV] shows that ACC^0 is properly contained in ModPH, and TC^0
is properly contained in the counting hierarchy. Thus, [CMTV] shows
that there are problems in ModPH that require superpolynomial-size
uniform ACC^0 circuits, and problems in the counting hierarchy that
require superpolynomial-size uniform TC^0 circuits. The proof in
[CMTV] 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.


Comment #1 to TR96-023 | 26th June 1996 09:22

A Trivial Modification Yields a More Interesting Theorem Comment on: TR96-023

Comment #1
Authors: Eric Allender
Accepted on: 26th June 1996 09:22
Downloads: 1105


I show how to make use of the argument of TR96-023 to show
that the permanent requires large uniform constant-depth circuits.

ISSN 1433-8092 | Imprint