Counting complexity and computational group theory

DSpace/Manakin Repository

Counting complexity and computational group theory

Show simple item record Vinodchandran, N.V. 2009-08-19T10:41:19Z 2009-08-19T10:41:19Z 2009-08-19T10:41:19Z 1998
dc.description.abstract The main contribution of this thesis is in proving upper bounds on the counting complexity of some computational problems that arise from group theory. It consists of two parts. The first part concentrates on studying the complexity of three basic, computationally hard, group-theoretic problems over black-box groups. These problems are membership testing, Order verification, and Isomorphism testing. It is shown that all these problems over solvable black-box groups are in the complexity class SPP. The second part of the thesis focus on studying the complexity of various representation classes with respect to their learnability, in particular the learnability of some group theoretic and linear algebraic concept classes. The complexity of learning these algebraic concept classes is compared to that of learning boolean functions represented in conjunctive normal form. A refinement of Angluin's model called the teaching assistant model of exact learning is proposed in order to do a finer classification of the complexity of exact learning. It acts as an interface between the teacher and the learner. The notion of teaching assistant classes are defined in exact analogy with known complexity classes; As one of the main results it is shown that while permutation groups (Linear spaces over fixed finite fields) can be learned using a teaching assistant in the assistant class analogous to LWPP (respectively, SPP), it is unlikely that the class 3-CNF can be learned using an LWPP or SPP assistant. The power of various assistant classes are investigated and representation classes which separate these assistant classes are exhibited. The two parts of the thesis are addressing two different issues but there are some underlying connections between the two parts. In both the parts the issue of analyzing the complexity of some computational problems over finite groups, although the exact nature of the problems differ. The learning algorithms designed with LWPP and SPP teaching asssistants are built on the complexity theoretic ideas used in showing the upper bound results in the first part of the thesis. en_US
dc.subject Computational Group Theory en_US
dc.subject Complexity en_US
dc.title Counting complexity and computational group theory en_US Ph.D en_US
dc.type.institution University of Madras en_US
dc.description.advisor Arvind, V.
dc.description.pages v; 117p. en_US
dc.type.mainsub Computer Science en_US

Files in this item

Files Size Format View
UNMTH58.pdf 9.529Mb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search


My Account