Collaborative Research: AF: Medium: Fundamental Challenges in Discrete and Continuous Optimization

Modern Algorithms, including those for artificial intelligence (AI) and Scientific Computing, rely on efficient optimization. This project addresses current challenges in optimization, with the goal of developing techniques that enable faster and more accurate algorithms than are currently known to be possible. The target problems are at the intersection of computer science with other theoretical disciplines, including convex geometry, analysis, statistics, and operations research. This project also includes research opportunities for undergraduate students and early exposure to computing concepts for K-12 students at local schools. The development of the theory of algorithms and complexity has gone hand-in-hand with the development of techniques for optimization. This project focuses on three related thrusts, all building on recent breakthroughs: (1) Understanding the complexity of the widely used interior-point method in terms of the number of iterations, in the worst case, on average and for sparse inputs; (2) developing continuous methods for solving discrete problems, particularly those at the frontier of discrepancy minimization, satisfiability and spectral optimization; and (3) improving approximation algorithms via better analysis of convex relaxations, as well as the analysis of practical cutting-plane methods for solving them. 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.