Date:  14:0014:40, Thursday, March 26, 2009 
Venue:  FIT Building 1315, 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 subclasses 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 wellstudied 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.
