Who Cares About Permanents?

Persi Diaconis
Stanford University

Evaluation of the permanent was one of the earliest problems to be proved #-p complete. It has also been the object of intense study by theorists Jerrum-Sinclair-Vigoda among many others. In this expository talk I review the many appearances of permanents in applied problems of statistics, permutations with restricted position as they appear in ESP and taste-testing experiments, matching theory and elsewhere. New heuristic algorithms are introduced which seem wonderful in applied problems. The gap between theory and practice is truly narrowing. All of this is joint work with Susan Holmes and Ron Graham.

Return to the Program