Geometry and Complexity Theory

复杂性理论既涉及实际问题，也涉及理论问题。实际问题包括为需要频繁进行的计算(如矩阵相乘)开发新的高效算法，以及确定是否存在比已知的算法更高效的算法。理论方面包括几乎是哲学性质的问题，例如：直觉和系统解决问题之间真的有区别吗？(这个问题是由戈德尔提出的，并促成了著名的P对NP猜想的发展。)该项目将使用现代数学工具来解决这些问题，更具体地说，是代数几何和表示理论。虽然这个项目的研究是由计算机科学的问题驱动的，但这些问题本身对数学很感兴趣，并有可能指导未来的数学研究，就像物理学近年来所做的那样。本项目关注复杂性理论中的两个核心问题：矩阵乘法的复杂性和Valiant猜想的几何复杂性理论方法。关于矩阵乘法，线性代数是所有数学应用的核心，而矩阵乘法是线性代数的基本运算。1969年，Strassen发现了一种新的矩阵相乘算法，其速度比标准算法快得多。这项工作以及随后的工作导致了一个令人震惊的猜想，即从本质上讲，矩阵相乘几乎和相加一样容易。这是一个中心问题，确定一个人能以多高的效率乘以矩阵，无论是实际相乘还是渐近相乘。这个项目将证明矩阵的乘法效率的界限。关于几何复杂性理论，理论计算机科学中的一个中心问题是，在旅行商问题等问题中是否可以避免暴力计算。这就是P对NP猜想的本质。几何复杂性理论(GCT)课程使用几何方法解决这些问题。GCT涉及代数几何、微分几何、表示论和组合学中的中心问题。这个项目的目标是(I)通过解决组合学和经典代数几何中的公开问题来更好地建立GCT的数学基础，以及(Ii)解决被认为更容易处理的复杂问题，例如确定行列式多项式是否允许一个小公式。

Complexity theory addresses both practical and theoretical questions. Practical issues include developing new, efficient algorithms for computations that need to be done frequently (such as multiplying matrices), as well as determining whether more efficient algorithms than the ones already known may exist. The theoretical aspects include questions almost philosophical in nature, such as: Is there really a difference between intuition and systematic problem solving? (This question was asked by Godel and contributed to the development of the famous P versus NP conjecture.) The project will use modern mathematical tools to address these questions, more specifically, algebraic geometry and representation theory. Although the research for this project is driven by questions from computer science, these questions are of interest to mathematics in their own right and have the potential to guide future mathematical research in the way physics has done in recent years.This project focuses on two central questions in complexity theory: the complexity of matrix multiplication and the Geometric Complexity Theory approach to Valiant's conjectures. Regarding matrix multiplication, linear algebra is central to all applications of mathematics, and matrix multiplication is the essential operation of linear algebra. In 1969 Strassen discovered a new algorithm to multiply matrices significantly faster than the standard algorithm. This and subsequent work has led to the astounding conjecture that asymptotically, it is essentially almost as easy to multiply matrices as it is to add them. It is a central question to determine just how efficiently one can multiply matrices, both practically and asymptotically. This project will prove bounds for how efficiently matrices can be multiplied. Regarding Geometric Complexity Theory, a central question in theoretical computer science is whether brute force calculations can be avoided in problems such as the traveling salesman problem. This is the essence of the P versus NP conjecture. The Geometric Complexity Theory (GCT) program addresses such questions using geometric methods. GCT touches on central questions in algebraic geometry, differential geometry, representation theory and combinatorics. The goals of this project are (i) to better establish the mathematical foundations of GCT by solving open problems in combinatorics and classical algebraic geometry and (ii) to solve complexity problems considered more tractable, such as determining whether or not the determinant polynomial admits a small formula.