Peter Bürgisser is Professor of Mathematics at the University of
Paderborn in Germany. His main area of expertise is the complexity of algebraic and geometric problems. He is also interested in the average-case analysis of numerical problems. He was an invited speaker at the International Congress of Mathematicians (2010) in Hyderabad. He is the author of two reference books in algebraic complexity.
Prospects for Geometric Complexity Theory
It is a remarkable fact that two prominent problems of algebraic complexity theory, the permanent versus determinant problem and the tensor rank problem (matrix multiplication), can be restated as explicit orbit closure problems. This offers the potential to prove lower complexity bounds by relying on methods from algebraic geometry and representation theory. While this basic idea for the tensor rank problem goes back to work by Volker Strassen from the mid eighties, the geometric complexity program has gained visibility and momentum in the past years. Some modest lower bounds for border rank have recently been proven by the construction of explicit obstructions. For further progress, a better understanding of irreducible representions of symmetric groups (tensor products and plethysms) is required. Interestingly, asymptotic versions of the the latter questions are of relevance in quantum information theory.
