Complexity upper bounds using permutation group theory

DSpace/Manakin Repository

Complexity upper bounds using permutation group theory

Show simple item record Kurur, Piyush P. 2009-09-23T07:07:09Z 2009-09-23T07:07:09Z 2009-09-23T07:07:09Z 2006
dc.description.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. en_US
dc.subject Complexity Theory en_US
dc.subject Group Theory en_US
dc.subject Computational Galois Theory en_US
dc.subject Graph Isomorphism en_US
dc.title Complexity upper bounds using permutation group theory en_US Ph.D en_US
dc.type.institution University of Madras en_US
dc.description.advisor Arvind, V.
dc.description.pages vi; 134p. en_US
dc.type.mainsub Computer Science en_US

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 simple item record

Search DSpace

Advanced Search


My Account