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

Title: A Study of Width Bounded Arithmetic Circuits and the Complexity of Matroid Isomorphism[HBNI TH 17]
Author: Raghavendra Rao, B. V.
Advisor: Meena Mahajan
Degree: Ph.D
Main Subjects: Computer Science
Institution: HBNI
Year: 2010
Pages: 173p.
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.
URI: http://hdl.handle.net/123456789/177

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

Search DSpace


Advanced Search

Browse

My Account