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

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.