TY  - BOOK
AU  - Srikanth Srinivasan
TI  - New Directions in Arithmetic and Boolean Circuit Complexity
PY  - 2011///
KW  - Computer Science
KW  - Arithmetic Complexity
KW  - Boolean Circuit complexity
KW  - HBNI Th 28
N1  - 2011
N2  - Proving lower bounds has been a notoriously hard problem for Theoretical Computer Scientists.  The purpose of this thesis is to supplement the efforts in many theorems regarding lower bounds in restricted models of computation: namely, to point out some interesting new directions for lower bounds, and take some steps towards resolving these questions.                              *This thesis studies the question of proving lower bounds for constant-depth Boolean circuits with help functions and noncommutative Algebraic Branching Programs with help polynomials; of proving lower bounds for monotone arithmetic circuits of bounded width; and of proving lower bounds on the size of noncommutative arithmetic circuits computing the noncommutative determinant. These problems are introduced in greater detail and the corresponding results are stated
UR  - http://www.imsc.res.in/xmlui/handle/123456789/256
ER  -