### Nonuniform ACC Circuit Lower BoundsNonuniform ACC Circuit Lower Bounds

Access Restriction
Subscribed

 Author Williams, Ryan Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2014 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword ACC ♦ Circuit complexity ♦ NEXP ♦ Lower bounds ♦ Satisfiability Abstract The class ACC consists of circuit families with constant depth over unbounded fan-in AND, OR, NOT, and $MOD_{m}$ gates, where $\textit{m}$ > 1 is an arbitrary constant. We prove the following. ---NEXP, the class of languages accepted in nondeterministic exponential time, does not have nonuniform ACC circuits of polynomial size. The size lower bound can be slightly strengthened to quasipolynomials and other less natural functions. $---E^{NP},$ the class of languages recognized in $2^{O(n)}$ time with an NP oracle, doesn’t have nonuniform ACC circuits of $2^{n}^{o(1)}$ size. The lower bound gives an exponential size-depth tradeoff: for every d, m there is a $\textit{Δ}$ > 0 such that $E^{NP}$ doesn’t have $depth-\textit{d}$ ACC circuits of size $2^{n}^{Δ}$ with $MOD_{m}$ gates. Previously, it was not known whether $EXP^{NP}$ had depth-3 polynomial-size circuits made out of only $MOD_{6}$ gates. The high-level strategy is to design faster algorithms for the circuit satisfiability problem over ACC circuits, then prove that such algorithms entail these lower bounds. The algorithms combine known properties of ACC with fast rectangular matrix multiplication and dynamic programming, while the second step requires a strengthening of the author’s prior work. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2014-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 61 Issue Number 1 Page Count 32 Starting Page 1 Ending Page 32

#### Open content in new tab

Source: ACM Digital Library