Geometry and representation theory in computational complexity

几何复杂性理论是利用代数几何和表示理论证明基本复杂性下界的一种方法。考虑的最突出的问题是恒量与行列式问题和矩阵乘法的复杂性。值得注意的是，这两个问题都可以重新表述为明确的轨道闭合问题。一种方法试图通过展示障碍来分离所考虑的轨道闭包，这些障碍是不可约的表示，出现在一个轨道闭包的坐标环中，而不在另一个轨道闭包中。几何复杂性程序在过去的几年中获得了知名度和势头，正如许多出版物所记录的那样。用这种方法已经证明了一些适度的下界。另一方面，很明显，需要开发更强大的工具才能继续进行。我们希望对已经开始的尝试进行深入分析，并探索其他途径。

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.