MCS: Randomization in Algorithmic Fewnomial Theory Over Complete Fields

这个项目代表了对算法代数几何、遍历复杂性理论、丢番图近似、实数和p-进几何、数值算法以及统计代数几何这一新兴领域的广泛研究。主要的焦点是稀疏多项式方程组-在许多应用程序中处于中心位置的一类计算问题。拟议的算法在某些工程领域产生了直接影响，在这些领域，PI和共同PI与数学以外的行业和教师有着密切的联系。智力上的优点包括：(1)获得斯梅尔第17个问题的确定性解；(2)稀疏多项式系统的最优随机根数；(3)P和NP边界问题的新的代数例子。更广泛的影响包括工程和计算机科学问题的新方法，博士后研究人员的培训，以及研究生的教育。特别是，Pi Rojas和研究生Rusek正在与Sandia国家实验室(包括公开可用的软件)合作，严格量化物理结构故障中的不确定性，例如核废料的储存。共同-Pi Avenano和Pi Rojas还与Daniele Mortari教授(德克萨斯州A和M航空航天工程系)就卫星轨道设计开展工作，并将其应用于监视和天文观测。

This project represents a broad investigation into algorithmic algebraic geometry, traversing complexity theory, Diophantine approximation, real and p-adic geometry, numerical algorithms, and the nascent field of statistical algebraic geometry. The main focus is systems of sparse polynomial equations --- a family of computational problems central in many applications. The proposed algorithms have immediate impact in certain areas of engineering where the PI and co-PIs have close connections with industry and faculty outside of mathematics. Intellectual merits include (1) an approach to a deterministic solution of Smale's 17th Problem, (2) optimal stochastic root counts for sparse polynomial systems, and (3) new algebraic examples of problems on the border between P and NP. Broader impacts include novel approaches to problems from engineering and computer science, the training of postdoctoral researchers, and the education of graduate students. In particular, PI Rojas and graduate student Rusek have an ongoing collaboration with Sandia National Laboratories (including publically-available software) on rigorously quantifying uncertainties in the failure of physical structures, e.g., the storage of nuclear waste. Co-PI Avendano and PI Rojas also have ongoing work with Prof. Daniele Mortari (of the Texas A and M Aerospace Engineering Department) on satellite orbit design, with applications to surveillance and astronomical observation.