Austin Shapiro

Permanents

The permanent of a matrix could be defined as "the determinant without the signs." Though not as fundamental as the determinant, it does arise in several problems of counting (e.g., perfect matchings, plane partitions, contingency tables). Unfortunately, it is hard to compute -- #P-complete, to be precise! I will discuss (1) the above applications of the permanent, (2) upper and lower bounds on special classes of permanents, and (3) algorithms for exact and approximate computation of the permanent.