Seminar Event Detail


Combinatorics

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 l-infinity 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 quasi-polynomial n^{O(ln n - ln epsilon)} time. The approach can be readily extended to computing hafnians, multi-dimensional permanents of tensors and other partition functions arising from combinatorial enumeration problems.

Files:


Speaker:  Alexander Barvinok
Institution:  U. Michigan

Event Organizer:     

 

Edit this event (login required).
Add new event (login required).
For access requests and instructions, contact math-webmaster@umich.edu

Back to previous page
Back to UM Math seminars/events page.