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

“分而治之”是计算机科学和数学中一项历史悠久的技术，它将问题分割成更小的部分，使问题更容易解决。本项目在两个方向上深化了划分的研究，一个是在半代数几何的背景下-这是由实多项式等式和不等式定义的集合的几何和拓扑性质的研究。第一个方向是系统化多项式划分，它最近已经成为一个强大的工具，能够解决许多长期存在的关联几何领域的开放问题。在计算几何中，被分割的空间或集合通常是复杂的，但分割是通过简单的对象：通过平面分割或切割成曲面。 多项式分割允许高度切割多项式，需要更精确的度为基础的上界的拓扑结构的半代数集和真实的品种比以前已知的，并导致一个非常富有成效的相互作用领域之间的真实的代数几何和离散几何。PI将开发新的技术在半代数几何，以满足新的要求强加于该领域的发展离散几何，二是将定量和算法的半代数几何推广到更一般的几何环境--可构造层范畴。 可构造的层有一个基本的半代数划分（在其元素上层的茎是局部常数）。 Kashiwara和Schapira证明了一个关于这一范畴在六种标准层运算下的稳定性的基本定理（类似于半代数集的Tarski-Seidenberg原理）。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.