AF: Small: Quantitative and Algorithmic Aspects of Semi-algebraic Sets and Partitions

“分而治之”是计算机科学和数学中的一种由来已久的技术，它将问题分成更小的部分，使其更容易解决。这个项目在半代数几何的背景下从两个方向深化了划分的研究，即研究由实多项式等式和不等式定义的集合的几何和拓扑性质。第一个方向是系统化多项式划分，它最近成为能够解决关联几何领域中许多长期悬而未决的问题的有力工具。在计算几何中，被划分的空间或集合通常是复杂的，但划分是由简单的对象进行的：按平面分割或切割成梯形。多项式划分允许多项式的高阶切分，使得半代数集和实簇的拓扑结构需要比已知的更精确的基于次数的上界，并导致实代数几何和离散几何领域之间卓有成效的相互作用。PI将发展半代数几何的新技术，以满足离散几何的发展对该领域的新要求，并发展一种新的多项式划分理论，使其研究系统化，并导致新的应用。第二，将定量和算法半代数几何推广到更一般的几何设置--可构造层。可构造层具有基本的半代数划分(在其元素上，层的柄是局部恒定的)。Kashiwara和Schapira证明了这一范畴在六种标准的束运算下的稳定性的一个基本定理(类似于半代数集的塔斯基-塞登堡原理)。PI将研究与可施工滑轮相关的定量和算法问题。复杂的上界和算法结果将有广泛的应用。该项目将在数学和计算的几个领域产生影响--包括定量和算法半代数几何、离散和计算几何、计算复杂性理论和对偏微分方程组的解的定量研究。该项目将在定量和算法实代数几何及其现代应用方面对研究生和博士后研究员进行培训。

"Divide and conquer," a time-honored technique in computer science andmathematics, partitions a problem into smaller pieces to make iteasier to solve. This project deepens the study of partitioning in twodirections, both in the context of semi-algebraic geometry -- which isthe study of geometric and topological properties of sets defined byreal polynomial equalities and inequalities.The first direction is to systematize polynomial partitioning, whichhas recently become a powerful tool capable of tackling manylong-standing open questions in the area of incidence geometry. Incomputational geometry, the space or sets being partitioned are oftencomplex but partitioning is by simple objects: splitting by planes orcutting into trapezoids. Polynomial partitioning allows high degreecutting polynomials, necessitating more precise degree-based upperbounds on the topology of semi-algebraic sets and real varieties thanthe ones known before, and leading to a very fruitful interactionbetween the fields of real algebraic geometry and discrete geometry.The PI will develop new techniques in semi-algebraic geometry to meetthe new demands imposed on the field by the developments in discretegeometry, and develop a new theory of polynomial partitioning that cansystematize their study and lead to new applications as well.The second is to generalize quantitative and algorithmicsemi-algebraic geometry to a much more general and geometric setting-- the category of constructible sheaves. Constructible sheaves comewith an underlying semi-algebraic partition (on whose elements thestalks of the sheaf are locally constant). Kashiwara and Schapiraproved a fundamental theorem on the stability of this category underthe six standard sheaf operations (analogous to Tarski-Seidenbergprinciple for semi-algebraic sets). The PI will study the quantitativeand algorithmic questions related to constructible sheaves. Thecomplexity upper bounds and algorithmic results would have wideapplications.The project will have impact in several areas of mathematics andcomputation -- including quantitative and algorithmic semi-algebraicgeometry, discrete and computational geometry, computationalcomplexity theory and quantitative study of the solutions to linearsystems of partial differential equations. The project will train agraduate student and a postdoctoral researcher in quantitative andalgorithmic real algebraic geometry and its modern applications.