On Structure and Lower Bounds in Restricted Models of Arithmetic Computations[HBNI Th118]

DSpace/Manakin Repository

On Structure and Lower Bounds in Restricted Models of Arithmetic Computations[HBNI Th118]

Show simple item record

dc.contributor.author Raja, S.
dc.date.accessioned 2017-06-09T05:47:02Z
dc.date.available 2017-06-09T05:47:02Z
dc.date.issued 2017-06-09T05:47:02Z
dc.date.submitted 2017
dc.identifier.uri http://hdl.handle.net/123456789/405
dc.description.abstract In this thesis some restricted models of arithmetic computation are explored. The main results obtained are summarized below: 1. Depth reduction and lower bound questions for set-multilinear computational models are studied. It turns out that set-multilinear arithmetic circuits can be efficiently depth reduced. Furthermore, lower bounds are shown for set-multilinear algebraic branching programs of restricted type-width computing an explicit p-family. This yields lower bounds for sums of read-once oblivious branching programs (ROABPs). 2. The structure of the noncommutative Valiant classes, called VP nc and VNP nc, is explored. The results obtained include finding natural complete problems for the class VPnc based on the well-known Chomsky-Schutzenberger theorem in formal language theory. Assuming (VP nc) Not equal to (VNP nc), a family in VNP nc is obtained that is neither in VP nc nor VNP nc-complete. 3. Multiplicative circuits and linear circuits over noncommutative domains are considered. Lower bounds on the size of multiplicative circuits computing a multi- output function over various noncommutative domains are obtained. An explicit matrix A is constructed, with entries from the noncommutative ring F(x1 , x2), such that there is no linear circuit computing Ay of size O(n) and depth O(logn). This is shown by suitably generalizing the matrix rigidity method of Valiant. en_US
dc.publisher.publisher
dc.subject Arithmetic Computations en_US
dc.subject Lower Bounds en_US
dc.subject Computational Complexity Theory en_US
dc.subject Arithmetic Circuit Complexity Theory en_US
dc.subject HBNI Th118 en_US
dc.title On Structure and Lower Bounds in Restricted Models of Arithmetic Computations[HBNI Th118] en_US
dc.type.degree Ph.D en_US
dc.type.institution HBNI en_US
dc.description.advisor Arvind, V.
dc.description.pages 150p. en_US
dc.type.mainsub Computer Science en_US

Files in this item

Files Size Format View
HBNI Th118.pdf 507.8Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account