Please use this identifier to cite or link to this item: http://hdl.handle.net/10603/4734
Title: Randomized algorithms in some commutative and noncommutative domains
Researcher: Joglekar, Pushkar S
Guide(s): Arvind, V
Keywords: Sieving Algorithms
Mathematics
Upload Date: 24-Sep-2012
University: Homi Bhabha National Institute
Completed Date: February-2011
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.
Pagination: 98p.
URI: http://hdl.handle.net/10603/4734
Appears in Departments:Department of Mathematical Sciences

Files in This Item:
File Description SizeFormat 
01_title.pdfAttached File88.77 kBAdobe PDFView/Open
02_certificate.pdf52.06 kBAdobe PDFView/Open
03_declaration.pdf43.29 kBAdobe PDFView/Open
04_acknowledgements.pdf46.34 kBAdobe PDFView/Open
05_abstract.pdf154.17 kBAdobe PDFView/Open
06_contents.pdf98.08 kBAdobe PDFView/Open
07_chapter 1.pdf178.53 kBAdobe PDFView/Open
08_chapter 2.pdf230.5 kBAdobe PDFView/Open
09_chapter 3.pdf239.23 kBAdobe PDFView/Open
10_chapter 4.pdf216.36 kBAdobe PDFView/Open
11_chapter 5.pdf191.43 kBAdobe PDFView/Open
12_bibliography.pdf107.89 kBAdobe PDFView/Open


Items in Shodhganga are protected by copyright, with all rights reserved, unless otherwise indicated.