dc.contributor.author |
Srikanth Srinivasan |
|
dc.date.accessioned |
2011-08-24T10:08:01Z |
|
dc.date.available |
2011-08-24T10:08:01Z |
|
dc.date.issued |
2011 |
|
dc.date.submitted |
2011 |
|
dc.identifier.uri |
https://dspace.imsc.res.in/xmlui/handle/123456789/256 |
|
dc.description.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. |
en_US |
dc.publisher.publisher |
The Institute of Mathematical Sciences |
|
dc.subject |
Arithmetic Complexity |
en_US |
dc.subject |
Boolean Circuit complexity |
en_US |
dc.subject |
HBNI Th28 |
en_US |
dc.title |
New Directions in Arithmetic and Boolean Circuit Complexity[HBNI Th28] |
en_US |
dc.type.degree |
Ph.D |
en_US |
dc.type.institution |
HBNI |
en_US |
dc.description.advisor |
Arvind, V. |
|
dc.description.pages |
103p. |
en_US |
dc.type.mainsub |
Computer Science |
en_US |
dc.type.hbnibos |
Mathematical Sciences |
|