AF: Small: Algorithmic and Quantitative Problems in Semi-algebraic and O-minimal Geometry

该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。本研究的目标是进一步加深我们对算法和定量半代数几何的理解，发展新技术，特别是来自代数拓扑和o-极小结构理论的新技术，并扩大半代数几何在其他领域的应用，如离散几何和计算几何。算法半代数几何是计算机科学和数学的几个不同领域的许多问题的核心，包括离散和计算几何、机器人运动规划、几何建模、计算机辅助设计、几何定理证明、真实代数变量的数学研究、分子化学、约束数据库等。一个密切相关的学科领域是定量实代数几何。定量实代数几何的结果是更好的半代数几何算法的基本组成部分，并且在计算机科学的其他几个领域发挥着越来越重要的作用：例如，在计算几何中排列的几何复杂性的边界，计算学习理论，证明计算复杂性理论的下界，凸优化问题等。因此，算法和定量实代数几何近年来一直是一个非常活跃的研究领域。所提出的研究将在实际代数几何中发展新的技术，这将导致新的和更好的算法，用于计算半代数集的拓扑不变量的理论，以及实践。此外，几个开放的问题在定量实代数几何和密切相关的问题在离散和计算几何将攻击与PI开发的数学工具。所有这些研究目标将被整合到研究生培训和课程开发的广泛计划中。

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5). The goal of the proposed research is to further our understanding of algorithmic and quantitative semi-algebraic geometry, develop new techniques especially coming from algebraic topology and the theory of o-minimal structures, and broaden the applications of semi-algebraic geometry in other areas such as discrete and computational geometry.Algorithmic semi-algebraic geometry lies at the heart of many problems in several different areas of computer science and mathematics including discrete and computational geometry, robot motion planning, geometric modeling, computer-aided design, geometric theorem proving, mathematical investigations of real algebraic varieties, molecular chemistry, constraint databases etc. A closely related subject area is quantitative real algebraic geometry. Results from quantitative real algebraic geometry are the basic ingredients of better algorithms in semi-algebraic geometry and play an increasingly important role in several other areas of computer science: for instance, in bounding the geometric complexity of arrangements in computational geometry, computational learning theory, proving lower bounds in computational complexity theory, convex optimization problems, etc. As such, algorithmic and quantitative real-algebraic geometry has been an extremely active area of research in recent years.The proposed research will develop new techniques in real algebraic geometry that would lead to new and better algorithms, for computing topological invariants of semi-algebraic sets in theory, as well as practice. In addition, several open problems in quantitative real algebraic geometry and closely related problems in discrete and computational geometry will be attacked with the mathematical tools developed by the PI. All these research objectives will be integrated in a broad program of training graduate students and curriculum development.