The Georgia Tech ACO Student Seminar is run by students in the Algorithms, Combinatorics, & Optimization program at Georgia Tech.
The purpose of this seminar is to keep students updated with current research, and to give students a venue to present their work. Any topic related (but not restricted) to algorithms, combinatorics, and optimization is very welcome. You can present research results, demo a work in progress, or just share something of general interest. There will also be occasional talks by ACO faculty and visitors. (Post-docs are welcome too!)
In Spring 2025, the seminar will meet on Fridays in Skiles 006 from 1-2pm. For more information please refer to the announcement sent by the organizers (or contact them directly). Subscribe to the mailing list aco-announce (or send an email to sympa@lists.gatech.edu with the subject line "subscribe aco-announce") to receive the announcements regularly.
If you are interested in giving a talk, you can contact any of the organizers: Aiya Kuchukova, Albert Weng, Jade Lintott, Yuexing (April) Niu. (Thanks to Max Dabagia and Sam van der Poel for organizing the seminar with us previously)
August 22th: Hoang Huy Nguyen (Georgia Tech)
Gold-medalist Performance in Solving Olympiad Geometry with AlphaGeometry2
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.
August 29th: Kalen Patton (Georgia Tech)
Online Allocation with Concave DR-Submodular Objectives
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.
September 5th: Ruben Ascoli (Georgia Tech)
Polynomial-to-Exponential Transition in Hypergraph Ramsey Numbers
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.
September 19th: No Seminar
Skiles 005 and 006 are reserved for the Colloquium.
September 26th: Aiya Kuchukova (Georgia Tech)
Sampling Colorings with Fixed Color Class Sizes
TBD
October 3rd: Caleb McFarland (Georgia Tech)
What do signed graphs have to do with integer programming?
TBD
October 31: Jacob Platnick (Georgia Tech)
Redistricting on dense random graphs
TBD