Classical online optimization theory focuses on regret guarantees for convex Lipschitz functions. However, online optimization problems motivated by machine learning for algorithm design fall outside this regime, since typically an algorithm’s performance as a function of its hyperparameters is a highly volatile function. This has inspired recent work on online optimization of piecewise-Lipschitz functions with complex transition boundaries. We provide open questions in this direction. Resolving these questions would advance the learning-theoretic foundation for adaptive algorithm design by clarifying when desirable sublinear regret guarantees are possible for learning the algorithms from online problem instances.

We study the intersection of a random geometric graph with an Erdős–Rényi graph. Specifically, we generate the random geometric graph G ( n , r ) by choosing n points uniformly at random from D = [ 0 , 1 ] 2 and joining any two points whose Euclidean distance is at most r . We let G ( n , p ) be the classical Erdős–Rényi graph, i.e. it has n vertices and every pair of vertices is adjacent with probability p independently. In this note we study G ( n , r , p ) ≔ G ( n , r ) ∩ G ( n , p ) . One way to think of this graph is that we take G ( n , r ) and then randomly delete edges with probability 1 − p independently. We consider the clique number, independence number, connectivity, Hamiltonicity, chromatic number, and diameter of this graph where both p ( n ) → 0 and r ( n ) → 0 ; the same model was studied by Kahle et al. (2023) for r ( n ) → 0 but p fixed.

We consider a simple model of a growing cluster of points in R d , d ≥ 2 . Beginning with a point X 1 located at the origin, we generate a random sequence of points X 1 , X 2 , … , X i , … , . To generate X i , i ≥ 2 we choose a uniform integer j in [ i − 1 ] = 1 , 2 , … , i − 1 and then let X i = X j + D i where D i = ( δ 1 , … , δ d ) . Here the δ j are independent copies of the Normal distribution N ( 0 , σ i ) , where σ i = i − α for some α > 0 . We prove that for any α > 0 the resulting point set is bounded a.s., and moreover, that the points generated look like samples from a β -dimensional subset of R d from the standpoint of the minimum lengths of combinatorial structures on the point-sets, where β = min ( d , 1 / α ) .

We prove that a polynomial fraction of the set of k-component forests in the m × n grid graph have equal numbers of vertices in each component, for any constant k. This resolves a conjecture of Charikar, Liu, Liu, and Vuong, and establishes the first provably polynomial-time algorithm for (exactly or approximately) sampling balanced grid graph partitions according to the spanning tree distribution, which weights each k-partition according to the product, across its k pieces, of the number of spanning trees of each piece. Our result follows from a careful analysis of the probability a uniformly random spanning tree of the grid can be cut into balanced pieces. Beyond grids, we show that for a broad family of lattice-like graphs, we achieve balance up to any multiplicative (1 ± ε) constant with constant probability. More generally, we show that, with constant probability, components derived from uniform spanning trees can approximate any given partition of a planar region specified by Jordan curves. This implies polynomial-time algorithms for sampling approximately balanced tree-weighted partitions for lattice-like graphs. Our results have applications to understanding political districtings, where there is an underlying graph of indivisible geographic units that must be partitioned into k population-balanced connected subgraphs. In this setting, tree-weighted partitions have interesting geometric properties, and this has stimulated significant effort to develop methods to sample them.

We consider the problem of generating uniformly random partitions of the vertex set of a graph such that every piece induces a connected subgraph. For the case where we want to have partitions with linearly many pieces of bounded size, we obtain approximate sampling algorithms based on Glauber dynamics which are fixed-parameter tractable with respect to the bandwidth of G, with simple-exponential dependence on the bandwidth. For example, for rectangles of constant or logarithmic width this gives polynomial-time sampling algorithms. More generally, this gives sub-exponential algorithms for bounded-degree graphs without large expander sub-graphs (for example, we obtain time algorithms for square grids). In the case where we instead want partitions with a small number of pieces of linear size, we show that Glauber dynamics can have exponential mixing time, even just for the case of 2 pieces, and even for 2-connected sub-graphs of the grid with bounded bandwidth.

Let $p=\frac{1+\varepsilon}{n}$. It is known that if $N=\varepsilon^3n\to\infty$, then with high probability (w.h.p.) $G_{n,p}$ has a unique giant largest component. We show that if in addition, $\varepsilon=\varepsilon(n)\to 0$, then w.h.p. the cover time of $G_{n,p}$ is asymptotic to $n\log^2N$; previously Barlow, Ding, Nachmias, and Peres had shown this up to constant multiplicative factors.

We consider the rank of a class of sparse Boolean matrices of size $n \times n$. In particular, we show that the probability that such a matrix has full rank, and is thus invertible, is a positive constant with value about 0.2574 for large $n$. The matrices arise as the vertex-edge incidence matrix of 1-out 3-uniform hypergraphs. The result that the null space is bounded in expectation can be contrasted with results for the usual models of sparse Boolean matrices, based on the vertex-edge incidence matrix of random $k$-uniform hypergraphs. For this latter model, the expected co-rank is linear in the number of vertices $n$, [A. Coja-Oghlan et al., in Proceedings of SODA, 2020, pp. 579--591], [C. Cooper, A. M. Frieze, and W. Pegden, in Proceedings of SODA, 2019, pp. 946--955]. For fields of higher order, the co-rank is typically Poisson distributed.

We determine, asymptotically in $n$, the distribution and mean of the weight of a minimum-weight $k$-clique (or any strictly balanced graph $H$) in a complete graph $K_n$ whose edge weights are independent random values drawn from the uniform distribution or other continuous distributions. For the clique, we also provide explicit (nonasymptotic) bounds on the distribution's cumulative distribution function in a form obtained directly from the Stein--Chen method and in a looser but simpler form. The direct form extends to other subgraphs and other edge-weight distributions. We illustrate the clique results for various values of $k$ and $n$. The results may be applied to evaluate whether an observed minimum-weight copy of a graph $H$ in a network provides statistical evidence that the network's edge weights are not independently distributed but have some structure.

The classical Beardwood-Halton-Hammersly theorem (1959) asserts the existence of an asymptotic formula of the form constant times square root n for the minimum length of a Traveling Salesperson Tour through n random points in the unit square, and in the decades since it was proved, the existence of such formulas has been shown for other such Euclidean functionals on random points in the unit square as well. Despite more than 50 years of attention, however, it remained unknown whether the minimum length TSP through n random points in the unit square was asymptotically distinct from its natural lower bounds, such as the minimum length spanning tree, the minimum length 2-factor, or, as raised by Goemans and Bertsimas, from its linear programming relaxation. We prove that the TSP on random points in Euclidean space is indeed asymptotically distinct from these and other natural lower bounds, and show that this separation implies that branch-and-bound algorithms based on these natural lower bounds must take nearly exponential time to solve the TSP to optimality, even in average case. This is the first average-case superpolynomial lower bound for these branch-and-bound algorithms.

We introduce and analyze the Walker-Breaker game, a variant of Maker-Breaker games where Maker is constrained to choose edges of a walk or path in a given graph $G$, with the goal of visiting as many vertices of the underlying graph as possible.

A recent theorem of Bissacot et al. [arXiv:0910.1824v2, 2010], proved using results about the cluster expansion in statistical mechanics, extends the Lovász local lemma by weakening the conditions under which its conclusion holds. In this note, we prove an algorithmic analogue of this result, extending Moser and Tardos's recent algorithmic local lemma [J. ACM, 57 (2010), 11], and providing an alternative proof of the theorem of Bissacot et al. applicable in the Moser--Tardos algorithmic framework.