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 full item record

Title: New Directions in Arithmetic and Boolean Circuit Complexity[HBNI Th 28]
Author: Srikanth Srinivasan
Advisor: Arvind, V.
Degree: Ph.D
Main Subjects: Computer Science
Institution: HBNI
Year: 2011
Pages: 103p.
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.
URI: http://hdl.handle.net/123456789/256

Files in this item

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

This item appears in the following Collection(s)

Show full item record

Search DSpace


Advanced Search

Browse

My Account