MCS: Randomization in Algorithmic Fewnomial Theory Over Complete Fields

该项目代表了对算法代数几何的广泛研究，遍历复杂性理论，丢芬图近似，实数和p进几何，数值算法以及统计代数几何的新兴领域。主要的焦点是稀疏多项式方程的系统——在许多应用中中心的一系列计算问题。所提出的算法对某些工程领域产生了直接影响，在这些领域，PI和co-PI与数学以外的行业和教师有着密切的联系。智力上的优点包括(1)Smale's 17问题的确定性解决方法，(2)稀疏多项式系统的最优随机根计数，以及(3)P和NP之间边界问题的新代数示例。更广泛的影响包括解决工程和计算机科学问题的新方法，博士后研究人员的培训以及研究生的教育。特别是，PI Rojas和研究生Rusek正在与桑迪亚国家实验室（包括公开可用的软件）进行合作，严格量化物理结构失效的不确定性，例如核废料的储存。Avendano和Rojas还与Daniele Mortari教授（德克萨斯航空航天工程系）在卫星轨道设计方面进行合作，并将其应用于监视和天文观测。

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.