In this talk we revisit the interplay between some linear algebraic concepts and circuit complexity theory. We will provide some new characterisations of complexity classes in terms of matrix rank computation. We consider the problem of optimizing matrix rank, a version of which is related to the notion of matrix rigidity: the number of entries that needs to be changed in the matrix to bring down the rank below a specified value is therigidity of a matrix. Matrices with high rigidity have interesting applications in the theory of lowerbounds: mainly in arithmetic circuits and in communication complexity. We will briefly mention some of our recent results in this context, and discuss some complexity theoretic results (and some open ends) for the computational version of the problem.

l           个人简介：

Jayalal Sarma M.N. is a Ph.D student for Theoretical Computer Science in The Institute of Mathematical Sciences in India, under the guidance of Prof. Meena Mahajan.

His academic interests are mainly in Computational Complexity theory.

l           学科分类：计算机科学与技术