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

点击翻译按钮获取中文摘要

"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.