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.

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