MCS: Randomization in Algorithmic Fewnomial Theory Over Complete Fields

MCS：完整域上算法少项理论的随机化

• 批准号: 0915245
• 负责人: J Maurice Rojas
• 金额: $ 40万
• 依托单位: Texas A&M Research Foundation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-15 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0915245&HistoricalAwards=false
• 关键词: MCS; Randomization; Algorithmic; Fewnomial; Theory

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.

该项目代表了对算法代数几何形状，遍历复杂性理论，毒液近似，真实和padic几何形状，数值算法以及统计代数几何学的新生场的广泛研究。主要重点是稀疏多项式方程的系统 - 在许多应用中，一系列计算问题家族。所提出的算法在PI和Co-Pis与数学以外的行业和教职员工之间有着密切联系的工程领域有直接的影响。智力优点包括（1）一种确定性解决方案的方法，即Smale的第17个问题，（2）稀疏多项式系统的最佳随机根数，以及（3）P和NP之间边界上问题的新代数示例。更广泛的影响包括工程和计算机科学问题，博士后研究人员的培训以及研究生的教育的新颖方法。特别是，Pi Rojas和研究生Rusek与Sandia National Laboratories（包括公开可用的软件）进行了持续的合作，以严格量化物理结构失败的不确定性，例如存储核废料。 Co-Pi Avendano和Pi Rojas在卫星轨道设计上还与Daniele Mortari教授（德克萨斯州A和M航空工程部）进行了持续的合作，并采用了监视和天文观察。