RUcore Resource Object
RUcore Resource Object
PDF-1(512.38 KB)
TitleOn circuit complexity classes and iterated matrix multiplication
NameWang, Fengming (author), Allender, Eric (chair), Saks, Michael (internal member), Szegedy, Mario (internal member), Impagliazzo, Russell (outside member), Rutgers University, Graduate School - New Brunswick,
Degree Date2012-01
Date Created2012
SubjectComputer Science,
Programming languages (Electronic computers),
Cellular automata
DescriptionIn 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.
NotePh. D.
NoteIncludes bibliographical references
NoteIncludes vita
Noteby Fengming Wang
Genretheses
Persistent URLhttp://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000064183
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.