Algorithmic Problems in Semi-algebraic Geometry and Topology

编号：0634907机构：格鲁吉亚技术研究公司-佐治亚理工学院PI：Basu，Saugata标题：半代数几何和拓扑中的数学问题摘要：代数半代数几何是计算机科学和数学的几个不同领域中许多问题的核心，包括离散和计算几何，机器人运动规划，几何建模，计算机辅助设计，几何定理证明，真实的代数簇的数学研究，分子化学，约束数据库等。一个密切相关的主题领域是定量真实的代数几何。从定量真实的代数几何的结果是半代数几何中更好的算法的基本成分，并且在计算机科学的其他几个领域中发挥着越来越重要的作用：例如，在计算几何学、计算学习理论中界定排列的几何复杂性，在计算复杂性理论中证明下界，凸优化问题等。因此，算法和定量实代数几何近年来一直是一个非常活跃的研究领域。主要的研究目标包括，在真实的代数几何中发展新的技术，这将导致新的和更好的算法，用于在理论上计算半代数集的拓扑不变量，以及实践，并使方法和技术的算法真实的代数几何承担几个开放的问题，在离散和计算几何和探索新的连接，特别是在该地区的计算拓扑结构。教育目标包括，开发一个综合的跨学科课程适合高级本科生和开始研究生，不需要先决条件超越大学水平的微积分和线性代数，使他们能够快速吸收必要的数学背景这条线的研究。拟议活动的更广泛影响将包括在算法半代数几何领域培训新的研究生，以及跨几个不同领域的合作研究：真实的代数几何、离散和计算几何、符号计算和计算复杂性理论。

Number: 0634907Institution: Georgia Tech Research Corporation - GA Institute of TechnologyPI: Basu, Saugata Title: Algorithmic Problems in Semi-algebraic Geometry and TopologyAbstract: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 main research objectives would include, development of 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, and bringing methods and techniques of algorithmic real algebraic geometry to bear on several open problems in discrete and computational geometry and to explore new connections, especially in the area of computational topology. The educational goals involve, developing an integrated cross-disciplinary curriculum suitable for advanced under-graduate and beginning graduate students, requiring no pre-requisite beyond college-level calculus and linear algebra, so that that they can quickly absorb the mathematical background necessary for this line of research. The broader impact of the proposed activity would include training of new graduate students in the field of algorithmic semi-algebraic geometry, as well as collaborative research spanning several different areas: real algebraic geometry, discrete and computational geometry, symbolic computation and computational complexity theory.