# ACO Student Seminar

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 Fall 2024, the seminar will meet on Fridays in Skiles 005 from 1-2pm. For more information, including the online meeting links, 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.

### Contact

If you are interested in giving a talk, you can contact any of the organizers: Max Dabagia, Aiya Kuchukova, Jade Lintott, and Sam van der Poel. (Thanks to Abhishek Dhawan, Jad Salem, and Reuben Tate for organizing the seminar previously.)

## Fall 2024 Talks

August 23: Aliaksei Semchankau (CMU)

On the sequence n! \bmod p

Abstract: Let $p$ be a prime, and let $\mathcal{A}$ be a set of residues of the sequence $1!, 2!, 3!, \ldots$ modulo $p$. We prove \[|\mathcal{A}| \geqslant (\sqrt{2} + o(1))\sqrt{p}.\] Now consider an interval $\mathcal{I} \subseteq \{0, 1, \ldots, p - 1\}$ of length $N > p^{7/8 + \varepsilon}$ and denote by $\mathcal{A}_{\mathcal{I}}$ the set of residues modulo $p$ it produces. Then we prove \[ |\mathcal{A}_{\mathcal{I}}| > (1 + o(1))\sqrt{p}.\]

Tools used are results from Algebraic Geometry as black boxes and simple combinatorial observations. This is a joint work with Alexandr Grebennikov, Arsenii Sagdeev, Aliaksei Vasilevskii, and available on arXiv: https://arxiv.org/abs/2204.01153.

August 30: Yunbum Kook (CS, Georgia Tech)

Rényi-infinity Uniform Sampling via Algorithmic Diffusion

Uniform sampling over a convex body is a fundamental algorithmic problem, yet convergence in KL or Rényi divergence of most samplers remains poorly understood. We introduce a constrained proximal sampler for uniformly sampling high-dimensional convex bodies. This principled algorithm achieves state-of-the-art runtime complexity with stronger guarantees on the output than previously known, namely in Rényi divergence (which implies TV, $W_2$, KL, $\chi^2$). The proof departs from known approaches for polytime algorithms for the problem --- we utilize a diffusion perspective to show contraction to the target distribution with the rate of convergence determined by functional isoperimetric constants of the stationary density. Notably, combining this sampler with a Gaussian cooling scheme results in Rényi-infinity uniform sampling with membership $d^3$ queries, where Rényi-infinity divergence is the strongest of commonly considered performance metrics.

September 6: Emile Anand (CS, Georgia Tech)

Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scale

We study reinforcement learning for global decision-making in the presence of many local agents, where the global decision-maker makes decisions affecting all local agents, and the objective is to learn a policy that maximizes the rewards of both the global and the local agents. Such problems find many applications, e.g. demand response, EV charging, queueing, etc. In this setting, scalability has been a long-standing challenge due to the size of the state/action space which can be exponential in the number of agents. This work proposes the \texttt{SUB-SAMPLE-Q} algorithm where the global agent subsamples $k\leq n$ local agents to compute an optimal policy in time that is only exponential in $k$, providing an exponential speedup from standard methods that are exponential in $n$. We show that the learned policy converges to the optimal policy in the order of $\tilde{O}(1/\sqrt{k}+\epsilon_{k,m})$ as the number of sub-sampled agents $k$ increases, where $\epsilon_{k,m}$ is the Bellman noise, by proving a novel generalization of the Dvoretzky-Kiefer-Wolfowitz inequality to the regime of sampling without replacement. We also conduct numerical simulations in a demand-response setting and a queueing setting. This is joint work with Guannan Qu.

September 13: Chi Hoi Yip (Georgia Tech)

Arithmetic progressions in Euclidean Ramsey theory

Euclidean Ramsey theory concerns Ramsey-type problems over Euclidean spaces. In this talk, I will discuss monochromatic arithmetic progressions in Euclidean Ramsey theory. Specifically, if $\ell_m$ denotes $m$ collinear points with consecutive points of distance one apart, we say that $\mathbb{E}^n \not \to (\ell_r,\ell_s)$ if there is a red/blue coloring of $n$-dimensional Euclidean space that avoids red congruent copies of $\ell_r$ and blue congruent copies of $\ell_s$. I will discuss a general framework on how to design algorithms to construct colorings avoiding short monochromatic arithmetic progressions in Euclidean Ramsey theory using some simple geometry and number theory. In particular, we prove $\mathbb{E}^n \not \to (\ell_3, \ell_{20})$, improving the best-known result $\mathbb{E}^n \not \to (\ell_3, \ell_{1177})$ by F\"uhrer and T\'oth, as well as $\mathbb{E}^n \not \to (\ell_4, \ell_{18})$ and $\mathbb{E}^n \not \to (\ell_5, \ell_{10})$ in the spirit of the classical result $\mathbb{E}^n \not \to (\ell_6, \ell_{6})$ due to Erd{\H{o}}s et. al. Joint work with Gabriel Currier and Kenneth Moore.

September 20: Mirabel Reid (CS, Georgia Tech)

The k-cap Process on Geometric Random Graphs

The k-cap (or k-winners-take-all) process on a graph works as follows: in each iteration, exactly k vertices of the graph are in the cap (i.e., winners); the next round winners are the vertices that have the highest total degree to the current winners, with ties broken randomly. This natural process is a simple model of firing activity in the brain. We study its convergence on geometric random graphs, revealing rather surprising behavior.

October 4: Split Session - Logan Post (Math, Georgia Tech) / Ruben Ascoli (Math, Georgia Tech)

Superpolynomial period lengths in the finite subtraction game / Finitely Dependent Processes

Given a finite move-set of positive integers, $A$, and starting with a heap of $n$ chips, Alice and Bob alternate turns; on each turn a player chooses $x\in A$ and subtracts $x$ chips from the heap. The game terminates when the number of chips becomes smaller than $\min\{A\}$ and no moves are possible. By the pigeonhole principle, $w^A(n)$ becomes periodic; the typical period length is a linear function of $\max\{A\}$. We investigate a generalization of this game with an initial seed dictating the winner at the end of the game, and show that the period length can be superpolynomial with $|A|=3$ moves. Joint work with Istvan Miklos.

--------------------------------------------------------

A k-dependent q-coloring of a (possibly infinite) graph G is a distribution on proper q-colorings of G such that subgraphs which are at distance more than k apart receive independent colorings, and the marginal distribution of colors is the same at every vertex. Seminal work of Holroyd and Ligget in 2016 showed that a 1-dependent 4-coloring of the integers exists. In this informal workshop-style presentation, I will discuss some of my favorite related unsolved problems.

October 11: William Frendreiss (Math, Georgia Tech)

Complexity in Algebraic Combinatorics

Abstract: Leslie Valiant’s seminal 1979 paper “Completeness Classes in Algebra” married the fields of theoretical computer science with algebraic combinatorics by introducing complexity classes VP and VNP to describe the complexity of polynomial computation. In this expository talk, we will explore developments in the field since Valiant’s paper, with a special focus on results involving the hardness of computing coefficients of special combinatorial polynomials. We will begin with a discussion on classes NP and #P. Then, we will introduce the Littlewood-Richardson coefficients, their connection with combinatorial structures, and complexity results related to their computation. Finally, as a short exercise, we will prove VNP-completeness of the matrix permanent and consequences of this. This presentation is inspired by Greta Panova’s lectures at the Max Planck Institute’s Summer School in Algebraic Combinatorics in July 2024.

October 18: Kalen Patton (Math, Georgia Tech)

Mechanisms and Prophet Inequalities with Graphical Dependencies

Abstract: In stochastic optimization settings, such as revenue-optimal auction design and prophet inequalities, we traditionally use n independent random variables to represent the values of n items. However, in practice, this assumption of independence often diverges from reality. On the other hand, strong impossibility results exist if we allow arbitrary correlations between item values. To reconcile the issues on both ends of this spectrum, recent research has pivoted towards exploring these problems under models of mild dependency.

In this talk, we will discuss our work on the optimal auction and prophet inequality problems within the framework of the popular graphical model of Markov Random Fields (MRFs), a choice motivated by its ability to capture complex dependency structures. Specifically, for the problem of selling n items to a single subadditive buyer, we show that simple mechanisms can obtain an O(Δ)-approximation to the optimal revenue, where Δ measures the strength of correlations in underlying MRF. This generalization as well as an exponential improvement on the previously best-known exp(O(Δ))-approximation results of Cai and Oikonomou (EC 2021) for additive and unit-demand buyers. For the prophet inequality problem, we obtain a similar exponential improvement. If time permits, we will also discuss some open questions and partial results for other stochastic problems under MRF dependencies. Based on joint work with Sahil Singla and Vasilis Livanos.

October 25: Chunyang Wang (Nanjing University)

A Sampling Lovász Local Lemma for Large Domain Sizes

We present polynomial-time algorithms for approximate counting and sampling solutions to constraint satisfaction problems (CSPs) with atomic constraints within the local lemma regime: $$pD^{2+o_q(1)}\lesssim 1.$$

When the domain size $q$ of each variable becomes sufficiently large, this almost matches the known lower bound $pD^2\gtrsim 1$ for approximate counting and sampling solutions to atomic CSPs [Bezáková et al, SICOMP '19; Galanis, Guo, Wang, TOCT '22], thus establishing an almost tight sampling Lovász local lemma for large domain sizes.

November 1: Daniel Hwang (Math, Georgia Tech)

Edge-Disjoint Spanning Trees on Star-Product Networks

Network topologies, or the design of networks, can be represented using the mathematical structure of graphs. In order to construct larger networks from two smaller networks, we can take their graph product. More specifically, we can take their star product, which is a generalization of the Cartesian product, to form star-product networks. Star-product networks have many benefits, such as low diameter and flexible structure, but in this presentation, we will also show that they have high parallelism by maximizing their number of edge-disjoint spanning trees (EDSTs). Our main result is an explicit construction of a near-maximal set of EDSTs for any star product, which can be extended under additional conditions. We also analyze their depth and discuss how close our results are to the theoretical maximum number of EDSTs. This presentation was completed in collaboration with Los Alamos National Laboratory and has been assigned LA-UR 24-31614. This is joint work with Kelly Isham, Laura Monroe, Kartik Lakhotia, Aleyah Dawkins, and Ales Kubicek.

November 8: Zhimeng Gao (CS, Georgia Tech)

Title TBA

Abstract TBA

November 22: Kyra Gunluk (CS, Georgia Tech)

Title TBA

Abstract TBA