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.
