Complexity upper bounds using permutation group theory

DSpace/Manakin Repository

Complexity upper bounds using permutation group theory

Show full item record

Title: Complexity upper bounds using permutation group theory
Author: Kurur, Piyush P.
Advisor: Arvind, V.
Degree: Ph.D
Main Subjects: Computer Science
Institution: University of Madras
Year: 2006
Pages: vi; 134p.
Abstract: This thesis studies the Graph Isomorphism and problems that arise in Galois theory. It is targeted to use structural properties of permutation groups together with other algebraic techniques to prove complexity upper bounds. Complexity theory is the study of resource bounded computations. Efficiency is measured in terms of the resource required to solve the problem as a function of the input size. The study of complexity Graph Isomorphism and problems associated with Galois theory with an aim of classifying these in the frame work of complexity theory is undertaken. The role of permutation group theory is a common thread that connects these two. The structure of permutation groups and the numerous efficient algorithms for permutation group problems play an important role in this thesis results. Permutation groups also plays an important role in algorithms for Graph Isomorphism. Group theory has played an important role in various complexity theoretic results. Chapter 2 speaks about a brief survey of the complexity theory required for this thesis; Chapter 3 develops the required group theory. Chapter 6 describes the required algebraic number theory, from which some of the results leads to one of the results on Galois theory in this thesis. Chapters 4 and 5 explains the results on Graph Isomorphism and related problems. The results on computational problems in Galois theory is described in Chapters 7,8 and 9.
URI: http://hdl.handle.net/123456789/123

Files in this item

Files Size Format View
piyush-kurur.pdf 695.8Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record

Search DSpace


Advanced Search

Browse

My Account