Testing isomorphism of mathematical structures is a source of computational problems with intriguing complexity. In this talk, we consider the complexity of testing if two given matroids are isomorphic. After giving some general results about the problem we consider various sub-classes of matroids and we present a series of reductions to show that the above problem for graphic matroids and bounded rank matroids are in fact equivalent to the well-studied graph isomorphism problem. We also study the corresponding automorphism problem and give a polynomial time membership test algorithm for the automorphism group for some class of matroids.

Date:	14:00-14:40, Thursday, March 26, 2009

Venue:	FIT Building 1-315, Tsinghua University

Title:	Complexity of Matroid Isomorphism Problem

Speaker:	Jayalal Sarma M.N.

Biography:	Jayalal Sarma M.N. is a postdoctoral research fellow in Institute for Theoretical Computer Science in Tsinghua University, hosted by Andrew Yao. His academic interests are mainly in Computational Complexity theory. He recently defended his Ph.D. thesis titled "Complexity Theoretic Aspects of Matrix Rank, Rigidity and Circuit Value" at The Institute of Mathematical Sciences, Chennai, India, and his advisor was Meena Mahajan.

Abstract:	Testing isomorphism of mathematical structures is a source of computational problems with intriguing complexity. In this talk, we consider the complexity of testing if two given matroids are isomorphic. After giving some general results about the problem we consider various sub-classes of matroids and we present a series of reductions to show that the above problem for graphic matroids and bounded rank matroids are in fact equivalent to the well-studied graph isomorphism problem. We also study the corresponding automorphism problem and give a polynomial time membership test algorithm for the automorphism group for some class of matroids.