New Directions in Arithmetic and Boolean Circuit Complexity[HBNI Th 28]

DSpace/Manakin Repository

New Directions in Arithmetic and Boolean Circuit Complexity[HBNI Th 28]

Show simple item record

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-08-24T10:08:01Z
dc.date.submitted 2011
dc.identifier.uri http://hdl.handle.net/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
dc.subject Arithmetic Complexity en_US
dc.subject Boolean Circuit complexity en_US
dc.subject HBNI Th 28 en_US
dc.title New Directions in Arithmetic and Boolean Circuit Complexity[HBNI Th 28] 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

Files in this item

Files Size Format View
SrikanthSrinivasan.pdf 829.7Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account