A Study of Width Bounded Arithmetic Circuits and the Complexity of Matroid Isomorphism[HBNI TH 17]

DSpace/Manakin Repository

A Study of Width Bounded Arithmetic Circuits and the Complexity of Matroid Isomorphism[HBNI TH 17]

Show simple item record

dc.contributor.author Raghavendra Rao, B. V.
dc.date.accessioned 2010-05-14T12:08:30Z
dc.date.available 2010-05-14T12:08:30Z
dc.date.issued 2010-05-14T12:08:30Z
dc.date.submitted 2010
dc.identifier.uri http://hdl.handle.net/123456789/177
dc.description.abstract This thesis is broadly divided into two parts: i) Study of width bounded arithmetic circuits, and ii) Computational complexity of matroid isomorphism problems. Various arithmetizations of boolean complexity class NC1 is studied in the first part. It is shown that constant width syntactic multilinear circuits are equivalent to constant width syntactic multilinear branching programmes at polynomial size formulas. For linear matroids it is shown that the isomorphism testing is in (Sigma_2)^p, and is unlikely to be (Sigma_2)^p complete. When the rank of the given input matroid is a constant, the problem is polynomial time many-one equivalent to the graph isomorphism problem. For the case of matroids represented by graphs, it is shown that the isomorphism testing problem is polynomial time equivalent to the graph isomorphism problem. Along the way colouring techniques are developed for handling coloured instances of matroid isomorphism problems. It is also proved that polynomial time equivalence of isomorphism testing problem and the problem of computing automorphism groups for the case of linear and graphic matroids. en_US
dc.publisher.publisher
dc.subject Matroid Isomorphism Problems en_US
dc.subject Bounded Arithmetic Circuits en_US
dc.subject HBNI TH 17 en_US
dc.title A Study of Width Bounded Arithmetic Circuits and the Complexity of Matroid Isomorphism[HBNI TH 17] en_US
dc.type.degree Ph.D en_US
dc.type.institution HBNI en_US
dc.description.advisor Meena Mahajan
dc.description.pages 173p. en_US
dc.type.mainsub Computer Science en_US

Files in this item

Files Size Format View
HBNITH 17.pdf 1.326Mb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account