ABSTRACT

Understanding the limits of efficient computation is central to the theory of computer science. These limits dictate what can be expected from the algorithms that are coded, and justify beliefs in the security of cryptography. The use of algebraic techniques (multiplication, derivatives, and beyond) is pervasive in the design of efficient computation. These techniques apply to problems inherently of an algebraic nature, as well for tasks that seemingly lack algebraic structure. This project seeks to understand the power of these techniques through two different lenses. The first aims to show how to efficiently eliminate the use of randomness in algebraic algorithms. The second aims to leverage the deep mathematical structure of algebraic algorithms to define limits on their computational power. These two aims are connected through attention to common techniques and models of algebraic computation. The project will promote study of algebraic computation in general through course design, organization of workshops, and training of undergraduate and graduate students.

In particular, this project seeks to design deterministic algorithms for deciding whether a given algebraic expression simplifies to a trivial expression, a problem known as polynomial identity testing (PIT). While efficient randomized algorithms for PIT have been known for decades, developing deterministic algorithms has proven challenging. The project identifies classes of PIT problems which are both of fundamental importance and that are ripe for further progress. Deterministically solving these PIT problems would settle key challenges in the area, and also lead to new algorithms in areas outside algebraic computation. Developing such deterministic PIT algorithms is known in general to be equivalent to establishing limits on efficient algebraic computation, and as such this project seeks to establish such limits through the geometric complexity theory (GCT) program. This program has seen significant overall interest from the research community, but has seen fewer than desired results due to the high barriers to entry arising from steep mathematical prerequisites. The project offers a set of problems within this program that both are of fundamental importance, but also are concretely solvable. The selection of these problems is informed by corresponding progress made in developing deterministic PIT algorithms, and as such the two parts of the project will develop in tandem.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

Please report errors in award information by writing to: awardsearch@nsf.gov.