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.

TBD

TBD

TBD