We prove that every n-vertex planar graph G with no triangle sharing an edge with a 4-cycle has independence ratio n/α(G) ≤ 4 − ε for ε = 1/30. This result implies that the same bound holds for 4-cycle-free planar graphs and planar graphs with no adjacent triangles and no triangle sharing an edge with a 5-cycle. For the latter case we strengthen the bound to ε = 2/9. Joint work with Tom Kelly, Sid Kolichala, and Jatong Su.

We analyze the asymptotic number and typical structure of claw-free graphs at constant edge densities. First we prove a formula for the asymptotics of the logarithm of the number of claw-free graphs at all constant edge densities. We show that the problem exhibits a second-order phase transition at edge density (5-\sqrt{5})/4. The asymptotic formula arises by solving a variational problem over graphons. In the supercritical regime there is a unique optimal graphon, while in the subcritical regime there is an infinite set of optimal graphons. By analyzing lower-order terms of the counts, we pinpoint a unique optimal graphon that captures the typical structure in the subcritical regime, and we prove precise asymptotic formulas. We also analyze the probability of claw-freeness in G(n,p) for constant p, obtaining a formula for the large deviation rate function for claw-freeness and analyzing lower-order terms of the probabilities. Joint work with Will Perkins.

The textbook algorithm for single-source shortest paths with real-valued edge weights runs in $O(mn)$ time on a graph with $m$ edges and $n$ vertices. A recent breakthrough algorithm by Fineman [Fin24] takes $\tilde{O}(mn^{8/9})$ randomized time. We present an $\tilde{O}(mn^{4/5})$ randomized time algorithm building on ideas from [Fin24]. 

We consider the problem of preprocessing an n×n matrix M, and supporting queries that, for any vector v, returns the matrix-vector product Mv. This problem has been extensively studied in both theory and practice: on one side, practitioners have developed algorithms that are highly efficient in practice, whereas theoreticians have proven that the problem cannot be solved faster than naive multiplication in the worst-case. This lower bound holds even in the average-case, implying that existing average-case analyses cannot explain this gap between theory and practice. Therefore, we study the problem for structured matrices. We show that for n×n matrices of VC-dimension d, the matrix-vector multiplication problem can be solved with O~(n^2) preprocessing and O~(n^2−1/d) query time. Given the low constant VC-dimensions observed in most real-world data, our results posit an explanation for why the problem can be solved so much faster in practice. Moreover, our bounds hold even if the matrix does not have a low VC-dimension, but is obtained by (possibly adversarially) corrupting at most a subquadratic number of entries of any unknown low VC-dimension matrix. Our results yield the first non-trivial upper bounds for many applications. In previous works, the online matrix-vector hypothesis (conjecturing that quadratic time is needed per query) was used to prove many conditional lower bounds, showing that it is impossible to compute and maintain high-accuracy estimates for shortest paths, Laplacian solvers, effective resistance, and triangle detection in graphs subject to node insertions and deletions in subquadratic time. Yet, via a reduction to our matrix-vector-multiplication result, we show we can maintain the aforementioned problems efficiently if the input is structured, providing the first subquadratic upper bounds in the high-accuracy regime. 

Service systems like data centers and ride-hailing are popularly modeled as queueing systems in the literature. Such systems are primarily studied in the steady state due to their analytical tractability. However, almost all applications in real life do not operate in a steady state, so there is a clear discrepancy in translating theoretical queueing results to practical applications. To this end, we provide a finite-time convergence for Erlang-C systems (also known as $M/M/n$ queues), providing a stepping stone towards understanding the transient behavior of more general queueing systems. We obtain a bound on the Chi-square distance between the finite time queue length distribution and the stationary distribution for a finite number of servers. We then use these bounds to study the behavior in the many-server heavy-traffic asymptotic regimes. The Erlang-C model exhibits a phase transition at the so-called Halfin-Whitt regime. We show that our mixing rate matches the limiting behavior in the Super-Halfin-Whitt regime, and matches up to a constant factor in the Sub-Halfin-Whitt regime.

To prove such a result, we employ the Lyapunov-Poincaré approach, where we first carefully design a Lyapunov function to obtain a negative drift outside a finite set. Within the finite set, we develop different strategies depending on the properties of the finite set to get a handle on the mixing behavior via a local Poincaré inequality. A key aspect of our methodological contribution is in obtaining tight guarantees in these two regions, which when combined give us tight mixing time bounds. We believe that this approach is of independent interest for studying mixing in reversible countable-state Markov chains more generally. This is a joint work with Professor Sushil Mahavir Varma and Professor Siva Theja Maguluri.

Many iterative algorithms in optimization, computational geometry, computer algebra, and other areas of computer science require repeated computation of some algebraic expression whose input changes slightly from one iteration to the next. Although efficient data structures have been proposed for maintaining the solution of such algebraic expressions under low-rank updates, most of these results are only analyzed under exact arithmetic (real-RAM model and finite fields) which may not accurately reflect the complexity guarantees of real computers. We analyze the stability and bit complexity of such data structures for expressions that involve the inversion, multiplication, addition, and subtraction of matrices under the word-RAM model. We show that the bit complexity only increases linearly in the number of matrix operations in the expression. In addition, we consider the bit complexity of maintaining the determinant of a matrix expression. We show that the required bit complexity depends on the logarithm of the condition number of matrices instead of the logarithm of their determinant.

Based on joint work with Emile Anand, Jan van den Brand, and Mehrdad Ghadiri.

We study the multi-agent Smoothed Online Convex Optimization (SOCO) problem, where N agents interact through a communication graph. In each round, each agent receives a (possibly heterogeneous) strongly convex hitting cost function in an online fashion and selects an online action. The objective is to minimize the global cumulative cost, which includes the sum of individual hitting costs, a temporal "switching cost" for changing decisions, and a spatial "dissimilarity cost" that penalizes deviations in decisions among neighboring agents. We propose the first truly decentralized algorithm ACORD for multi-agent SOCO that provably exhibits asymptotic optimality. Our approach allows each agent to operate using only local information from its immediate neighbors in the graph. For finite-time performance, we establish that the optimality gap in the competitive ratio decreases with time horizon T and can be conveniently tuned based on the per-round computation available to each agent. Our algorithm benefits from a provably scalable computational complexity that depends only logarithmically on the number of agents and almost linearly on their degree within the graph. Moreover, our results hold even when the communication graph changes arbitrarily and adaptively over time. Finally, ACORD, by virtue of its asymptotic-optimality, is shown to be provably superior to the state-of-the-art LPC algorithm, while exhibiting much lower computational complexity. Extensive numerical experiments across various network topologies further corroborate our theoretical claims.

We present efficient counting and sampling algorithms for random $k$-SAT when the clause density satisfies $\alpha \le \frac{2^k}{\poly(k)}$. In particular, the exponential term $2^k$ matches the satisfiability threshold $\Theta(2^k)$ for the existence of a solution and the (conjectured) algorithmic threshold $2^k (\ln k) / k$ for efficiently finding a solution. Previously, the best-known counting and sampling algorithms required far more restricted densities $\alpha\lesssim 2^{k/3}$ [He, Wu and Yang '23]. Notably, our result goes beyond the lower bound $d\gtrsim 2^{k/2}$ for worst-case $k$-SAT with bounded-degree $d$ [Bez{\'{a}}kov{\'{a}} et al. '19], showing that for counting and sampling, the average-case random $k$-SAT model is computationally much easier than the worst-case model.

At the heart of our approach is a new refined analysis of the recent novel coupling procedure of Wang and Yin [FOCS '24], utilizing the structural properties of random constraint satisfaction problems (CSPs). Crucially, our analysis avoids reliance on the $2$-tree structure used in prior works, which cannot extend beyond the worst-case threshold $2^{k/2}$. Instead, we employ a witness tree similar to that used in the analysis of the Moser-Tardos algorithm for the Lov\'{a}sz Local lemma, which may be of independent interest. Our new analysis provides a universal framework for efficient counting and sampling for random atomic CSPs, including, for example, random hypergraph colorings. At the same time, it immediately implies as corollaries several structural and probabilistic properties of random CSPs that have been widely studied but rarely justified, including replica symmetry and non-reconstruction.

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.

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. 

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.

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.

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.

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.

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.

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.

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.

For a parameter ε ∈ (0, 1/2],  a set of ε-locality-sensitive orderings (LSOs) has the property that for any two points p, q ∈ [0, 1)^d, there exists an order in the set such that all points between p and q (in the ordering) are ε-close to either p or q. 

These orderings enable simple algorithms for several low-dimensional proximity problems in computational geometry, including dynamic bichromatic closest pair, dynamic spanners, dynamic approximate minimum spanning trees, dynamic fault-tolerant spanners, and nearest neighbor search.

In this talk, we will discuss the initial construction of LSOs, our recent work (in collaboration with Sariel Har-Peled) that provides a new construction with a reduced set size, and how this can be applied to solve geometric problems.

The minimum cost flow problem asks for a flow in a network that minimizes the cost along the edges used, subject to capacity and demand constraints. Interior point methods have been extensively applied to solve this and related problems.

We study this problem in a streaming setting, where we have a limited amount of space and are given the input as a stream of data that is presented as a sequence of items that can only be examined in a certain number of passes. We show that we can solve the minimum cost flow problem exactly with $O(\sqrt{n})$ passes through the input and $O(n^{1.5})$ space. Notably, this also gives the first oracle for min-cost flows in $O(n^{1.5})$ space, beating the naive bound of $O(n^2)$ space required to store the value of the flow along each edge. Joint work with Jan van den Brand.

Consider a hypercube [0,1]^n and an intersecting hyperplane described by a^⊤x = b. Let polytope P be the portion of the cube clipped by this hyperplane, described by a^⊤x ≤ b, x ∈ [0,1]^n. Computing the volume of such a polytope is known to be #P-Hard.

We propose a deterministic algorithm that estimates the volume of P within relative error 1±ε in time polynomial in inputs a, b, n and 1/ε (fully polynomial approximation scheme). In our algorithm we use a known approximation scheme for counting knapsack solutions in order to estimate the number of points that lie on a grid in our polytope, and use this grid to approximate the volume. Joint work with Santosh Vempala.

Over the past decades, a fascinating computational phase transition has been identified in sampling from Gibbs distributions. Though, the computational complexity at the critical point remains poorly understood, as previous algorithmic and hardness results all required a constant slack from this threshold.

In this talk, I will introduce our recent result on resolving this open question at the critical phase transition threshold, thus completing the picture of the computational phase transition. Specifically, we show that for the hardcore model on graphs with maximum degree $\Delta\ge 3$ at the uniqueness threshold $\lambda = \lambda_c(\Delta)$, the mixing time of Glauber dynamics is upper bounded by a polynomial in $n$, but is not nearly linear in the worst case. Similar results are established in the critical Ising model.

This talk is based on joint work with Xiaoyu Chen, Zongchen Chen and Yitong Yin.

Abstract: We introduce the pipeline intervention problem, defined by a layered directed acyclic graph and a set of stochastic matrices governing transitions between successive layers. The graph is a stylized model for how people from different populations are presented opportunities, eventually leading to some reward. In our model, individuals are born into an initial position (i.e. some node in the first layer of the graph) according to a fixed probability distribution, and then stochastically progress through the graph according to the transition matrices, until they reach a node in the final layer of the graph; each node in the final layer has a reward associated with it. The pipeline intervention problem asks how to best make costly changes to the transition matrices governing people's stochastic transitions through the graph, subject to a budget constraint. We consider two objectives: social welfare maximization, and a fairness-motivated maximin objective that seeks to maximize the value to the population (starting node) with the least expected value. We consider two variants of the maximin objective that turn out to be distinct, depending on whether we demand a deterministic solution or allow randomization. For each objective, we give an efficient approximation algorithm (an additive FPTAS) for constant width networks. We also tightly characterize the "price of fairness" in our setting: the ratio between the highest achievable social welfare and the highest social welfare consistent with a maximin optimal solution. Finally we show that for polynomial width networks, even approximating the maximin objective to any constant factor is NP hard, even for networks with constant depth. This shows that the restriction on the width in our positive results is essential.

Abstract: A $k$-uniform hypergraph $H = (V, E)$ is $k$-partite if $V$ can be partitioned into $k$ sets $V_1, \ldots, V_k$ such that each edge in $E$ contains precisely one vertex from each $V_i$. For example, a 2-partite 2-uniform hypergraph is a bipartite graph. In this talk, we will discuss extensions of results on bipartite graphs to this more general setting of hypergraphs. Specifically, we will consider list colorings, balanced colorings, and balanced independent sets.

Abstract: In the Nash social welfare problem the goal is to assign indivisible goods to agents to maximize the geometric mean of their valuations. There is a natural convex relaxation, but it has unbounded integrality gap. By constructing tighter relaxations, it is possible to obtain constant-factor approximation algorithms. We will cover two such relaxations, and then discuss the new challenges and surprises when we try to extend the approach to the case of weighted Nash social welfare.

Abstract: Gibbs-sampling, also known as coordinate hit-and-run (CHAR), is a random walk used to sample points uniformly from convex bodies. Its transition rule is simple: Given the current point p, pick a random coordinate i and resample the i'th coordinate of p according to the distribution induced by fixing all other coordinates. Despite its use in practice, strong theoretical guarantees regarding the mixing time of CHAR for sampling from convex bodies were only recently shown in works of Laddha and Vempala, Narayanan and Srivastava, and Narayanam, Rajaraman and Srivastava. In the work of Laddha and Vempala, as part of their proof strategy, the authors introduced the notion of the $\ell_0$ isoperimetric coefficient of a measurable set and provided a lower bound for the quantity in the case of axis-aligned cubes. In this talk we will present some new results regarding the $\ell_0$ isoperimetric coefficient of measurable sets. In particular we pin down the exact order of magnitude of the $\ell_0$ isoperimetric coefficient of axis-aligned cubes and present a general upper bound of the $\ell_0$ isoperimetric coefficient for any measurable set. As an application, we will mention how the results give a moderate improvement in the mixing time of CHAR.

Abstract: A graph $G$ is \textit{$k$-locally sparse} if for each vertex $v \in V(G)$, the subgraph induced by its neighborhood contains at most $k$ edges. Alon, Krivelevich, and Sudakov showed that for $f > 0$ if a graph $G$ of maximum degree $\Delta$ is $\Delta^2/f$-locally-sparse, then $\chi(G) = O\left(\Delta/\log f\right)$. We introduce a more general notion of local sparsity by defining graphs $G$ to be \textit{$(k, F)$-locally-sparse} for some graph $F$ if for each vertex $v \in V(G)$ the subgraph induced by the neighborhood of $v$ contains at most $k$ copies of $F$. Employing the R\"{o}dl nibble method, we prove the following generalization of the above result: for every bipartite graph $F$, if $G$ is $(k, F)$-locally-sparse, then $\chi(G) = O\left( \Delta /\log\left(\Delta k^{-1/|V(F)|}\right)\right)$. This improves upon results of Davies, Kang, Pirot, and Sereni who consider the case when $F$ is a path. Our results also hold for list and correspondence coloring in the more general so-called ``color-degree'' setting.

Abstract: Optimizing decisions often leads to disparities in costs among different groups, raising the question of how to select the most equitable fairness objective. Motivated by this, we consider the portfolio problem: given a combinatorial problem and a class C of equity or fairness objectives, an \alpha-approximate portfolio is a subset of the feasible cost vectors to the problem such that for each equity objective in C, the portfolio has an $\alpha$-approximately optimal solution to the problem for that equity objective. Portfolios naturally select good representative solutions for a given problem when multiple notions of equity must be considered, and are useful from an operational perspective. Increasing the size of the portfolio decreases the achievable approximation factor \alpha. We study this trade-off for many fundamental combinatorial problems and for various classes C of equity objectives, such as top-k, ordered, and symmetric monotonic norms. When the set of feasible cost vectors forms a polyhedron with a constant number of constraints, we give exponential improvements on portfolio sizes. Our technique is based on multiple linearizations of convex norm objectives and a novel primal-dual counting argument. For the special case of identical jobs scheduling problem to balance machine loads on d machines, we characterize the trade-off between portfolio size and approximation up to log log d factor. I will close with new algorithmic and counting questions that stem from this work.

Abstract: Let Sn denote the symmetric group and let W(Sn) denote the weak order of Sn. Through a surprising connection to a subset of parking functions, which we call unit Fubini rankings, we provide a complete characterization and enumeration for the total number of Boolean intervals in W(Sn) and the number of Boolean intervals of rank k in W(Sn). Furthermore, for any π ∈ Sn, we establish that the number of Boolean intervals in W(Sn) with minimal element π is a product of Fibonacci numbers. 

This talk is based on work with Jennifer Elder, Pamela E. Harris, and Jan Kretschmann.

Affiliation: Adam Mickiewicz University, Poznan

Abstract: An ordered matching M_n is a partition of a linearly ordered set of size 2n into n pairs (called edges). Taking the linear ordering into account, every pair of edges forms one of three patterns: AABB, ABBA, or ABAB. A submatching with all pairs of edges forming the same pattern is called a clique. In my talk, I will first show an Erdos-Szekeres type result guaranteeing a large clique in every matching M_n.  Then I will move on to a random (uniform) setting and investigate the largest size of a clique of a given type (pattern) present in almost all matchings. Finally, I will attempt to generalize these results to r-uniform hypermatchings, that is, partitions of a linearly ordered set of size rn into n r-element subsets.  This is joint work with Andrzej Dudek and Jarek Grytczuk.

Affiliation: CS, Georgia Tech

Abstract: We study the complexity of sampling from the stationary distribution of a mean-field SDE, or equivalently, the complexity of minimizing a functional over the space of probability measures which includes an interaction term. Our main insight is to decouple the two key aspects of this problem: (1) approximation of the mean-field SDE via a finite-particle system, via uniform-in-time propagation of chaos, and (2) sampling from the finite-particle stationary distribution, via standard log-concave samplers. Our approach is conceptually simpler and its flexibility allows for incorporating the state-of-the-art for both algorithms and theory. This leads to improved guarantees in numerous settings, including better guarantees for optimizing certain two-layer neural networks in the mean-field regime.

Affiliation: ISyE, Georgia Tech

Abstract: Stochastic approximation is an iterative algorithm to find the fixed point of the operator given its noisy samples. It has been widely applied in machine learning and reinforcement learning. In many settings, it is implemented in a two-time scale manner where one time scale estimates an auxiliary parameter of the system while the other uses this estimate to find the fixed point. Recently, there has been an increasing focus on how fast these algorithms converge to the fixed point. In this paper, we analyze two-time scale linear stochastic approximation when the noise follows Markovian behavior and characterize the rate of the convergence of the algorithm.

Affiliation: Math, Georgia Tech

Abstract: (We will give a brief overview of the discharging method, so no prior knowledge of discharging is required). Odd coloring (resp, PCF coloring) is a stricter form of proper vertex coloring in which every nonisolated vertex is required to have a color in its neighborhood with odd multiplicity (resp, with multiplicity 1).  We introduce a new tool useful for these colorings, based on greedy coloring, which we call the forb-flex method. Combining this with the discharging method allows us to prove $\chi_{\mathsf{PCF}}(G) \leq 4$ for planar graphs of girth at least 11, and $\chi_{\mathsf{o}}(G) \leq 4$ for planar graphs of girth at least 10, improving upon the recent works of Cho, Choi, Kwon, and Park. 

Affiliation: CS, Georgia Tech

Abstract: Machine Learning models are increasingly used to support or substitute decision making. In situations where skilled experts are needed, it is crucial to learn how to reduce their burden and delegate decisions to a model when its performance is at least of equal quality. However, models are often pre-trained and fixed, while tasks arrive sequentially, and their distribution may shift. In that case, the respective performance of the decision makers may change and the deferral algorithm must remain adaptive. 

In this talk, I will introduce a new  cost-constrained contextual bandit model for this online learning-to-defer problem. Additionally, I will present an algorithm for the problem from (Agrawal & Devanur, 2016) and present our empirical results on datasets from human subjects. 

Abstract: In this talk, we will survey results on edge-coloring algorithms for simple graphs with few colors. We will give a high level overview of the ideas behind classical and recent algorithms for coloring with 2\Delta - 1, \Delta+1, and (1+\epsilon)\Delta colors. 

Abstract: The connections between convex optimization and logconcave sampling have been considerably enriched in the past decade with many conceptual and mathematical analogies. For instance, the Langevin algorithm can be viewed as a sampling analogue of gradient descent and has condition-number-dependent guarantees on its performance. In the early 1990s, Nesterov and Nemirovski developed the Interior-Point Method (IPM) for convex optimization based on self-concordant barriers, providing efficient algorithms for structured convex optimization, often faster than the general method. This raises the following question: Can we develop an analogous IPM for structured sampling problems?

 In 2012, Kannan and Narayanan proposed the Dikin walk for uniformly sampling polytopes, and an improved analysis was given in 2020 by Laddha-Lee-Vempala. The Dikin walk uses a local metric defined by a self-concordant barrier for linear constraints. In this talk, we demonstrate the generality of this approach: developing and adapting IPM's machinery with the Dikin walk for poly-time sampling algorithms. Our IPM-based sampling framework provides an efficient warm start and goes beyond uniform distributions and linear constraints. As an illustrative example, we demonstrate how this approach gives the fastest algorithms to sample uniform, exponential, or Gaussian distributions on a truncated PSD cone.

Abstract: Multi-commodity flow is a generalization of maximum flow where more than one type of commodity is routed through the network. Recent advances in single-commodity flow have used graph-specific techniques, but improvements to multi-commodity flow have come from improvements to general linear program solvers.

In this talk, we describe how to speed up the robust central path method for multi-commodity flow on dense graphs by using graph data structures. This is the first improvement to high-accuracy multi-commodity flow algorithms that does not just stem from improvements to general linear program solvers.

Based on joint work with Jan van den Brand.

Abstract: A classic result from optimal stopping theory asks when one should stop and accept a value from a sequence of observed values, presented one by one, if one knows the distributions that these values are coming from and wants to select the maximum. The catch is that, if a value is rejected, it can never be selected again. This setting, which combines online decision making with stochastic uncertainty, is called the prophet inequality. Over the past decade, there have been several exciting discoveries, connecting auction theory and online combinatorial optimization with prophet inequality-type problems.

In this talk, we cover some of the standard ideas and results on prophet inequalities and online combinatorial optimization. Afterwards, we present the first results in a new direction that studies prophet inequalities for minimization instead, a setting which presents rich and qualitatively different results from the maximization case. Our approach aims to unify the maximization and minimization results into a single framework via the use of extreme value theory.

Abstract: We consider the algorithmic problem of finding large balanced independent sets in sparse random bipartite graphs, and more generally the problem of finding independent sets with specified proportions of vertices on each side of the bipartition. In a bipartite graph it is trivial to find an independent set of density at least half (take one of the partition classes). In contrast, in a random bipartite graph of average degree d, the largest balanced independent sets (containing equal number of vertices from each class) are typically of density (2 + od(1)) log d/d . Can we find such large balanced independent sets in these graphs efficiently? By utilizing the overlap gap property and the low-degree algorithmic framework, we prove that local and low-degree algorithms (even those that know the bipartition) cannot find balanced independent sets of density greater than (1 + ε) log d/d for any ε > 0 fixed and d large but constant. 

Abstract: In a seminal paper, Kannan and Lovász (1988) considered a quantity μ_KL(Λ,K) which denotes the best volume-based lower bound on the covering radius μ(Λ,K) of a convex body K with respect to a lattice Λ. Kannan and Lovász proved that μ(Λ,K)≤n⋅μ_KL(Λ,K) and the Subspace Flatness Conjecture by Dadush (2012) claims a O(log(n)) factor suffices, which would match the lower bound from the work of Kannan and Lovász. We settle this conjecture up to a constant in the exponent by proving that μ(Λ,K)≤O(log^3(n))⋅μ_KL(Λ,K). Our proof is based on the Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017). Following the work of Dadush (2012, 2019), we obtain a (log(n))^O(n)-time randomized algorithm to solve integer programs in n variables. Another implication of our main result is a near-optimal flatness constant of O(n*log^3(n)).

Abstract: Large learning rates, when applied to gradient descent for nonconvex optimization, yield various implicit biases, including edge of stability, balancing, and catapult. There are a lot of theoretical works trying to analyze these phenomena, while the high level idea is still missing: it is unclear when and why these phenomena occur. In this talk, I will show that these phenomena are actually various tips of the same iceberg. They occur when the objective function of optimization has some good regularity. This regularity, together with the effect of large learning rate on guiding gradient descent from sharp regions to flatter ones, leads to the control of the largest eigenvalue of Hessian, i.e., sharpness, along the GD trajectory, which results in various phenomena. The result is based on the nontrivial convergence analysis under large learning rate on a family of nonconvex functions of various regularities without Lipschitz gradient which is usually a default assumption in nonconvex optimization. In addition, it contains the first non-asymptotic result on the rate of convergence in this circumstance. Neural network experiments will also be presented to validate this result.

Abstract: We characterize Borel line graphs in terms of 10 forbidden induced subgraphs, namely the 9 finite graphs from the classical result of Beineke together with a 10th infinite graph associated to the equivalence relation $\E_0$ on the Cantor space. As a corollary, we prove a partial converse to the Feldman--Moore theorem, which allows us to characterize all locally countable Borel line graphs in terms of their Borel chromatic numbers.

Abstract: We give a polynomial-time algorithm for unsupervisedly learning high-dimensional halfspaces with margins in $d$-dimensional space to within the desired Total Variation (TV) distance. Notably, our algorithm does not need labels and establishes the unique (and efficient) identifiability of the hidden halfspace under our distributional assumption. The algorithm uses only the first two moments of suitable re-weightings of the empirical distribution. Its analysis uses classical facts about generalized Dirichlet polynomials and relies crucially on a new monotonicity property of the moment ratio of truncations of logconcave distributions.

Prior work addressed the special case when the underlying distribution is Gaussian via Non-Gaussian Component Analysis. We improve on this by providing polytime guarantees based on TV distance, in place of existing moment-bound guarantees that can be super-polynomial. Our work is also the first to go beyond Gaussians in this setting.

Abstract: We consider the problem of maximizing the size of a common independent set between a general matroid and a partition matroid whose parts arrive online. This captures the classic online bipartite matching problem when both matroids are partition matroids. Our main result is a (1 - 1/e)-competitive algorithm for the fractional version of this problem. This applies even for the poly-matroid setting, where the rank function of the offline matroid is replaced with a general monotone submodular function. The key new ingredient for this result is the construction of a "water level" vector for poly-matroids, which allows us to generalize the classic water-filling algorithm for online bipartite matching. This construction reveals connections to submodular utility allocation markets and principal partition sequences of matroids.

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.