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

Title: On Structure and Lower Bounds in Restricted Models of Arithmetic Computations[HBNI Th118]
Author: Raja, S.
Advisor: Arvind, V.
Degree: Ph.D
Main Subjects: Computer Science
Institution: HBNI
Year: 2017
Pages: 150p.
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.
URI: http://hdl.handle.net/123456789/405

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

Search DSpace


Advanced Search

Browse

My Account