AF: Small: Symmetry, Randomness and Computations in Real Algebraic Geometry

Purdue University, West Lafayette IN

Investigators

Abstract

Sets defined in terms of real polynomial inequalities, called semi-algebraic sets, are ubiquitous in science and engineering. Consequently, it is very important to have efficient algorithms for computing properties of semi-algebraic sets. One drawback of semi-algebraic geometry is the very high algorithmic complexity for such algorithms. Semi-algebraic sets tend to get topologically very complicated as the number and the degrees of the polynomials defining them, as well as the dimension of the ambient space, increases. Thus it is very important to identify situations, especially from the point of view of practical applications, where this increase in topological as well as algorithmic complexity can be controlled in a better way. The project will address several key questions in algorithmic and quantitative semi-algebraic geometry concentrating on the phenomenon of reduction in complexity induced by symmetry, as well as by randomness, in various situations. The project will have impact on several areas of mathematics and computer science and will train two graduate students in quantitative and algorithmic real algebraic geometry and its modern applications. A part of the project will deal with quantitative and algorithmic questions related to semi-algebraic sets equipped with a group action. Since the action of the group descends to the cohomology of such sets, the cohomology spaces get an extra structure of being finite-dimensional modules over the group. This gives the advantage that one can study the cohomology of such sets and compute their dimensions using the structure of this module. The investigator plans to exploit this basic idea to develop algorithms with exponentially better complexity than the best algorithms for the same problems for general semi-algebraic sets. Since semi-algebraic sets equipped with group actions occur frequently in practice, these algorithms will have many practical applications. The second part of the project will deal with random algebraic geometry, which is a relatively new and rapidly developing topic. Since, unlike complex discriminants, real discriminants disconnect spaces of parameters, there is no unique generic situation in real algebraic geometry. Thus, study of real algebraic geometry often involves difficult classification problems that soon become intractable, e.g. Hilbert's sixteenth problem. An attractive alternative that also has practical applications is to choose an appropriate measure and study expected statistics (such as Betti numbers) of real varieties, rather than consider all possibilities. The investigator will explore several problems through the probabilistic lens afforded by a widely studied Kostlan measure, with the goal of proving that the typical behavior of semi-algebraic sets defined by randomly chosen polynomials is often much better than the worst-case deterministic behavior, and translate this reduction of complexity into corresponding algorithmic results. 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.