Randomized algorithms in some commutative and noncommutative domains[HBNI Th48]

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 NP-hard. 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 Ajtai-Kumar-Sivakumar 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 NP-hard for various metrics. Interestingly the author adapts Ajtai-Kumar-Sivakumar like sieving technique to give a singly exponential algorithm to compute a shortest non-identity 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 Raz-Shpilka 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 nonuniform-ModpL upperbound on the complexity.