Date: Friday, February 06, 2015
Location: 3866 East Hall (4:10 PM to 5:00 PM)
Title: Complex geometry and computational complexity of the permanent
Abstract: The permanent of a square matrix is a polynomial in the matrix entries, which looks like the determinant, only simpler: all the monomials are taken with the "+" sign. It turns out that the permanent of a complex matrix where each entry is within 0.275 from 1 is never 0. In other words, the linfinity distance from the matrix of all 1s to the complex hypersurface of matrices with 0 permanent is bounded from below by a positive absolute constant, independent on the size of the matrix (the best possible value of the constant is not known, one can show, however, that it does not exceed 0.708). This fact allows us to compute the permanent of an nxn real or complex matrix with entries within 0.274 from 1 within a relative error epsilon >0 in quasipolynomial n^{O(ln n  ln epsilon)} time. The approach can be readily extended to computing hafnians, multidimensional permanents of tensors and other partition functions arising from combinatorial enumeration problems.
Files:
Speaker: Alexander Barvinok
Institution: U. Michigan
Event Organizer:
