AF: Small: Geometry of Polynomials and Algorithm Design

本项目以复杂的几何和代数技术为基础，为算法设计中的经典问题开发新的算法。此类问题的一个例子是旅行推销员问题（TSP），它涉及在大量目的地之间找到最短的路线，并在物流，规划和车辆路线中得到应用。TSP也用于芯片制造和基因组测序的子程序。另一个有趣的应用是在线匹配，它被搜索引擎或大型在线出版商用于分配广告空间。除了可能影响拼车和在线广告等大型行业外，拟议中的项目还旨在开发普遍适用的分析工具，并为其他应用程序设计新算法。该项目还包括一个教育和外联部分，其中包括设计和广泛传播关于这一主题的课程材料。该项目侧重于两类问题：首先，它用算法透镜研究多项式根的几何形状，并旨在开发多项式时间算法，而目前的理论只给出存在性证明。其次，它通过提出组合学（如计算某些组合对象）或离散优化（如旅行推销员问题）中的新问题，扩展了这一理论的范围和适用性。具体而言，该项目包括研究：(i)通过多项式的镜头来计数问题，并通过使用多项式编码问题实例来研究计数和抽样问题的算法；（ii）旅行推销员问题和一个新猜想的研究，该猜想可能会导致对该问题具有更好的近似比的算法；（iii）在线随机优化，其中提出了一种使用傅里叶分析来近似该问题的最佳解的新方法。（iv）多项式时间算法，用于查找某些多项式族的根，这些多项式族可以更快地构建称为拉马努金图的低次，高连通性图。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This project builds on sophisticated geometric and algebraic techniques to develop new algorithms for classic problems in algorithms design. One example of such problems is the Traveling Salesman Problem (TSP) which involves finding the shortest tour between a large number of destinations and has applications in logistics, planning, and vehicle routing. TSP is also used in chip manufacturing and as a subroutine in Genome sequencing. Another application of interest is online matching which is used by search engines or large online publishers for allocating advertisement space. In addition to the potential for impacting large industries like ride-sharing and online advertising, the proposed project aims to develop analytical tools that are generally applicable and can lead to the design of new algorithms for other applications. The project also includes an education and outreach component which incorporates design and broad dissemination of course materials on the subject. The project focuses on two types of questions: first, it studies the geometry of the roots of polynomials with an algorithmic lens, and aims to develop polynomial-time algorithms where the current theory only gives proof-of-existence. Second, it expands the scope and applicability of this theory by proposing new problems in combinatorics (like counting certain combinatorial objects) or discrete optimization (like the traveling salesman problem). In particular, the project includes the study of: (i) counting problems through the lens of polynomials and the study algorithms for counting and sampling problems by encoding problem instances using polynomials, (ii) the traveling salesman problem and the study of a new conjecture that can potentially lead to algorithms with better approximation ratio for this problem, (iii) online stochastic optimization where a new approach using Fourier analysis to approximate the optimum solution for this problem is proposed, and (iv) polynomial-time algorithms for finding roots of certain families of polynomials that can lead to faster construction of low-degree, high-connectivity graphs known as Ramanujan graphs.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.