TY - JOUR
TI - On circuit complexity classes and iterated matrix multiplication
DO - https://doi.org/doi:10.7282/T35D8QVQ
PY - 2012
AB - In this thesis, we study small, yet important, circuit complexity classes within NC^1, such as ACC^0 and TC^0. We also investigate the power of a closely related problem called Iterated Matrix Multiplication and its implications in low levels of algebraic complexity theory. More concretely, 1. We show that extremely modest-sounding lower bounds for certain problems can lead to non-trivial derandomization results. a. If the word problem over S_5 requires constant-depth threshold circuits of size n^{1+epsilon} for some epsilon > 0, then any language accepted by uniform polynomial-size probabilistic threshold circuits can be solved in subexponential time (and more strongly, can be accepted by a uniform family of deterministic constant-depth threshold circuits of subexponential size.) b. If there are no constant-depth arithmetic circuits of size n^{1+epsilon} for the problem of multiplying a sequence of n 3-by-3 matrices, then for every constant d, black-box identity testing for depth-d arithmetic circuits with bounded individual degree can be performed in subexponential time (and even by a uniform family of deterministic constant-depth AC circuits of subexponential size). 2. 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 ACC_m circuits of quasi-polynomial size and o(loglog n) depth, where $m$ is an arbitrarily chosen constant. 3. We show that there are families of polynomials having small depth-two arithmetic circuits that cannot be expressed by algebraic branching programs of width two. This clarifies the complexity of the problem of computing the product of a sequence of two-by-two matrices, which arises in several settings.
KW - Computer Science
KW - Programming languages (Electronic computers)
KW - Cellular automata
LA - eng
ER -