Some complexity theoretic aspects of graph isomorphism and related problems[HBNI Th 19]

DSpace/Manakin Repository

Some complexity theoretic aspects of graph isomorphism and related problems[HBNI Th 19]

Show simple item record

dc.contributor.author Das, Bireswar
dc.date.accessioned 2010-05-20T04:53:38Z
dc.date.available 2010-05-20T04:53:38Z
dc.date.issued 2010-05-20T04:53:38Z
dc.date.submitted 2010
dc.identifier.uri http://hdl.handle.net/123456789/179
dc.description.abstract The complexity of graph isomorphism problem for restricted classes of graphs are studied and the complexity of group theoretic problems related graph isomorphism are investigated. Several problems closely related to the graph isomorphism problem are classified in Algorithmic graph theory in the classes PZK and SZK. A constant round perfect zero knowledge proof is given for the group isomorphism problem when the groups are given by their multiplication tables. The prover and the verifier in this proof system use only polylogarithmically many random bits. On this motivation, Honest Verifier Statistical Zero Knowledge(HVSZK) proof is studied where the prover, verifier and the simulator use polylogarithmic randomness but also has polylogarithmic message size and only 2 rounds. A polynomial-time oracle algorithm is given for Tournament Canonization that accesses oracles for Tournament Isomorphism and Rigid-Tournament Canonization. Extending the Babai-Luks Tournament Canonization algorithm, an n^O( k^2 + log n) is given for canonization and isomorphism testing of k-hypertournaments, where n is the number of vertices and k is the size of hyper edges. A FPT algorithm is given for the bounded color class hypergraph isomorphism problem which has run-time (b!2^O(b))(N^O(1)), where b is the size of the largest color class and N is the input size. It is proved that the isomorphism and canonization problem for k-tree is in the class StUL which is contained in UL. It is also proved that the isomorphism problem for k-path is complete for L under disjunctive truth-table reductions computable in uniform AC^0. en_US
dc.publisher.publisher
dc.subject Complexity Theory en_US
dc.subject Graph Isomorphism en_US
dc.subject HBNI Th 19 en_US
dc.title Some complexity theoretic aspects of graph isomorphism and related problems[HBNI Th 19] en_US
dc.type.degree Ph.D en_US
dc.type.institution HBNI en_US
dc.description.advisor Arvind, V.
dc.description.pages 143p. en_US
dc.type.mainsub Computer Science en_US

Files in this item

Files Size Format View
Bireswar-HBNI Th19.pdf 948.1Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account