Speaker: Jayalal Sarma M.N The Institute of Mathematical Sciences, Chennai, India
Time: 2008-03-05 13:00-2008-03-05 14:00
Venue: FIT Building 4-603, Tsinghua University
Download: Click!

Abstract:

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 the rigidity of a matrix. Matrices with high rigidity have interesting applications in the theory of lower bounds: 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.

 

Short Bio:

 

My academic interests are mainly in Computational Complexity theory.
A little more specifically,
       ●  Algebraic and Combinatorial Concepts Related to Circuit Complexity.
        ●  Computational Complexity of Linear Algebraic Problems.
        ●  Word problems and Computing Power of Algebraic Structures (like monoids, groups etc).
        ●  Structural Complexity and Derandomization Techniques.