Randomized algorithms in some commutative and noncommutative domains

Abstract

In this thesis we explore the computation complexity of some algebraic problems in the commutative and the noncommutative setting. Our motivation is to better understand the algorithmic questions in both the settings and to see the interplay between them. We also investigate the possibility of applying the techniques and tools developed in the one model to the other. Specifically, we 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 + _ for any constant _ gt 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 _ Rn of dimension k, the Subspace avoiding problem is to compute the length of a shortest vector in L n M with respect to the concerned norm. In this thesis we give a new algorithm 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 `p norms. Later we give some applications of our algorithm to the CVP and the SVP problem. Next we investigate the computational complexity of two natural problems for metrics on permutation groups (which are nonabelian in general) given by generatingsets.