Robust Output Sensitive Algorithms for Subanalytic Geometry

点击翻译按钮获取中文摘要

The investigator aims to complete the nascent theory ofoutput-sensitive algorithms in real algebraic geometry.Output-sensitive in this context means that the complexity of theunderlying algorithm depends mainly on intrinsic geometricparameters, e.g., the number of connected components of theunderlying solution set, as opposed to extrinsic parameters likethe degrees of the input polynomials. Such algorithms are fasterthan the traditional methods of computational algebra by a factorexponential in the dimension, but have so far been discoveredonly in various isolated contexts. So a unified algorithmicapproach has a broad impact. Furthermore, the underlyingapproach takes numerical conditioning into account from theoutset, thus providing algorithms that are certifiably preciseeven when applied to approximate data. Another novelty is thatthe underlying theory applies in the even broader arena of realand p-adic analytic functions. The algorithmic aspects of p-adicanalytic functions are almost completely unexplored, so asecondary focus of this project is to elaborate and apply thisnew theory to equation-solving over finite fields and motivicintegration. The investigator combines advanced techniques from numericalanalysis and algebraic geometry to provide a new approach to afundamental problem occuring in many applications: solvinganalytic inequalities. For example, finding the optimalallocation of resources in a large organization (e.g., an army,an airline, or a large business) has long been known to reduce tosolving linear inequalities. From a different direction, it isknown that the complexity of certain neural net architectures(which are useful in training automated bomb-sniffers and patternrecognition systems) depends critically on understanding thesolutions of nonlinear polynomial inequalities. Both theseexamples are special cases of analytic inequalities, and thisproject provides new algorithms for their solution that aremagnitudes faster than current algorithms. Furthermore, thesenew algorithms provide certifiably precise solutions --- afeature which is especially important when facing uncertainphysical data. Another novel aspect is the principalinvestigator's recent discovery that the underlying techniquesapply to an even broader context, which can provide new solutionsto many problems in the design of cryptosystems.