Harry Crane, Rutgers University

Abstract

The alpha-permanent is a matrix function that has a similar algebraic form to the determinant but exhibits very different computational behavior. The permanent (alpha=1) is known to be #P-complete, and is a fundamental object in computational complexity theory. The more general alpha-permanent appears in statistical models for point pattern data and combinatorial data (e.g., partition and permutation data), where its computational complexity limits its applied use in many cases. I'll discuss some algebraic properties of the alpha-permanent which suggest natural connections to familiar concepts in probability theory and statistics. I'll also describe some immediate research problems that arise out of these observations.