Classifying certain algebraic problems using Logspace counting classes[HBNI Th 5]

DSpace/Manakin Repository

Classifying certain algebraic problems using Logspace counting classes[HBNI Th 5]

Show simple item record

dc.contributor.author Vijayaraghavan, T. C.
dc.date.accessioned 2009-09-16T12:10:33Z
dc.date.available 2009-09-16T12:10:33Z
dc.date.issued 2009-09-16T12:10:33Z
dc.date.submitted 2008
dc.identifier.uri http://hdl.handle.net/123456789/118
dc.description.abstract In this thesis the results showing a finer classification of the complexity of several algebraic problems that have efficient polynomial time algorithms are obtained. The problems based on Group theory and Linear Algebra are considered in this thesis. A randomized parallel algorithm to solve LCON and place it in BP.NC^2 is presented in this thesis. A new logspace counting class ModL is introduced and shown that L^ModL = L^GapL. The BP.NC^2 upper bound for LCON also shows LCON is in (L^ModL)/ poly. Some of the well known techniques of polynomial identity testing and the Isolating Lemma are two main ingredients in the results found. Using LCON and LCONX it is also shown that the problem of computing a basis for the nullspace, denoted by LCONNULL, of a mapping in terms of a matrix is also in BP.NC^2 and in L^ModL / poly. A study on generalization of LCON, Testing feasibility of a system of linear equations over a finite ring R having unit element, proves the result that testing feasibility of linear equations over R is also in L^ModL / poly. The matroid intersection problem is considered for linearly representable matroids. It is to find an independent set of maximum cardinality in both M1 and M2. This thesis examines the complexity of problems on groups given by their Cayley as their input. It is shown that many of these problems such as testing whether the input group is simple, nilpotent, solvable, and computing normal closure, centralizer and so on are all logspace computable. en_US
dc.subject Group Theory en_US
dc.subject Linear Algebra en_US
dc.title Classifying certain algebraic problems using Logspace counting classes[HBNI Th 5] en_US
dc.type.degree Ph.D en_US
dc.type.institution HBNI en_US
dc.description.advisor Arvind, V.
dc.description.pages iv; 103p. en_US
dc.type.mainsub Computer Science en_US

Files in this item

Files Size Format View
vijayaraghavan_tc.pdf 840.6Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account