ACO Student Seminar

Abstract: We present AlphaGeometry2, a significantly improved version of AlphaGeometry introduced in Trinh et al. (2024), which has now surpassed an average gold medalist in solving Olympiad geometry problems. To achieve this, we first extend the original AlphaGeometry language to tackle harder problems involving movements of objects, and problems containing linear equations of angles, ratios, and distances. This, together with support for non-constructive problems, has markedly improved the coverage rate of the AlphaGeometry language on International Math Olympiads (IMO) 2000-2024 geometry problems from 66% to 88%. The search process of AlphaGeometry2 has also been greatly improved through the use of Gemini architecture for better language modeling, and a novel knowledge-sharing mechanism that enables effective communication between search trees. Together with further enhancements to the symbolic engine and synthetic data generation, we have significantly boosted the overall solving rate of AlphaGeometry2 to 84% for all geometry problems over the last 25 years, compared to 54% previously. AlphaGeometry2 was also part of the system that achieved silver-medal standard at IMO 2024. Last but not least, we report progress towards using AlphaGeometry2 as a part of a fully automated system that reliably solves geometry problems directly from natural language input.
Joint work with the Google DeepMind team during the IMO run in 2024.

Online resource allocation problems are central challenges in economics and computer science, modeling situations in which n items arriving one at a time must each be immediately allocated among m agents. In such problems, our objective is to maximize a monotone reward function f(x) over the allocation vector x​, which describes the amount of each item given to each agent. In settings where f is concave and has "diminishing returns'' (monotone decreasing gradient), several lines of work over the past two decades have had great success designing constant-competitive algorithms, including the foundational work of Mehta et. al. (2005) on the Adwords problem and its follow-ups. Notably, while a greedy algorithm is 1/2-competitive in such settings, these works have shown that one can often obtain a competitive ratio of 1−1/e​≈0.632 in many settings when items are divisible (i.e. allowing fractional allocations). However, prior works have thus far used a variety of problem-specific techniques, leaving open the general question: Does a (1−1/e)-competitive fractional algorithm always exist for online resource allocation problems with concave, diminishing-returns objectives?

In this work, we answer this question affirmatively, thereby unifying and generalizing prior results for special cases. Our algorithm is one which makes continuous greedy allocations with respect to an auxiliary objective U(x). Using the online primal-dual method, we show that if U satisfies a "balanced" property with respect to f, then one can bound the competitiveness of such an algorithm. Our crucial observation is that there is a simple expression for U which has this balanced property for any f, yielding our general (1−1/e​)-competitive algorithm.

Abstract: Let r_k(s, e; t) denote the smallest N such that any red/blue edge coloring of the complete k-uniform hypergraph on N vertices contains either e red edges among some s vertices, or a blue clique of size t. Erdős and Hajnal introduced the study of this Ramsey number in 1972 and conjectured that for fixed s > k, there is a well defined value h_k(s) such that r_k(s, h_k(s)-1; t) is polynomial in t, while r_k(s, h_k(s); t) is exponential in a power of t. Erdős later offered $500 for a proof.

Conlon, Fox, and Sudakov proved the conjecture for k=3 and 3-adically special values of s, and Mubayi and Razborov proved it for k at least 4. We prove the conjecture for k=3 and all s, settling all remaining cases of the problem.

Joint work with Xiaoyu He and Hans Yu.

Classical results by Jerrum (1995) and Salas-Sokal (1997) show the possibility of efficient approximate counting and uniform sampling of proper colorings with $q \geq 2\Delta+1$ colors in graphs of maximum degree $\Delta$. For colorings with fixed color class sizes, Kierstand and Kostochka (2007) reproved the existence of equitable coloring (colorings where class sizes differ by at most 1) and provided a polynomial algorithm which produces such a coloring and requires only $q \geq \Delta+1$ colors. In this paper we provide efficient approximate counting and uniform sampling algorithms for colorings with fixed color class sizes that are equitable or close to equitable. The proof uses techniques such as zero-freeness of partition functions, Local Central Limit Theorems, and cluster expansion. We hope our result adds to the growing evidence of the possibility to efficiently sample fundamental combinatorial objects, such as colorings, with global constraints. Joint work with Will Perkins and Xavier Povill.

The talk will not assume any knowledge of sampling or statistical physics. 

TBD

Let A be a matrix and A_p its best rank p approximation. Computing A_p, for a relatively small p, is a task of fundamental importance.  One often stores  A_p and uses it as input in many downstream tasks. Typically, we want to choose p so that A_p capture most of  the energy of A, namely || A- A_p||_F < 10%  || A||_F, say. 

In practice, data is noisy and incomplete.  Thus, one only has access to a matrix A' = A+E, where E represents noise. The question is to find a low rank matrix B, given A', such that || A- B||_F < 10% || A||_F, say.  (We do not know p. )

We propose a very simple algorithm to this task, based on the idea of  "energy shrinkage".  The core of the method is a new perturbation bound for the difference ||A'_p -A_p||, which significantly improves bounds obtained using Eckard-Young-Mirsky theorem.  This is one of many recent new perturbations obtained by  the contour expansion method, introduced by Tran and the speaker a few years ago. 

TBD

Abstract: The success of modern Large Language Models (LLMs) is a technological breakthrough but foundations on which it is built has remained largely a mystery. A foundational understanding would vastly improve our ability to both diagnose potential issues (e.g. from a safety perspective) and also ability to push the capabilities of these models (e.g. in challenging settings such as reasoning and scientific discovery). Towards this broad goal, I will speak about two recent directions, both inspired by classical work in the theory of computation, with the aim to convey the importance of algorithmic insights even in the setting of LLMs.

First, we ask the question of how we can elicit new behavior from language models aimed towards tasks such as reasoning. A paradigm that has recently gained popularity is process verification, which aims to use guidance in language model generation. Though effective in principle, standard methods using them suffer compounding error with the length of the generated sequence, an issue particularly problematic due to the increase in the horizon of modern reasoning tasks. We present a new perspective on this problem by connecting the guidance problem to fundamental problems in approximate counting and sampling and present an algorithm, we dub VGB, that circumvents compounding of error with the horizon.

Secondly, we look at the problem of understanding the structure in language and models thereof. Again drawing inspiration from a classical area of TCS, the study of latent variable models, we present a new perspective on sequence models, which we call (extended) low logit rank. We demonstrate empirically that models in practice exhibit this structure in practice and use this structure to demonstrate surprising consequences such as sampling from language models by querying unrelated prompts. Motivated by this, we present theoretical results such as equivalence to low dimensional latent variable models, expressivity and learning guarantees. In particular, we present this as an approach to theoretically understand the structure in large language models. 

In summary, through this talk I aim to convey how perspectives from the theory of computation can inspire principled approaches to fundamental pressing problems in the study of large language models. This talk is based on joint works with Dhruv Rohatgi, Donya Saless, Yunchen Li, Ankur Moitra, Andrej Risteki, Dylan Foster, Noah Golowich and Allen Liu. 

Bio: Abhishek Shetty is the incoming Catherine M. and James E. Allchin Early-Career Assistant Professor in Computer Science at Georgia Tech, starting in Fall 2026. Currently, he is a FODSI postdoctoral fellow at Massachusetts Institute of Technology hosted by Costis Daskalakis, Ankur Moitra and Sasha Rakhlin and previously PhD student at the University of California at Berkeley advised by Nika Haghtalab. His research focuses on building fundamental connections between the theory of computation and machine learning, with particular interest in understanding the algorithmic and statistical role of data in generalization and sequential decision making. His research has been recognized with an Apple AI/ML fellowship and an ASA SCGS best student paper.