# Complexity upper bounds using permutation group theory

 dc.contributor.author Kurur, Piyush P. dc.date.accessioned 2009-09-23T07:07:09Z dc.date.available 2009-09-23T07:07:09Z dc.date.issued 2009-09-23T07:07:09Z dc.date.submitted 2006 dc.identifier.uri http://hdl.handle.net/123456789/123 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 dc.type.degree 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