Geometry and Complexity Theory

复杂性理论解决了实践和理论问题。实际问题包括开发新的，有效的算法，需要经常做的计算（如乘法矩阵），以及确定是否有更有效的算法比已知的可能存在。理论方面包括几乎哲学性质的问题，例如：直觉和系统解决问题之间真的有区别吗？(This这个问题是哥德尔提出的，并促成了著名的P对NP猜想的发展。）该项目将使用现代数学工具来解决这些问题，更具体地说，代数几何和表示理论。虽然这个项目的研究是由计算机科学的问题驱动的，但这些问题本身就对数学有兴趣，并且有可能指导未来的数学研究，就像近年来物理学所做的那样。这个项目关注复杂性理论中的两个核心问题：矩阵乘法的复杂性和Valiant代数的几何复杂性理论方法。关于矩阵乘法，线性代数是所有数学应用的中心，矩阵乘法是线性代数的基本运算。 在1969年斯特拉森发现了一个新的算法乘以矩阵显着快于标准算法。这项工作和随后的工作导致了一个惊人的猜想，即渐近地，矩阵相乘基本上和矩阵相加一样容易。这是一个中心问题，以确定如何有效地可以乘以矩阵，无论是实际和渐近。 这个项目将证明如何有效地矩阵相乘的界限。关于几何复杂性理论，理论计算机科学中的一个中心问题是在旅行推销员问题等问题中是否可以避免暴力计算。这就是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.