CAREER: Learning, testing, and hardness via extremal geometric problems

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2).

If P differs from NP, there are many important computational problems that cannot be solved efficiently. Even more importantly for applications (because in practice exact solutions are often not needed), it is computationally hard even to approximately solve some of these problems. The field that studies this topic, known as "hardness of approximation," has progressed in leaps and bounds over the last two decades.

One of the seminal achievements of the field was the forging of a deep connection between computational complexity and isoperimetric-type problems in geometry and probability. The isoperimetric problem in the plane -- which has been known and studied for more than 2 millenia -- asks which shape of a given area has a minimal perimeter (the answer: a circle).

If there were a better understanding of certain probabilistic, high-dimensional variants of this problem, it would close several open problems in hardness of approximation. A better understanding of the limits of efficient approximate computation will in turn lead to better algorithms for real-world computational problems.

This project is about strengthening the link between hardness of approximation, geometry and probability. By solving new optimal partitioning problems in geometry and probability, the investigator will develop algorithms and prove new algorithmic hardness results. One of the difficulties with these partitioning problems is the presence of combinatorially many saddle points or local minima, but the investigator's recent resolution (with E.

Milman) of the Gaussian double-bubble conjecture included a new method to circumvent this difficulty. Algorithmic consequences of these optimal partitioning problems include (i) improved bounds for testing and learning geometric concept classes; (ii) improved algorithms for non-interactive correlation distillation (a problem in cryptography with applications to random beacons and information reconciliation); and (iii) a stronger separation between classical and quantum communication complexity.

This award will allow graduate and undergraduate students to participate in related research projects, it will fund the development of open-source software for numerical computation, and it will support outreach activities for K-12 students.

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.