Access Restriction

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

   Open content in new tab
Source: ACM Digital Library