Speaker: Manindra Agrawal
Indian Institute of Technology
Monday, January 22, 2007
11:00 AM - 1:00 PM
EBU3b 1202

ABSTRACT
I will talk about the problem of expressing permanent of matrices as determinant of (possibly larger) matrices. This problem has close connections with complexity of arithmetic computations: complexities of computing permanent and determinant roughly correspond to arithmetic versions of the classes NP and DP respectively. I will survey known results about their relative complexity and describe two recently developed approaches that might lead to a proof of the conjecture that permanent can only be expressed as determinant of superpolynomial-sized matrices.