Srikanth Srinivasan
New Directions in Arithmetic and Boolean Circuit Complexity - 2011 - 103p.
2011
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.
Computer Science
Arithmetic Complexity Boolean Circuit complexity HBNI Th 28
HBNI Th 28
New Directions in Arithmetic and Boolean Circuit Complexity - 2011 - 103p.
2011
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.
Computer Science
Arithmetic Complexity Boolean Circuit complexity HBNI Th 28
HBNI Th 28