New Directions in Arithmetic and Boolean Circuit Complexity
Material type:
TextPublication details: 2011Description: 103pSubject(s): Computer Science | Arithmetic Complexity | Boolean Circuit complexity | HBNI Th 28Online resources: Click here to access online Dissertation note: 2011Ph.DHBNI Abstract: 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.
THESIS & DISSERTATION
| Current library | Home library | Call number | Materials specified | URL | Status | Date due | Barcode |
|---|---|---|---|---|---|---|---|
| IMSc Library | IMSc Library | HBNI Th 28 (Browse shelf (Opens below)) | Link to resource | Available | 64968 |
2011
Ph.D
HBNI
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.
There are no comments on this title.