AF: Small: Algorithmic Foundations for Processing Algebraic Sets

An algebraic set is a collection of points that satisfy constraints imposed by a collection of multivariable polynomial equations. Algebraic sets defined on real numbers naturally arise in electrical engineering, computer vision, and modeling of biochemical reaction networks. Put another way, algebraic sets are geometric objects that are cut out by polynomial equations: These sets provide a rich language for modeling and computation, as well as a clear framework for algorithm design.

The boundary of what is efficiently computable and what is intractable for computations over real algebraic sets is currently hazy. Moreover, even in the cases in which we have a fast algorithm for processing a collection of real algebraic sets, its numerical stability aspects are typically unclear. This proposal aims to develop a practical and clarifying theory: We aim to delineate hard and easy problems in computational real algebra in a way that guides numerical computations.

The project has the potential to impact the accuracy of 3D reconstruction, the stability of power-flow networks, and the modeling of biochemical reaction networks. The project will also train undergraduate and graduate students in theoretical computer science.

The proposal will address several structural and algorithmic questions. The first problem is to design an algorithm for finding a complex zero of a sparse system of polynomial equations that is average-case polynomial time. The second problem is understanding the relation between description complexity and geometric complexity of a real algebraic set.

We will specifically focus on Kushnirenko's conjecture and test our findings against the conjectures arising from systems biology. Kushnirenko's conjecture, in simple terms, asserts that the number of connected pieces of a real algebraic set is a polynomial function of the number of terms that appear in its defining equations. The third problem is to design algorithms that separate the polynomial systems with many real zeros from the ones with few real zeros, and this is motivated by applications in power flow network design.

The last problem to be addressed is the design and analysis of preconditioners for algebraic sets in general, and 3D reconstruction in particular.

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.