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.
