AF: SMALL: Beyond Worst-Case Analysis for Computing with Polynomials

Computational algebraic geometry is the study of efficient ways to manipulate solution sets of algebraic equations on a computer. The origins of the field, starting from Buchberger’s algorithm in the 60’s, focused on exact computations on polynomial equations with integer coefficients. The goal of this research is to study computations on polynomial equations with real and complex number coefficients from a modern computational perspective.

This research is inspired by the emerging applications of multivariate polynomials (with real coefficients) in engineering, and has its roots in basic questions of complexity theory. The educational component of the research includes training of undergraduate students from different disciplines, creation of a student-accessible research seminar, and development of multiple undergraduate and graduate courses.

The project addresses the large discrepancy between practical performance of algorithms on real polynomials and the worst-case-based complexity estimates from computational algebraic geometry. The investigator aims to develop average-case upper bounds for complexity of sparse polynomial system solving over the real and complex numbers, upper bounds for the complexity of multivariate polynomial based algorithms on random networks, and average-case lower bounds for convex programming based approaches to algebraic computations.

Progress made in this project will benefit applications of polynomial computations with numerical data, and develop foundations of average-case complexity theory for polynomial computations on real and complex numbers.

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.