Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with ACC:
TR96-023 | 21st March 1996
Eric Allender

A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy

Comments: 1

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 ... more >>>

TR17-188 | 22nd December 2017
Cody Murray, Ryan Williams

Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP

We prove that if every problem in $NP$ has $n^k$-size circuits for a fixed constant $k$, then for every $NP$-verifier and every yes-instance $x$ of length $n$ for that verifier, the verifier's search space has an $n^{O(k^3)}$-size witness circuit: a witness for $x$ that can be encoded with a circuit ... more >>>

ISSN 1433-8092 | Imprint