Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-017 | 8th February 2011 18:20

NEXP does not have non-uniform quasi-polynomial-size ACC circuits of o(loglog n) depth

RSS-Feed




TR11-017
Authors: Fengming Wang
Publication: 9th February 2011 11:37
Downloads: 4153
Keywords: 


Abstract:

$\mbox{ACC}_m$ circuits are circuits consisting of unbounded fan-in AND, OR and MOD_m gates and unary NOT gates, where m is a fixed integer. We show that there exists a language in non-deterministic exponential time which can not be computed by any non-uniform family of $\mbox{ACC}_m$ circuits of quasi-polynomial size and $o(\log \log n)$ depth, where m is an arbitrarily chosen constant.



ISSN 1433-8092 | Imprint