Geometry and representation theory in computational complexity

• Antragsteller: Professor Dr. Peter Bürgisser
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2009 bis 2015
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 121425861

Geometric complexity theory is an approach towards proving fundamental complexity lower bounds by means of algebraic geometry and representation theory. The most prominent questions considered are the permanent versus determinant problem and the complexity of matrix multiplication. It is remarkable that both questions can be restated as explicit orbit closure problems. One tries to separate the orbit closures under consideration by exhibiting obstructions, which are irreducible representations occuring in the coordinate ring of one orbit closure, but not in the other. The geometric complexity program has gained visibility and momentum in the past years, as documented by numerous publications. Some modest lower bounds have been proven using this approach. On the other hand, it has become clear that more powerful tools need to be developed for proceeding. We want to deepen the analyses of our attempts already started and to explore other routes.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1388: Representation Theory (Darstellungstheorie)