Abstract:

This thesis explores the computation complexity of some algebraic problems
in the commutative and the noncommutative setting. Motivation is to better understand the algorithmic questions in both the settings and to see the interplay between them. Also, the possibility of applying the
techniques and tools developed in the one model to the other is investigated. Specifically, this thesis focus on the computational complexity of the problems over integer lattices, permutation groups and arithmetic circuits. Algorithmic problems over integer lattices and permutation groups Shortest vector problem(SVP) and the closest vector problem(CVP) are two important problems
over integer lattices and their algorithmic complexity is a subject of extensive
research in the recent time due to advent of lattice based cryptosystems.
Both of these problems are known to be NPhard. Ajtai, Kumar and Sivakumar
in a breakthrough work gave a singly exponetial time randomized algorithm for
SVP and a singly exponential algorithm for solving CVP within factor of 1 + E
for any constant E > 0. Recently a new problem was introduced by Blömer and
Naewe called Subspace avoiding problem SAP to better understand the computational
complexity of CVP and SVP. Both of these problems are special cases of SAP. Given an integer lattice L of rank n and a subspace M in Rn of dimension k, the Subspace avoiding problem is to compute the length of a shortest vector in L \ M with respect to the concerned norm. In this thesis a new algorithm is given for SAP based on the AjtaiKumarSivakumar sieving technique which
performs better compared to Blömer and Naewe algorithm parameterized on the dimension k of the subspace concerned. Our algorithm works for metrics given by gauge functions which includes usual lp norms. Later give some applications of our algorithm to the CVP and the SVP problem.
Next, the computational complexity of two natural problems for metrics on permutation groups (which are nonabelian in general) given by generating sets, are investigated. These problems are exact analogue of closest vector problem and the shortest vector problem. These problems are also known to be NPhard for various metrics. Interestingly the author adapts AjtaiKumarSivakumar like sieving technique to give a singly exponential algorithm to compute a shortest nonidentity permutation in a given permutation group with respect to l(infinity) metric. Some of the results known for CVP and SVP to the permutation
group setting are extended, some of the results need a restriction on the group to be solvable(which are also nonabelian in general).
Monomial algebras and finite automata: In this part of the thesis the author studies arithmetic circuit and algebraic branching program size lower bound questions as
well as polynomial identity testing problem over monomial algebras both in the
noncommutative and the commutative setting. Main tool used here is basic automata
theory. The first result is extension of Nisan’s lower bound for the Permanent
and Determinant polynomials over free noncommutative algebra to the similar lower bound result over noncommutative monomial algebras. Furthermore, the RazShpilka deterministic identity test for noncommutative ABPs also carry over to monomial algebras. In the commutative setting, extends Jerrum and Snir’s 2(Omega(n)) size lower bound for monotone arithmetic circuits computing the nxn Permanent in the commutative polynomial ring to similar lower bound result over commutative monomial algebras. Next it investigates randomize parallel complexity of Monomial Search Problem which is a natural search version on the identity testing problem. The randomized(NC)2 upperbound on the complexity both in the commutative and noncommutative setting.
Hadamard product of polynomials, introduce and study the Hadamard product of the multivariate polynomials in the free noncommutative polynomial ring F{x1,x2, ..., xn}. This thesis explores arithmetic circuit and branching program complexity of the Hadamard product of polynomials when they are individually
given by arithmetic circuits and/or algebraic branching programs. It is shown
that the noncommutative branching program complexity of the Hadamard product
of polynomials given by ABPs is upper bounded by the product of the given
branching program sizes. Then apply this result to tightly classify the complexity
of identity testing problem for noncommutative ABPs over field of rationals.
It is shown that the problem is complete for logspace counting class C=L. The same problem is explored over finite fields and show nonuniformModpL
upperbound on the complexity. 