ECCC-Report TR96-023https://eccc.weizmann.ac.il/report/1996/023Comments and Revisions published for TR96-023en-usWed, 26 Jun 1996 09:22:28 +0300
Comment 1
| A Trivial Modification Yields a More Interesting Theorem Comment on: TR96-023 |
Eric Allender
https://eccc.weizmann.ac.il/report/1996/023#comment1I show how to make use of the argument of TR96-023 to show
that the permanent requires large uniform constant-depth circuits.
Wed, 26 Jun 1996 09:22:28 +0300https://eccc.weizmann.ac.il/report/1996/023#comment1
Paper TR96-023
| A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy |
Eric Allender
https://eccc.weizmann.ac.il/report/1996/023A 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.
Fri, 22 Mar 1996 14:12:05 +0300https://eccc.weizmann.ac.il/report/1996/023