AF: Small: Geometric Inequalities, Clustering Hardness, and Social Choice

University Of Southern California, Los Angeles CA

Investigators

Abstract

This project seeks to answer the following related questions: (1) "What is the best way to cluster data on a computer?" (2) "How can we design voting systems whose outcomes are robust in the face of inaccuracies in counting?" Question (1) arises, for instance, when a content provider wants to cluster consumers with similar interests into separate groups. Question (2) arises when designing voting systems that are resilient to attempted interference by third parties. Questions (1) and (2) can be reformulated as isoperimetric problems. One example of an isoperimetric problem asks for the shape of a fence of fixed length that encloses the most area (the answer being a circular fence, which has been known since ancient times). Investigations in theoretical computer science in the last two decades have given renewed interest for Questions (1) and (2). Generally speaking, theoretical computer science finds ways for computers to solve problems as quickly and as efficiently as possible. The overarching goal of this project is to prove that some important computational problems cannot possibly be solved better than by some well-known efficient algorithms. This project continues the investigator's application of calculus of variations techniques to prove isoperimetric inequalities. These inequalities then imply computational-hardness results in theoretical computer science and optimality statements in social-choice theory. Several recent isoperimetric problems in theoretical computer science such as (1) and (2) ask for the Euclidean sets of smallest Gaussian surface area and fixed Gaussian volume. Since a landmark result of Colding and Minicozzi in 2012, it has become apparent that calculus of variations techniques can solve these isoperimetric problems, where other methods are not successful. The principal investigator will continue to apply the methods of Colding and Minicozzi in order to ultimately prove that certain semidefinite programming algorithms are the best possible approximation algorithms for several problems of interest, assuming Khot's Unique Games Conjecture. Expected project outcomes include sharp computational hardness results for: the MAX-m-CUT problem, a kernel-clustering problem from machine learning, and certain cases of the Unique Games Conjecture. 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.