Robust Output Sensitive Algorithms for Subanalytic Geometry

Texas A&M Research Foundation, College Station TX

Investigators

Abstract

The investigator aims to complete the nascent theory of output-sensitive algorithms in real algebraic geometry. Output-sensitive in this context means that the complexity of the underlying algorithm depends mainly on intrinsic geometric parameters, e.g., the number of connected components of the underlying solution set, as opposed to extrinsic parameters like the degrees of the input polynomials. Such algorithms are faster than the traditional methods of computational algebra by a factor exponential in the dimension, but have so far been discovered only in various isolated contexts. So a unified algorithmic approach has a broad impact. Furthermore, the underlying approach takes numerical conditioning into account from the outset, thus providing algorithms that are certifiably precise even when applied to approximate data. Another novelty is that the underlying theory applies in the even broader arena of real and p-adic analytic functions. The algorithmic aspects of p-adic analytic functions are almost completely unexplored, so a secondary focus of this project is to elaborate and apply this new theory to equation-solving over finite fields and motivic integration. The investigator combines advanced techniques from numerical analysis and algebraic geometry to provide a new approach to a fundamental problem occuring in many applications: solving analytic inequalities. For example, finding the optimal allocation of resources in a large organization (e.g., an army, an airline, or a large business) has long been known to reduce to solving linear inequalities. From a different direction, it is known that the complexity of certain neural net architectures (which are useful in training automated bomb-sniffers and pattern recognition systems) depends critically on understanding the solutions of nonlinear polynomial inequalities. Both these examples are special cases of analytic inequalities, and this project provides new algorithms for their solution that are magnitudes faster than current algorithms. Furthermore, these new algorithms provide certifiably precise solutions --- a feature which is especially important when facing uncertain physical data. Another novel aspect is the principal investigator's recent discovery that the underlying techniques apply to an even broader context, which can provide new solutions to many problems in the design of cryptosystems.