Geometry and Complexity Theory

点击翻译按钮获取中文摘要

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.