AF: Small: Algebraic Methods for Core Problems in Algorithms and Complexity

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

This project targets a number of challenging problems in Algorithms and Complexity that are amenable to an algebraic approach. Research is organized around three major goals: 1. Algorithms for matrix multiplication with the aim of achieving nearly-linear running time (i.e., proving that the matrix multiplication exponent equals 2).2. Algorithms for polynomial factorization with the aim of achieving nearly-linear running time, and 3. Explicit constructions of randomness extractors with the aim of achieving logarithmic seed length and optimal output length. A secondary aim of this project is to explicitly cultivate novel algebraic methods with broader applicability, and the choice of problems and approaches is made with this in mind. Matrix multiplication is a central open problem in theoretical computer science, and improved algorithms for this important problem would have immediate consequences for a broad array of related problems. Univariate polynomial factorization is a similarly fundamental operation on polynomials, and it stands out as one of a very few such problems for which nearly-linear time algorithms are not yet known. Randomness extractors are unbalanced bipartite graphs with random-like properties that have emerged as a fundamental object in theoretical computer science (and beyond) with a huge array of applications spanning Complexity, Algorithms, Distributed Systems, Cryptography, Coding Theory, Compressed Sensing, and other areas. Resolving fundamental open problems such as those targeted in this project enhances our understanding and mastery of efficient computation.