AF: Small: Graph Cut Complexity, Weak Unique Games, and Adam Nonconvergence

This project attempts to find the barrier between tractability and intractability for computational problems of broad interest and central importance. That is, the investigator will try to prove that certain problems cannot be quickly solved by computers. The project will also investigate if certain known algorithms are the best possible ones for these problems.

The algorithms considered in this project have been studied extensively, but a complete understanding remains elusive. A central part of the project is mathematically investigating if the plurality voting method is the "democratic" election method that best protects against random corruption or miscounting of votes. Besides suggesting which voting methods are mathematically the best ones to use, the project aims to advance the understanding of what computers can and cannot do in a reasonable amount of time.

The final part of the project addresses the method used to train large language models and other artificial intelligence (AI) tools and how well this method works. This training method is known to be deficient in certain ways, and the project will look for new deficiencies in this method. Understanding these deficiencies could lead to better performance of AI tools such as large language models.

The project will also train graduate students and include outreach activities to the public for greater understanding of different electoral methods such as ranked choice voting.

This project will attempt to prove the following results in complexity theory. (1) The Plurality is Stablest Conjecture (i.e., if votes have been corrupted or miscounted, the best way to determine the winner of an election is to take the plurality.) (2) Sharp hardness of approximation for the MAX-m-CUT problem, assuming the Unique Games Conjecture, which is a central problem in complexity theory of similar importance to the P versus NP problem. (3) Sharp hardness of approximation for the product state Quantum MAX-CUT problem, assuming the Unique Games Conjecture. (4) A weak version of the Unique Games Conjecture over the field of two elements. (5) Improved nonconvergence of the Adam optimization method for online function minimization, for a larger range of parameters. The projects (1) through (4) are closely related, since (1) implies (2), and proving (3) involves a variant of (1). Also, the methods to be explored for (4) are closely related to those used for (1), (2) and (3).

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.