Theory of Computing Report

August 11-13, 2025 Oxford, UK https://feasible-math.org/events/PC25/ Proof complexity is a vibrant area in the intersection of computational complexity, algorithms and mathematical logic exploring the inherent difficulty of proving statements in different formal proof systems. This workshop aims to cover both traditional topics and emerging trends in the field, including lower bounds on lengths of proofs, … Continue reading Proof Complexity 2025

By shacharlovett

Authors: Albert Brandl, Christian G. Fermüller, Gernot Salzer

This paper investigates the problem of testing clause sets for membership in classes known from literature. In particular, we are interested in classes defined via renaming: Is it possible to rename the predicates in a way such that positive and negative literals satisfy certain conditions? We show that for classes like Horn or OCC1N, the existence of such renamings can be decided in polynomial time, whereas the same problem is NP-complete for class PVD. The decision procedures are based on hyper-resolution; if a renaming exists, it can be extracted from the final saturated clause set.

Authors: Yaroslav Ivanashev

In this paper, we characterize the classes of languages and functions that are low for counting function classes. The classes #P and GapP have their low classes exactly characterized: Low(#P) = UP $\cap$ coUP and Low(GapP) = SPP. We prove that Low(TotP) = P, Low(SpanP) = NP $\cap$ coNP, and give characterizations of low function classes for #P, GapP, TotP, and SpanP. We establish the relations between NPSVt, UPSVt, and the counting function classes. For each of the inclusions between these classes we give an equivalent inclusion between language classes. We also prove that SpanP $\subseteq$ GapP if and only if NP $\subseteq$ SPP, and the inclusion GapP+ $\subseteq$ SpanP implies PH = $\Sigma_{2}^{P}$. For the classes #P, GapP, TotP, and SpanP we summarize the known results and prove that each of these classes is closed under left composition with FP+ if and only if it collapses to its low class of functions.

Authors: Duy Le

Cache systems fundamentally limit modern computing performance due to their inability to precisely capture data relationships. While achieving 85-92% hit rates, traditional systems rely on statistical heuristics that cannot guarantee relationship discovery, leading to suboptimal prefetching and resource waste. We present PFCS (Prime Factorization Cache System), which leverages the mathematical uniqueness of prime factorization to achieve deterministic relationship discovery with zero false positives. PFCS assigns unique primes to data elements and represents relationships as composite numbers, enabling the recovery of perfect relationships through factorization. A comprehensive evaluation across database, ML, and HPC workloads demonstrates an average performance improvement of x 6.2, 98.9% hit rates, and a 38% power reduction compared to state-of-the-art systems. The mathematical foundation provides formal guarantees impossible with approximation-based approaches, establishing a new paradigm for cache system design

Authors: Thomas Schibler, Subhash Suri, Jie Xue

We introduce the Polychromatic Traveling Salesman Problem (PCTSP), where the input is an edge weighted graph whose vertices are partitioned into $k$ equal-sized color classes, and the goal is to find a minimum-length Hamiltonian cycle that visits the classes in a fixed cyclic order. This generalizes the Bipartite TSP (when $k = 2$) and the classical TSP (when $k = n$). We give a polynomial-time $(3 - 2 * 10^{-36})$-approximation algorithm for metric PCTSP. Complementing this, we show that Euclidean PCTSP is APX-hard even in $R^2$, ruling out the existence of a PTAS unless P = NP.

Authors: Dinghua Shi, Yang Zhao, Guanrong Chen

The network homology Hk-core decomposition proposed in this article is similar to the k-core decomposition based on node degrees of the network. The C. elegans neural network and the cat cortical network are used as examples to reveal the symmetry of the deep structures of such networks. First, based on the concept of neighborhood in mathematics, some new concepts are introduced, including such as node-neighbor subnetwork and Betti numbers of the neighbor subnetwork, among others. Then, the Betti numbers of the neighbor subnetwork of each node are computed, which are used to perform Hk-core decomposition of the network homology. The construction process is as follows: the initial network is referred to as the H0-core; the H1-core is obtained from the H0-core by deleting some nodes of certain properties; the H2-core is obtained from the H1-core by deleting some nodes or edges of certain properties; the H3-core is obtained from the H2-core by deleting some nodes of certain properties or by retaining the nodes of certain properties, and so on, which will be described in detail in the main text. Throughout the process, the index of node involved in deleting edge needs to be updated in every step. The Hk-core decomposition is easy to implement in parallel. It has a wide range of applications in many fields such as network science, data science, computational topology, and artificial intelligence. In this article, we also show how to use it to simplify homology calculation, e.g. for the C. elegans neural network, whereas the results of decomposition are the H1-core, the H2-core, and the H3-core. Thus, the simplexes consisting of four highest-order cavities in the H3-core subnetwork can also be directly obtained.

Authors: Gianmarco Picarella, Marc van Kreveld, Frank Staals, Sjoerd de Vries

We study the problem of computing a convex region with bounded area and diameter that contains the maximum number of points from a given point set $P$. We show that this problem can be solved in $O(n^6k)$ time and $O(n^3k)$ space, where $n$ is the size of $P$ and $k$ is the maximum number of points in the found region. We experimentally compare this new algorithm with an existing algorithm that does the same but without the diameter constraint, which runs in $O(n^3k)$ time. For the new algorithm, we use different diameters. We use both synthetic data and data from an application in cancer detection, which motivated our research.

Authors: Hugo Akitaya, Matias Korman, Frederick Stock

A configuration of $n$ unit-cube-shaped \textit{modules} (or \textit{robots}) is a lattice-aligned placement of the $n$ modules so that their union is face-connected. The reconfiguration problem aims at finding a sequence of moves that reconfigures the modules from one given configuration to another. The sliding cube model (in which modules are allowed to slide over the face or edge of neighboring modules) is one of the most studied theoretical models for modular robots. In the sliding cubes model we can reconfigure between any two shapes in $O(n^2)$ moves ([Abel \textit{et al.} SoCG 2024]). If we are interested in a reconfiguration algorithm into a \textit{compact configuration}, the number of moves can be reduced to the sum of coordinates of the input configuration (a number that ranges from $\Omega(n^{4/3})$ to $O(n^2)$, [Kostitsyna \textit{et al.} SWAT 2024]). We introduce a new algorithm that combines both universal reconfiguration and an input-sensitive bound on the sum of coordinates of both configurations, with additional advantages, such as $O(1)$ amortized computation per move.

Authors: Marcia Fampa, Jon Lee

In 2022, we published a book, \emph{Maximum-Entropy Sampling: Algorithms and Application (Springer)}. Since then, there have been several notable advancements on this topic. In this manuscript, we survey some recent highlights.

Authors: Marthe Bonamy, Cyril Gavoille, Timothé Picavet, Alexandra Wesolek

We give a new, short proof that graphs embeddable in a given Euler genus-$g$ surface admit a simple $f(g)$-round $\alpha$-approximation distributed algorithm for Minimum Dominating Set (MDS), where the approximation ratio $\alpha \le 906$. Using tricks from Heydt et al. [European Journal of Combinatorics (2025)], we in fact derive that $\alpha \le 34 +\varepsilon$, therefore improving upon the current state of the art of $24g+O(1)$ due to Amiri et al. [ACM Transactions on Algorithms (2019)]. It also improves the approximation ratio of $91+\varepsilon$ due to Czygrinow et al. [Theoretical Computer Science (2019)] in the particular case of orientable surfaces. All our distributed algorithms work in the deterministic LOCAL model. They do not require any preliminary embedding of the graph and only rely on two things: a LOCAL algorithm for MDS on planar graphs with ``uniform'' approximation guarantees and the knowledge that graphs embeddable in bounded Euler genus surfaces have asymptotic dimension $2$. More generally, our algorithms work in any graph class of bounded asymptotic dimension where ``most vertices'' are locally in a graph class that admits a LOCAL algorithm for MDS with uniform approximation guarantees.

Authors: Debojyoti Bhattacharya, Subhabrata Paul

Let $G=(V, E)$ be an undirected graph. The set $N_G[x]=\{y\in V|xy\in E\}\cup \{x\}$ is called the closed neighbourhood of a vertex $x\in V$ and for an edge $e=xy\in E$, the closed neighbourhood of $e$ is the set $N_G[x]\cup N_G[y]$, which is denoted by $N_G[e]$ or $N_G[xy]$. A set $L\subseteq V$ is called \emph{liar's vertex-edge dominating set} of a graph $G=(V,E)$ if for every $e_i\in E$, $|N_G[e_i]\cap L|\geq 2$ and for every pair of distinct edges $e_i,e_j\in E$, $|(N_G[e_i]\cup N_G[e_j])\cap L|\geq 3$. The notion of liar's vertex-edge domination arises naturally from some applications in communication networks. Given a graph $G$, the \textsc{Minimum Liar's Vertex-Edge Domination Problem} (\textsc{MinLVEDP}) asks to find a liar's vertex-edge dominating set of $G$ of minimum cardinality. In this paper, we study this problem from an algorithmic point of view. We design two linear time algorithms for \textsc{MinLVEDP} in block graphs and proper interval graphs, respectively. On the negative side, we show that the decision version of liar's vertex-edge domination problem is NP-complete for undirected path graphs.

Authors: Yichun Yang, Rong-Hua Li, Meihao Liao, Guoren Wang

Effective Resistance (ER) is a fundamental tool in various graph learning tasks. In this paper, we address the problem of efficiently approximating ER on a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ with $n$ vertices and $m$ edges. First, we focus on local online-computation algorithms for ER approximation, aiming to improve the dependency on the approximation error parameter $\epsilon$. Specifically, for a given vertex pair $(s,t)$, we propose a local algorithm with a time complexity of $\tilde{O}(\sqrt{d}/\epsilon)$ to compute an $\epsilon$-approximation of the $s,t$-ER value for expander graphs, where $d=\min \{d_s,d_t\}$. This improves upon the previous state-of-the-art, including an $\tilde{O}(1/\epsilon^2)$ time algorithm based on random walk sampling by Andoni et al. (ITCS'19) and Peng et al. (KDD'21). Our method achieves this improvement by combining deterministic search with random walk sampling to reduce variance. Second, we establish a lower bound for ER approximation on expander graphs. We prove that for any $\epsilon\in (0,1)$, there exist an expander graph and a vertex pair $(s,t)$ such that any local algorithm requires at least $\Omega(1/\epsilon)$ time to compute the $\epsilon$-approximation of the $s,t$-ER value. Finally, we extend our techniques to index-based algorithms for ER computation. We propose an algorithm with $\tilde{O}(\min \{m+n/\epsilon^{1.5},\sqrt{nm}/\epsilon\})$ processing time, $\tilde{O}(n/\epsilon)$ space complexity and $O(1)$ query complexity, which returns an $\epsilon$-approximation of the $s,t$-ER value for any $s,t\in \mathcal{V}$ for expander graphs. Our approach improves upon the state-of-the-art $\tilde{O}(m/\epsilon)$ processing time by Dwaraknath et al. (NeurIPS'24) and the $\tilde{O}(m+n/\epsilon^2)$ processing time by Li and Sachdeva (SODA'23).

Authors: Aadityan Ganesh, Qianfan Zhang

We consider a revenue-optimizing auctioneer in single-dimensional environments with matroid feasibility constraints. Akbarpour and Li (2020) argue that any revenue-optimal, truthful, and credible mechanism requires unbounded communication. Recent works (Ferreira and Weinberg, 2020; Essaidi et al., 2022; Chitra et al., 2024) circumvent their impossibility for the single-item setting through the use of cryptographic commitments and blockchains. We extend their results to matroid feasibility constraints. At a high level, the two-round Deferred-Revelation Auction (DRA) discussed by Ferreira and Weinberg (2020) and Chitra et al., (2024) requires each bidder to submit a deposit, which is slashed upon presenting verifiable evidence indicating a deviation from the behaviour prescribed by the mechanism. We prove that the DRA satisfies truthfulness, credibility and revenue-optimality for all matroid environments when bidders' values are drawn from $\alpha$-strongly regular distributions for $\alpha > 0$. Further, we argue that the DRA is not credible for any feasibility constraint beyond matroids and for any smaller deposits than suggested by previous literature even in single-item environments. Finally, we modify the Ascending Deferred-Revelation Auction (ADRA) for single-item settings proposed by Essaidi et al., (2022) for arbitrary bidder value distributions. We implement a deferred-revelation variant of the deferred-acceptance auction for matroids due to Bikhchandani et al., (2011), which requires the same bounded communication as the ADRA.

Authors: Noam Horowicz, Tsvi Kopelowitz

In the snippets problem, the goal is to preprocess text $T$ so that given two patterns $P_1$ and $P_2$, one can locate the occurrences of the two patterns in $T$ that are closest to each other, or report their distance. Kopelowitz and Krauthgamer [CPM2016] showed upper bound tradeoffs and conditional lower bounds tradeoffs for the snippets problem, by utilizing connections between the snippets problem and the problem of constructing a color distance oracle (CDO), which is a data structure that preprocess a set of points with associated colors so that given two colors $c$ and $c'$ one can quickly find the (distance between the) closest pair of points with colors $c$ and $c'$. However, the existing upper bound and lower bound curves are not tight. Inspired by recent advances by Kopelowitz and Vassilevska-Williams [ICALP2020] regarding Set-disjointness data structures, we introduce new conditionally optimal algorithms for $(1+\varepsilon)$ approximation versions of the snippets problem and the CDO problem, by applying fast matrix multiplication. For example, for CDO on $n$ points in an array with preprocessing time $\tilde{O}(n^a)$ and query time $\tilde{O}(n^b)$, assuming that $\omega=2$ (where $\omega$ is the exponent of $n$ in the runtime of the fastest matrix multiplication algorithm on two squared matrices of size $n\times n$), we show that approximate CDO can be solved with the following tradeoff $$ a + 2b = 2 \text{ if } 0 \leq b \leq \frac1 3$$ $$ 2a + b = 3 \text{ if } \frac13\leq b \leq 1.$$ Moreover, we prove that for exact CDO on points in an array, the algorithm of Kopelowitz and Krauthgamer [CPM2016], is essentially optimal assuming that the strong APSP hypothesis holds for randomized algorithms. Thus, the exact version of CDO is strictly harder than the approximate version.

Authors: Nick Arnosti, Felipe Simon

We study a foundational model of dynamic matching market with abandonment. This model has been studied by Collina et al (2020) and Aouad and Saritac (2022), and many other papers have considered special cases. We compare the performance of greedy policies -- which identify a set of "acceptable" matches up front, and perform these matches as soon as possible -- to that of an omniscient benchmark which knows the full arrival and departure sequence. We use a novel family of linear programs ($LP^{ALG}$) to identify which greedy policy to follow. We show that the value of $LP^ALG$ is a *lower bound* on the value of the greedy policy that it identifies in two settings of interest: -When all types have the same departure rate. -The bipartite case where types on the same side of the market have the same departure rate. The proofs of these results use a new result (Lemma 1), which relates the *probability* that at least one agent from a set of types is present in the system to the expected number of such agents. We also show that the value of $LP^{ALG}$ is at least 1/2 of the reward rate earned by the omniscient policy (Proposition 4). Therefore, for both settings above, our greedy policy provably earns at least half of the omniscient reward rate. This improves upon the bound of 1/8 from Collina (2020). In both settings our competitive ratio of 1/2 is the best possible: no online policy can provide a better guarantee (Theorem 2). To show these results we introduce a new linear program that upper bounds the objective value of the omniscient policy (Proposition 3). This improves upon the upper bounds presented by Collina et al (2020) and Kessel et al (2022).

Authors: David Eppstein

We show that the max-min-angle polygon in a planar point set can be found in time $O(n\log n)$ and a max-min-solid-angle convex polyhedron in a three-dimensional point set can be found in time $O(n^2)$. We also study the maxmin-angle polygonal curve in 3d, which we show to be $\mathsf{NP}$-hard to find if repetitions are forbidden but can be found in near-cubic time if repeated vertices or line segments are allowed, by reducing the problem to finding a bottleneck cycle in a graph. We formalize a class of problems on which a decremental greedy algorithm can be guaranteed to find an optimal solution, generalizing our max-min-angle and bottleneck cycle algorithms, together with a known algorithm for graph degeneracy.

Authors: Rolf van Lieshout, Bart van Rossum

We study the periodic assignment problem, in which a set of periodically repeating tasks must be assigned to workers within a repeating schedule. The classical efficiency objective is to minimize the number of workers required to operate the schedule. We propose a O(n log n) algorithm to solve this problem. Next, we formalize a notion of fairness among workers, and impose that each worker performs the same work over time. We analyze the resulting trade-off between efficiency and fairness, showing that the price of fairness is at most one extra worker, and that such a fair solution can always be found using the Nearest Neighbor heuristic. We characterize all instances that admit a solution that is both fair and efficient, and use this result to develop a O(n log n) exact algorithm for the fair periodic assignment problem. Finally, we show that allowing aperiodic schedules never reduces the price of fairness.

Authors: Patryk Jędrzejczak, Łukasz Kowalik

In 1965, Vizing [Diskret. Analiz, 1965] showed that every planar graph of maximum degree $\Delta\ge 8$ can be edge-colored using $\Delta$ colors. The direct implementation of the Vizing's proof gives an algorithm that finds the coloring in $O(n^2)$ time for an $n$-vertex input graph. Chrobak and Nishizeki [J. Algorithms, 1990] have shown a more careful algorithm, which improves the time to $O(n\log n)$ time, though only for $\Delta\ge 9$. In this paper, we extend their ideas to get an algorithm also for the missing case $\Delta=8$. To this end, we modify the original recoloring procedure of Vizing. This generalizes to bounded genus graphs.

Authors: John Peca-Medlin, Chenyang Zhong

Binary search trees (BSTs) are fundamental data structures whose performance is largely governed by tree height. We introduce a block model for constructing BSTs by embedding internal BSTs into the nodes of an external BST -- a structure motivated by parallel data architectures -- corresponding to composite permutations formed via Kronecker or wreath products. Extending Devroye's result that the height $h_n$ of a random BST satisfies $h_n / \log n \to c^* \approx 4.311$, we show that block BSTs with $nm$ nodes and fixed external size $m$ satisfy $h_{n,m} / \log n \to c^* + h_m$ in distribution. We then analyze height growth under iterated products. For simple butterfly trees (from iterated Kronecker products of $S_2$), we give a full distributional description showing polynomial height growth: $\mathbb{E} h_n^{\operatorname{B}} = \Theta(N^\alpha)$ with $\alpha \approx 0.58496$. For nonsimple butterfly trees (from wreath products), we prove power-law bounds: $cN^\alpha\cdot (1 + o(1)) \le \mathbb{E} h_n^{\operatorname{B}} \le dN^\beta\cdot (1 + o(1))$, with $\beta \approx 0.913189$.

Authors: Nikhil Kumar, JJ Nan, Chaitanya Swamy

In the classical \emph{survivable-network-design problem} (SNDP), we are given an undirected graph $G = (V, E)$, non-negative edge costs, and some $(s_i,t_i,r_i)$ tuples, where $s_i,t_i\in V$ and $r_i\in\mathbb{Z}_+$. We seek a minimum-cost subset $H \subseteq E$ such that each $s_i$-$t_i$ pair remains connected even if any $r_i-1$ edges fail. It is well-known that SNDP can be equivalently modeled using a weakly-supermodular \emph{cut-requirement function} $f$, where we seek a minimum-cost edge-set containing at least $f(S)$ edges across every cut $S \subseteq V$. Recently, Dinitz et al. proposed a variant of SNDP that enforces a \emph{relative} level of fault tolerance with respect to $G$, where the goal is to find a solution $H$ that is at least as fault-tolerant as $G$ itself. They formalize this in terms of paths and fault-sets, which gives rise to \emph{path-relative SNDP}. Along these lines, we introduce a new model of relative network design, called \emph{cut-relative SNDP} (CR-SNDP), where the goal is to select a minimum-cost subset of edges that satisfies the given (weakly-supermodular) cut-requirement function to the maximum extent possible, i.e., by picking $\min\{f(S),|\delta_G(S)|\}$ edges across every cut $S\subseteq V$. Unlike SNDP, the cut-relative and path-relative versions of SNDP are not equivalent. The resulting cut-requirement function for CR-SNDP (as also path-relative SNDP) is not weakly supermodular, and extreme-point solutions to the natural LP-relaxation need not correspond to a laminar family of tight cut constraints. Consequently, standard techniques cannot be used directly to design approximation algorithms for this problem. We develop a \emph{novel decomposition technique} to circumvent this difficulty and use it to give a \emph{tight $2$-approximation algorithm for CR-SNDP}. We also show new hardness results for these relative-SNDP problems.

Authors: Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, Gokarna Sharma

The most celebrated and extensively studied model of distributed computing is the {\em message-passing model,} in which each vertex/node of the (distributed network) graph corresponds to a static computational device that communicates with other devices through passing messages. In this paper, we consider the {\em agentic model} of distributed computing which extends the message-passing model in a new direction. In the agentic model, computational devices are modeled as relocatable or mobile computational devices (called agents in this paper), i.e., each vertex/node of the graph serves as a container for the devices, and hence communicating with another device requires relocating to the same node. We study two fundamental graph level tasks, leader election, and minimum spanning tree, in the agentic model, which will enhance our understanding of distributed computation across paradigms. The objective is to minimize both time and memory complexities. Following the literature, we consider the synchronous setting in which each agent performs its operations synchronously with others, and hence the time complexity can be measured in rounds. In this paper, we present two deterministic algorithms for leader election: one for the case of $k

Authors: Yuexin Su, Ziyi Yang, Peiyuan Huang, Tongyang Li, Yinyu Ye

Bandits with knapsacks (BwK) constitute a fundamental model that combines aspects of stochastic integer programming with online learning. Classical algorithms for BwK with a time horizon $T$ achieve a problem-independent regret bound of ${O}(\sqrt{T})$ and a problem-dependent bound of ${O}(\log T)$. In this paper, we initiate the study of the BwK model in the setting of quantum computing, where both reward and resource consumption can be accessed via quantum oracles. We establish both problem-independent and problem-dependent regret bounds for quantum BwK algorithms. For the problem-independent case, we demonstrate that a quantum approach can improve the classical regret bound by a factor of $(1+\sqrt{B/\mathrm{OPT}_\mathrm{LP}})$, where $B$ is budget constraint in BwK and $\mathrm{OPT}_{\mathrm{LP}}$ denotes the optimal value of a linear programming relaxation of the BwK problem. For the problem-dependent setting, we develop a quantum algorithm using an inexact quantum linear programming solver. This algorithm achieves a quadratic improvement in terms of the problem-dependent parameters, as well as a polynomial speedup of time complexity on problem's dimensions compared to classical counterparts. Compared to previous works on quantum algorithms for multi-armed bandits, our study is the first to consider bandit models with resource constraints and hence shed light on operations research.

Authors: Harsh Shah, Purna Chandrasekhar, Rahul Vaze

Online convex optimization with switching cost is considered under the frugal information setting where at time $t$, before action $x_t$ is taken, only a single function evaluation and a single gradient is available at the previously chosen action $x_{t-1}$ for either the current cost function $f_t$ or the most recent cost function $f_{t-1}$. When the switching cost is linear, online algorithms with optimal order-wise competitive ratios are derived for the frugal setting. When the gradient information is noisy, an online algorithm whose competitive ratio grows quadratically with the noise magnitude is derived.

Authors: Mohammad Dindoost, Oliver Alvarado Rodriguez, Bartosz Bryg, Ioannis Koutis, David A. Bader

Subgraph isomorphism, essential for pattern detection in large-scale graphs, faces scalability challenges in attribute-rich property graphs used in neuroscience, systems biology, and social network analysis. Traditional algorithms explore search spaces vertex-by-vertex from empty mappings, leading to extensive early-stage exploration with limited pruning opportunities. We introduce HiPerMotif, a novel hybrid parallel algorithm that fundamentally shifts the search initialization strategy. After structurally reordering the pattern graph to prioritize high-degree vertices, HiPerMotif systematically identifies all possible mappings for the first edge (vertices 0,1) in the target graph, validates these edge candidates using efficient vertex and edge validators, and injects the validated partial mappings as states at depth 2. The algorithm then continues with traditional vertex-by-vertex exploration from these pre-validated starting points, effectively pruning the expensive early search tree branches while enabling natural parallelization over edge candidates. Our contributions include the edge-centric initialization paradigm with state injection, a structural reordering strategy achieving up to 5x speedup, rapid edge and vertex validators for attribute-rich graphs, and efficient parallel enumeration over target graph edges. Implemented in the open-source Arachne framework, HiPerMotif achieves up to 66x speedup over state-of-the-art baselines (VF2-PS, VF3P, Glasgow) on diverse datasets where baselines successfully complete execution. Additionally, HiPerMotif successfully processes massive datasets such as the H01 connectome with 147 million edges, which existing methods cannot handle due to memory constraints. Comprehensive evaluation across synthetic and real-world graphs demonstrates HiPerMotif's scalability, enabling advanced analysis in computational neuroscience and beyond.

Authors: Ekin Ergen

We consider a natural extension of online makespan scheduling on identical parallel machines by introducing scenarios. A scenario is a subset of jobs, and the task of our problem is to find a global assignment of the jobs to machines so that the maximum makespan under a scenario, i.e., the maximum makespan of any schedule restricted to a scenario, is minimized. For varying values of the number of scenarios and machines, we explore the competitiveness of online algorithms. We prove tight and near-tight bounds, several of which are achieved through novel constructions. In particular, we leverage the interplay between the unit processing time case of our problem and the hypergraph coloring problem both ways: We use hypergraph coloring techniques to steer an adversarial family of instances proving lower bounds, which in turn leads to lower bounds for several variants of online hypergraph coloring.

Authors: Xi He, Max. A. Little

We introduce an efficient and elegant combination generator for producing all combinations of size less than or equal to K, designed for exhaustive generation and combinatorial optimization tasks. This generator can be implemented to achieve what we define as optimal efficiency: constant amortized time, optimal cache utilization, embarrassingly parallel execution, and a recursive structure compatible with pruning-based search. These properties are difficult to satisfy simultaneously in existing generators. For example, classical Gray code or lexicographic generators are typically list-based and sequentially defined, making them difficult to vectorized, inefficient in cache usage, and inherently hard to parallelize. Generators based on unranking methods, while easy to parallelize, are non-recursive. These limitations reduce their applicability in our target applications, where both computational efficiency and recursion are crucial. We adapt Bird's algebra of programming-style calculation to derive our algorithms, a formalism for developing correct-by-construction programs from specifications. As a result, all generators in this paper are first formulated in their clearest specification, and efficient definitions are derived constructively through equational reasoning, resulting in concise and elegant divide-and-conquer definitions. Beyond presenting a combination generator, we extend our approach to construct generators for K-permutations, nested combinations of combinations, and nested permutation-combination structures. To the best of our knowledge, the literature has not previously reported generators for these nested structures. We also develop sequential variants that produce configurations in Gray code-compatible orders -- such as the revolving door ordering -- which are particularly useful for constructing nested generators.

Authors: Sophie Boileau, Andrew Hong, David Liben-Nowell, Alistair Pattison, Anna N. Rafferty, Charlie Roslansky

In many covering settings, it is natural to consider the simultaneous presence of desirable elements (that we seek to include) and undesirable elements (that we seek to avoid). This paper introduces a novel combinatorial problem formalizing this tradeoff: from a collection of sets containing both "desirable" and "undesirable" items, pick the subcollection that maximizes the margin between the number of desirable and undesirable elements covered. We call this the Target Approximation Problem (TAP) and argue that many real-world scenarios are naturally modeled via this objective. We first show that TAP is hard, even when restricted to cases where the given sets are small or where elements appear in only a small number of sets. In a large subset of these cases, we show that TAP is hard to even approximate. We then exhibit exact polynomial-time algorithms for other restricted cases and provide an efficient 0.5-approximation for the case where elements occur at most twice, derived through a tight connection to the greedy algorithm for Unweighted Set Cover.

Authors: Jadwiga Czyżewska, Marcin Pilipczuk

For a directed graph $G$, let $\mathrm{mindeg}(G)$ be the minimum among in-degrees and out-degrees of all vertices of $G$. It is easy to see that $G$ contains a directed cycle of length at least $\mathrm{mindeg}(G)+1$. In this note, we show that, even if $G$ is $2$-connected, it is NP-hard to check if $G$ contains a cycle of length at least $\mathrm{mindeg}(G)+3$. This is in contrast with recent algorithmic results of Fomin, Golovach, Sagunov, and Simonov [SODA 2022] for analogous questions in undirected graphs.

Authors: Zeev Nutov, Reut Cohen

In the $k$-Edge Connected Spanning Subgraph ($k$-ECSS) problem we are given a (multi-)graph $G=(V,E)$ with edge costs and an integer $k$, and seek a min-cost $k$-edge-connected spanning subgraph of $G$. The problem admits a $2$-approximation algorithm and no better approximation ratio is known. Recently, Hershkowitz, Klein, and Zenklusen [STOC 24] gave a bicriteria $(1,k-10)$-approximation algorithm that computes a $(k-10)$-edge-connected spanning subgraph of cost at most the optimal value of a standard Cut-LP for $k$-ECSS. We improve the bicriteria approximation to $(1,k-4)$, and also give another non-trivial bicriteria approximation $(3/2,k-2)$. The $k$-Edge-Connected Spanning Multi-subgraph ($k$-ECSM) problem is almost the same as $k$-ECSS, except that any edge can be selected multiple times at the same cost. A $(1,k-p)$ bicriteria approximation for $k$-ECSS w.r.t. Cut-LP implies approximation ratio $1+p/k$ for $k$-ECSM, hence our result also improves the approximation ratio for $k$-ECSM.

Authors: Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, Meirav Zehavi

We present an algorithm for a class of $n$-fold ILPs: whose existing algorithms in literature typically (1) are based on the \textit{augmentation framework} where one starts with an arbitrary solution and then iteratively moves towards an optimal solution by solving appropriate programs; and (2) require solving a linear relaxation of the program. Combinatorial $n$-fold ILPs is a class introduced and studied by Knop et al. [MP2020] that captures several other problems in a variety of domains. We present a simple and direct algorithm that solves Combinatorial $n$-fold ILPs with unbounded non-negative variables via an application of the Steinitz lemma, a classic result regarding reordering of vectors. Depending on the structure of the input, we also improve upon the existing algorithms in literature in terms of the running time, thereby showing an improvement that mirrors the one shown by Rohwedder [ICALP2025] contemporaneously and independently.

Beginning computer science students learn about stacks, queues, and priority queues, different ways of organizing and ordering a collection of tasks to be performed. But more basic than any of those, and less frequently taught and formalized, is the ready list, a collection of tasks to be performed whose ordering is not important. All it needs to do is to allow new tasks to be added to the collection and to find and remove an arbitrary task from the collection.

Standard algorithms that work with ready lists include:

Reachability

Input: a directed or undirected graph and a starting vertex in the graph

Output: the set of vertices that can be reached from the starting vertex

Algorithm:

• Initialize a set of reachable vertices, and a ready list of reachable but unprocessed vertices, both initially containing only the starting vertex.
• While the ready list is non-empty:
  • Find and remove a vertex \(v\) from the ready list
  • For each outgoing neighbor \(w\) of \(v\) that is not already in the reachable set, add \(w\) to both the reachable set and the ready list.
• Return the reachable set

Topological ordering

Input: a directed acyclic graph

Output: a sequence of vertices, ordered so all edges go from earlier to later in the ordering

Algorithm:

• Initialize a ready list of vertices with no incoming edges
• While the ready list is non-empty:
  • Find and remove a vertex \(v\) from the ready list
  • Delete \(v\) from the graph and output \(v\)
  • Add to the ready list any former neighbor of \(v\) which, after the deletion, has no more incoming edges

Stable matching

Input: A set of job applicants and a set of employers, with each applicant having a preference ordering among the employers and each employer having a preference ordering among the applicants

Output: A stable matching

Algorithm:

• Initialize a ready list of job offers from each employer to its top applicant
• While the ready list is non-empty:
  • Find and remove an offer from employer \(X\) to applicant \(A\)
  • If \(A\) prefers their current situation over \(X\), add to the ready list a new job offer from \(X\) to \(X\)’s next applicant.
  • Otherwise, match \(A\) and \(X\); if \(A\) was previously matched, remove that match and add to the ready list a new job offer from \(A\)’s previous employer to its next applicant

In the cases of reachability and stable matching, the ordering chosen by the ready list is unimportant: you will always get the same reachable set and the same matching. In the case of topological ordering, you may get different orderings but regardless of order you will always output the same set of vertices for any given graph, even if the graph is not acyclic.

This invariance is usually proven algorithm-by-algorithm, but it is true very generally for a class of algorithms with three simple properties: First, an item that is added to the ready list stays there until it is processed. Second, each item is added to the ready list only once. And third, the condition for adding an item to the ready list should be a monotonic combination of which other items have already been processed: if a certain combination of processed items triggers an addition, then any superset of the same combination should trigger the same addition. The trigger for reachability is that some neighbor is processed, and the trigger for topological ordering is that all incoming neighbors are processed. For stable matching, the trigger for an offer from \(X\) to \(A\) is that \(X\)’s previous applicant has already received both an offer from \(X\) and an offer from another employer that they prefer over \(X\).

These three properties are enough to prove that the sequences in which items can be processed by an algorithm of this type form an antimatroid. The key axiom of antimatroid sequences that we need to prove is that, if two sequences \(S\) and \(T\) can both be generated, and \(S\) contains an item not in \(T\), then \(S\) contains an item \(x\) that can be processed next after \(T\), producing a sequence \(Tx\). To prove this, simply let \(x\) be the first item that belongs to \(S\) but not \(T\), and apply the monotonic trigger property.

In any antimatroid, all sequences that cannot be extended consist of the same set of items. Again, this is easy to prove: if two sequences had different sets of items, then one would contain an item by which the other could be extended. To translate this into terms more familiar to the beginning computer science students: if a ready list obeys the three properties given above, and we run an algorithm using it until the ready list becomes empty, then all runs of the algorithm process the same set of items.

While exploring this I ran into another basic algorithm that in its usual form is based on integer priority queues but can be transformed into a ready list algorithm:

Degeneracy

Input: An undirected graph

Output: A subgraph whose minimum degree is as large as possible

Algorithm:

• Initialize an empty ready list
• While the graph is non-empty:
  • If the ready list is empty, set \(d\) to the minimum degree in the graph, set \(S\) to be an empty set, and add to the ready list all vertices of degree \(d\)
  • Find and remove a vertex \(v\) from the ready list
  • Delete \(v\) from the graph and add \(v\) to \(S\)
  • Add to the ready list any former neighbors of \(v\) for which this removal decreases the degree to \(\le d\)
• Output the subgraph induced in the original input graph by \(S\)

This can be made to run in linear time but the details of that are beyond the scope of this post. Proving monotonicity of the condition for triggering addition to the ready list is a little less obvious here. For each integer \(k\) we can define a subgraph called the \(k\)-core, the union of all subgraphs whose minimum degree is at least \(k\). The output is the \(d\)-core. The monotonic trigger for any vertex \(v\) to be added to the ready list is that all vertices not in the \(k\)-core have already been processed, where \(k\) is the largest value for which the \(k\)-core contains \(v\), and that \(v\) has at most \(k\) unprocessed neighbors.

Abstractly, the decreasing degrees of the vertices can be seen as a kind of element quality that decreases as other elements are removed; we seek the subset maximizing the minimum quality of any of its elements. My latest preprint, “Decremental greedy polygons and polyhedra without sharp angles” (arXiv:2507.04538, to appear at this year’s Canadian Conference on Computational Geometry) looks at a general class of problems like this, and identifies several more. One of the simplest of these is to find a polygon through a subset of the points that maximizes the minimum interior angle.

So here is the algorithm; I think the similarities between this and the degeneracy algorithms are obvious.

Max-min angle polygon

Input: A set of points in \(\mathbb{R}^2\)

Output: A polygon with the points as vertices whose sharpest angle is as large as possible

Algorithm:

• Initialize an empty ready list
• While the set of points is non-empty:
  • If the ready list is empty, set \(\theta\) to the minimum angle of a convex hull vertex of the remaining points, set \(S\) to be an empty set, and add to the ready list all convex hull vertices of angle \(\theta\)
  • Find and remove a point \(p\) from the ready list
  • Delete \(p\) from the points and add \(p\) to \(S\)
  • Add to the ready list any convex hull vertices for which this removal decreases the angle to \(\le\theta\)
• Output the convex hull of \(S\)

This can be made to run in time \(O(n\log n)\); for details see the preprint. I’ll finish with one more from the full version of the paper, on cycles in directed graphs.

Bottleneck cycle

Input: A directed graph with weighted edges

Output: A cycle whose minimum edge weight is as large as possible

Algorithm:

• Initialize a ready list of the edges out of all vertices that have no incoming edges, and the edges into all vertices that have no outgoing edges
• Initialize an empty set \(S\)
• While the set of graph edges is non-empty:
  • If the ready list is empty, set \(w\) to the minimum weight of a remaining edge, set \(S\) to be an empty set, and add to the ready list all edges of weight \(w\)
  • Find and remove an edge \((u,v)\) from the ready list
  • Delete edge \((u,v)\) from the graph and add it to \(S\)
  • If \(u\) has no more outgoing edges, add to the ready list all its incoming edges.
  • If \(v\) has no more incoming edges, add to the ready list all its outgoing edges.
• Find and output any cycle in the subgraph of edges in \(S\)

For this one, a direct implementation on a graph with \(n\) vertices and \(m\) edges would take time \(O(m\log n)\), not really better than the obvious binary search. However, it can be made to run in linear time for graphs with edges already sorted by length, and this presorted version can be used as a subroutine in a different algorithm for graphs with unsorted edges, in time \(O(m\log^* n)\). In turn, bottleneck cycles can be used as a subroutine in an algorithm for finding the max-min angle closed polygonal curve for 3d points, allowing the curve to pass repeatedly through points and segments, in time \(O(n^3\log^* n)\). For details see the preprint.

By David Eppstein

A friend sent me a fun article in FT Alphaville by Bryce Elder showing how dogma doesn’t need to make sense to make money. The article hooked me from the get-go:

“The Virtue of Complexity in Return Prediction — co-authored by Bryan Kelly with Semyon Malamud and Kangying Zhou — found that complex machine-learning models were better than simple ones at predicting stock prices and building portfolios.”

“The finding was a big deal because it contradicted one of machine learning’s guiding principles, the bias-variance trade-off, which says the predictive power of models weakens as they grow beyond some optimum level. Given too many parameters to play with, a bot will tend to overfit its output to random noise in the training data.”

Oh, I’ve written about this before, arguing we should remove the bias-variance tradeoff from the machine learning curriculum. Much love to everyone who references the ye olde argmin blog in the comments over on Alphville. I appreciate the shoutouts! However, many of my friends in finance have told me that their data was where statistical overfitting, the type of overfitting we teach in our undergraduate classes, was a real phenomenon. Here is a paper that apparently refutes their claims. According to Kelly et al., even in finance, the bias-variance tradeoff isn’t real. Elder continues:

“The finding was rooted in an AI concept known as double descent, which says deep learning algorithms make fewer mistakes when they have more variable parameters than training data points.”

Double descent, you say? Hmm. At this point in the article, I got a bit worried because that’s… not what double descent says. Well, now I had to go and download the paper from SSRN. It checks in at a crisp 141 pages.

Once you skip past the laborious theoretical analysis of a linear Gaussian model, you get to the experiments on page 41. The authors want to predict next month's prices from a set of 15 indicators. They use a window of past pairs of indicators and prices from the last 12 months to make this prediction. They propose applying standard supervised learning to solve this problem. Translating their setup into machine learning language: their training dataset has 12 examples, each with 15 features. Yes, 12.

What do they conclude? They find that if they use random Fourier features, then the training error continues to decrease as they add more and more features. In particular, using 12,000 random Fourier features still gives good performance.

Oh my. I know it’s been twenty years since Ali and I first wrote up our paper on random features, and our point seems to have been lost in time.1 The motivation was finding computationally efficient ways to approximate machine learning in kernel spaces. I realize no one learns about kernel methods anymore, but you can read about them in Chapter 4 of Patterns, Predictions, and Actions. For the purpose of this post: kernel methods give you a computationally efficient way to compute a prediction model that uses an infinite number of features. Through some fun linear algebra, it turns out you only need to solve a linear system with one variable for every training example. Kernel methods transform infinite-dimensional learning problems into finite-dimensional linear algebra problems.

Still, kernel methods require more computation than standard linear regression methods (and deep learning methods for that matter). The time needed to solve a linear system scales with the cube of the number of data points. The time required to solve linear regression scales linearly with the number of data points. Ali and I initially stumbled upon random features as a way to approximate kernel methods by solving linear regression problems.

But you know folks, kernel methods aren’t that computationally expensive. Cubic time is still polynomial time. And high-dimensional linear regression has its own scaling issues. The solution time of a random Fourier features problem scales with the square of the number of features.2 Since random features approximate kernel methods, the prediction performance of kernel methods should always be as good or better.3

To reiterate, kernel ridge regression solves an infinite-dimensional regression problem. It is going to get you the solution promised by the asymptote of that double descent curve you are all so enamored with. Infinity is more than 12,000, and moar is always better, right? If you find yourself using 1000 times more random features than data points, you might want to consider reading a few tutorials on kernel regression. It’s not hard to implement! In Python on my laptop, I can solve a 12 example kernel ridge regression problem in microseconds.

The argmin blog is here to help you save money on GPU cloud credits.

Now you might ask, would “ridgeless kernel regression,” that is, kernel regression that ignores the warnings of the bias-variance tradeoff, work well for time series analysis? This is a good question, and one asked by Emmanuel Parzen in his landmark 1961 paper, “An Approach to Time Series Analysis.”4 Parzen’s paper is one of the first to explicitly use reproducing kernels in prediction problems. In Section 6, he proposes using ridgeless kernel regression to solve the exact same problem studied by Kelly and coauthors.

I’m not the first person to recognize this, as Elder notes in Alphaville. Stefan Nagel wrote a convincing rebuttal to Kelly et al., posted last week. Nagel notes that random Fourier features are approximating kernel regression. He also notes that the prediction function computed by kernel regression looks a lot like kernel smoothing. This means the data points that most influence the prediction will be the ones most recent in time. Nagel thus argues that Kelly et al. are making a bunch of appeals to deep learning hype to reinvent momentum investing.

And about that bias-variance tradeoff? If you slog through Kelly et al, you’ll see that their theoretical analysis has a bias-variance tradeoff! And the optimum setting requires tuning the tradeoff!

“We show that machine learning portfolios tend to incrementally benefit from moving away from the ridgeless limit by introducing nontrivial shrinkage.”

Sigh.

I realize that everyone has jumped on the deep learning train now, but cargo culting isn’t in your interest. For small problems (like training sets of size 12), you don’t need neural networks. You can use them, I guess. But you can get more understanding out of these small, infinite-dimensional models that people have been studying for seventy years.

Sadly, the hype cycle gets everyone confused. It’s hilarious that stylized statistical learning theory stories now find their way into the mainstream press. The Alphaville title is even confused here: “Are bigger AI models better stock pickers? Maybe, but probably not. Complexity ain’t all that, wonks say.” I mean, this contradicts the rest of the story. First, calling ordinary least squares “AI” is a bit of a stretch. Second, Nagel’s results show that in this restricted class of models, bigger models are indeed better. Moreover, those infinitely large models recover well-known, naive momentum strategies.

Kelly and his fund, AQR, weren’t happy about Elder’s article. They wrote a rebuttal, proclaiming:

“The empirical dominance of large models has been shown in every area of ML by heavyweight ML academics’ research, which has been conducted throughout the natural and applied sciences. Language and image modeling are most well-known applications that exemplify the success of large models. Do we really think that finance, economics, or other social sciences are special? The work of Kelly and team shows otherwise.”

This heavyweight ML academic offers a very reasonable consulting fee if you are at a hedge fund and need assistance understanding double descent and the no true Scotsman fallacy.

Subscribe now

By Ben Recht

Let me briefly report on two birthday conferences for long-time friends and colleagues Saharon Shelah and Yuri Gurevich. Yuri fest took place in Munich and on Zoom between June 20–22 2025 and Shelah’s birthday conference will be held in Vienna on July 14–15, 2025.

For my general thoughts on celebrating colleagues’ birthdays in these tragic and dangerous times, see this post.

Saharon Shelah is among the greatest and most decorated mathematicians of our time with groundbreaking contributions in model theory, set theory, combinatorics, and other areas. Among his most famous achievements are  the development of classification theory in model theory, his arithmetic cardinal theory (see this post), his proof that Whitehead’s conjecture is independent from ZFC, and his effective bounds for Van der Waerden numbers in combinatorics.

Yuri Gurevich is a renowned mathematical logician who transitioned to theoretical and practical computer science, software engineering, and later, quantum computing. One of the most natural average-case complete problems was introduced in a paper by Andreas Blass and Yuri Gurevich. (Andreas and Yuri have been long-time collaborators and friends.) Saharon and Yuri also coauthored a few important papers, including one on monadic second-order theories.

I’ve known both Saharon and Yuri since the late 1970s. Over the years, I would occasionally visit Saharon’s office (and now that I think about it, I should have taken a picture of it) to discuss interesting problems. These conversations contributed to Saharon’s generalization of Arrow’s theorem and to his work with Micha Perles on “n-convexity.” Once, Saharon asked me to comment on an introduction for the general mathematical audience to his second book on classification theory. In 1994, Saharon and I shared the Pólya Prize in Combinatorics. My daughter was a classmate of Saharon’s son, so we also met occasionally at school events.

My friendship with Yuri began at Microsoft in the late 1990s. As a complete layman, I was fascinated by his approach to software engineering, which had a major impact on Microsoft. Yuri, in turn, was interested in my views on quantum computing—well before he became an active researcher in the field in 2013—and we discussed the topic frequently over the years. We also shared an interest in detecting deception using mathematical tools (see this post by Omer Reingold on his approach). 

Heartfelt congratulations to Saharon and Yuri!

Ronald de Wolf’s lecture on quantum proofs to classical theorems. 

At YuriFest, Ronald de Wolf gave a great lecture on quantum proofs for classical theorems (the audio is a bit weak—turn the volume to 100%). One of his examples is discussed in this post. Yuri himself gave a wonderful talk titled The nature of nondeterministic probabilistic, quantum, etc. algorithms.

Reminder: Joram’s seminar on hypercontractivity and groups, Wednesday and Thursday, July 9 and 10, 2025.

By Gil Kalai

Authors: David Miloschewsky, Supartha Podder

In 2004, Aaronson introduced the complexity class $\mathsf{PostBQP}$ ($\mathsf{BQP}$ with postselection) and showed that it is equal to $\mathsf{PP}$. In this paper, we define a new complexity class, $\mathsf{CorrBQP}$, a modification of $\mathsf{BQP}$ which has the power to perform correlated measurements, i.e. measurements that output the same value across a partition of registers. We show that $\mathsf{CorrBQP}$ is exactly equal to $\mathsf{BPP}^{\mathsf{PP}}$, placing it "just above" $\mathsf{PP}$. In fact, we show that other metaphysical modifications of $\mathsf{BQP}$, such as $\mathsf{CBQP}$ (i.e. $\mathsf{BQP}$ with the ability to clone arbitrary quantum states), are also equal to $\mathsf{BPP}^{\mathsf{PP}}$. Furthermore, we show that $\mathsf{CorrBQP}$ is self-low with respect to classical queries. In contrast, if it were self-low under quantum queries, the counting hierarchy ($\mathsf{CH}$) would collapse to $\mathsf{BPP}^{\mathsf{PP}}$. Finally, we introduce a variant of rational degree that lower-bounds the query complexity of $\mathsf{BPP}^{\mathsf{PP}}$.

Authors: Rocco Ascone, Giulia Bernardini, Alessio Conte, Veronica Guerrini, Giulia Punzi

We study the basic regular expression intersection testing problem, which asks to determine whether the intersection of the languages of two regular expressions is nonempty. A textbook solution to this problem is to construct the nondeterministic finite automaton that accepts the language of both expressions. This procedure results in a $\Theta(mn)$ running time, where $m$ and $n$ are the sizes of the two expressions, respectively. Following the approach of Backurs and Indyk [FOCS'16] and Bringmann, Gr{\o}nlund, and Larsen [FOCS'17] on regular expression matching and membership testing, we study the complexity of intersection testing for homogeneous regular expressions of bounded depth involving concatenation, OR, Kleene star, and Kleene plus. Specifically, we consider all combinations of types of depth-2 regular expressions and classify the time complexity of intersection testing as either linear or quadratic, assuming SETH. The most interesting result is a quadratic conditional lower bound for testing the intersection of a ''concatenation of +s'' expression with a ''concatenation of ORs'' expression: this is the only hard case that does not involve the Kleene star operator and is not implied by existing lower bounds for the simpler membership testing problem.

Authors: Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan

The celebrated Ore-DeMillo-Lipton-Schwartz-Zippel (ODLSZ) lemma asserts that n-variate non-zero polynomial functions of degree d over a field $\mathbb{F}$ are non-zero over any "grid" $S^n$ for finite subset $S \subseteq \mathbb{F}$, with probability at least $\max\{|S|^{-d/(|S|-1)},1-d/|S|\}$ over the choice of random point from the grid. In particular, over the Boolean cube ($S = \{0,1\} \subseteq \mathbb{F}$), the lemma asserts non-zero polynomials are non-zero with probability at least $2^{-d}$. In this work we extend the ODLSZ lemma optimally (up to lower-order terms) to "Boolean slices" i.e., points of Hamming weight exactly $k$. We show that non-zero polynomials on the slice are non-zero with probability $(t/n)^{d}(1 - o_{n}(1))$ where $t = \min\{k,n-k\}$ for every $d\leq k\leq (n-d)$. As with the ODLSZ lemma, our results extend to polynomials over Abelian groups. This bound is tight (upto the error term) as evidenced by degree d multilinear monomials. A particularly interesting case is the "balanced slice" ($k=n/2$) where our lemma asserts that non-zero polynomials are non-zero with roughly the same probability on the slice as on the whole cube. The behaviour of low-degree polynomials over Boolean slices has received much attention in recent years. However, the problem of proving a tight version of the ODLSZ lemma does not seem to have been considered before, except for a recent work of Amireddy, Behera, Paraashar, Srinivasan and Sudan (SODA 2025) who established a sub-optimal bound of approximately $((k/n)\cdot(1-(k/n)))^d$ using a proof similar to that of the standard ODLSZ lemma. While the statement of our result mimics that of the ODLSZ lemma, our proof is significantly more intricate and involves spectral reasoning which is employed to show that a natural way of embedding a copy of the Boolean cube inside a balanced Boolean slice is a good sampler.

Authors: Nikhil S. Mande, Swagato Sanyal, Viktor Zamaraev

The problem of learning or reconstructing an unknown graph from a known family via partial-information queries arises as a mathematical model in various contexts. The most basic type of access to the graph is via \emph{edge queries}, where an algorithm may query the presence/absence of an edge between a pair of vertices of its choosing, at unit cost. While more powerful query models have been extensively studied in the context of graph reconstruction, the basic model of edge queries seems to have not attracted as much attention. In this paper we study the edge query complexity of learning a hidden bipartite graph, or equivalently its bipartite adjacency matrix, in the classical as well as quantum settings. We focus on learning matchings and half graphs, which are graphs whose bipartite adjacency matrices are a row/column permutation of the identity matrix and the lower triangular matrix with all entries on and below the principal diagonal being 1, respectively. \begin{itemize} \item For matchings of size $n$, we show a tight deterministic bound of $n(n-1)/2$ and an asymptotically tight randomized bound of $\Theta(n^2)$. A quantum bound of $\Theta(n^{1.5})$ was shown in a recent work of van Apeldoorn et al.~[ICALP'21]. \item For half graphs whose bipartite adjacency matrix is a column-permutation of the $n \times n$ lower triangular matrix, we give tight $\Theta(n \log n)$ bounds in both deterministic and randomized settings, and an $\Omega(n)$ quantum lower bound. \item For general half graphs, we observe that the problem is equivalent to a natural generalization of the famous nuts-and-bolts problem, leading to a tight $\Theta(n \log n)$ randomized bound. We also present a simple quicksort-style method that instantiates to a $O(n \log^2 n)$ randomized algorithm and a tight $O(n \log n)$ quantum algorithm. \end{itemize}

Authors: Umang Bhaskar, Katharina Eickhoff, Lennart Kauther, Jannik Matuschke, Britta Peis, Laura Vargas Koch

In train routing, the headway is the minimum distance that must be maintained between successive trains for safety and robustness. We introduce a model for train routing that requires a fixed headway to be maintained between trains, and study the problem of minimizing the makespan, i.e., the arrival time of the last train, in a single-source single-sink network. For this problem, we first show that there exists an optimal solution where trains move in convoys, that is, the optimal paths for any two trains are either the same or are arc-disjoint. Via this insight, we are able to reduce the approximability of our train routing problem to that of the min-max disjoint paths problem, which asks for a collection of disjoint paths where the maximum length of any path in the collection is as small as possible. While min-max disjoint paths inherits a strong inapproximability result on directed acyclic graphs from the multi-level bottleneck assignment problem, we show that a natural greedy composition approach yields a logarithmic approximation in the number of disjoint paths for series-parallel graphs. We also present an alternative analysis of this approach that yields a guarantee depending on how often the decomposition tree of the series-parallel graph alternates between series and parallel compositions on any root-leaf path.

Authors: Pieter Kleer, Daan Noordenbos

We consider an optimal stopping problem with n correlated offers where the goal is to design a (randomized) stopping strategy that maximizes the expected value of the offer in the sequence at which we stop. Instead of assuming to know the complete correlation structure, which is unrealistic in practice, we only assume to have knowledge of the distribution of the maximum value of the sequence, and want to analyze the worst-case correlation structure whose maximum follows this distribution. This can be seen as a trade-off between the setting in which no distributional information is known, and the Bayesian setting in which the (possibly correlated) distributions of all the individual offers are known. As our first main result we show that a deterministic threshold strategy using the monopoly price of the distribution of the maximum value is asymptotically optimal assuming that the expectation of the maximum value grows sublinearly in n. In our second main result, we further tighten this bound by deriving a tight quadratic convergence guarantee for sufficiently smooth distributions of the maximum value. Our results also give rise to a more fine-grained picture regarding prophet inequalities with correlated values, for which distribution-free bounds often only yield a performance guarantee that is of the order 1/n.

Authors: Michał Włodarczyk

Calculating the diameter of an undirected graph requires quadratic running time under the Strong Exponential Time Hypothesis and this barrier works even against any approximation better than 3/2. For planar graphs with positive edge weights, there are known $(1+\varepsilon)$-approximation algorithms with running time $poly(1/\epsilon, \log n) \cdot n$. However, these algorithms rely on shortest path separators and this technique falls short to yield efficient algorithms beyond graphs of bounded genus. In this work we depart from embedding-based arguments and obtain diameter approximations relying on VC set systems and the local treewidth property. We present two orthogonal extensions of the planar case by giving $(1+\varepsilon)$-approximation algorithms with the following running times: 1. $O_h((1/\varepsilon)^{O(h)} \cdot n \log^2 n)$-time algorithm for graphs excluding an apex graph of size h as a minor, 2. $O_d((1/\varepsilon)^{O(d)} \cdot n \log^2 n)$-time algorithm for the class of d-apex graphs. As a stepping stone, we obtain efficient (1+\varepsilon)-approximate distance oracles for graphs excluding an apex graph of size h as a minor. Our oracle has preprocessing time $O_h((1/\varepsilon)^8\cdot n \log n \log W)$ and query time $O((1/\varepsilon)^2 * \log n \log W)$, where $W$ is the metric stretch. Such oracles have been so far only known for bounded genus graphs. All our algorithms are deterministic.

Authors: Theo Bourdais, Abeynaya Gnanasekaran, Houman Owhadi, Tuhin Sahai

Algorithms are the engine for reproducible problem-solving. We present a framework automating algorithm discovery by conceptualizing them as sequences of operations, represented as tokens. These computational tokens are chained using a grammar, enabling the formation of increasingly sophisticated procedures. Our ensemble Monte Carlo tree search (MCTS) guided by reinforcement learning (RL) explores token chaining and drives the creation of new tokens. This methodology rediscovers, improves, and generates new algorithms that substantially outperform existing methods for strongly NP-hard combinatorial optimization problems and foundational quantum computing approaches such as Grover's and Quantum Approximate Optimization Algorithm. Operating at the computational rather than code-generation level, our framework produces algorithms that can be tailored specifically to problem instances, not merely classes.

Authors: Ferenc Bencs, Guus Regts

In this paper we take inspiration from Weit'z algorithm for approximating the independence polynomial to provide a new algorithm for computing the coefficients of the Taylor series of the logarithm of the independence polynomial. Hereby we provide a clear connections between Barvinok's interpolation method and Weitz's algorithm. Our algorithm easily extends to other graph polynomials and partition functions and we illustrate this by applying it to the chromatic polynomial and to the graph homomorphism partition function. Our approach arguably yields a simpler and more transparent algorithm than the algorithm of Patel and the second author. As an application of our algorithmic approach we moreover derive, using the interpolation method, a deterministic $O(n(m/\varepsilon)^{7})$-time algorithm that on input of an $n$-vertex and $m$-edge graph of minimum degree at least $3$ and $\varepsilon>0$ approximately computes the number of sink-free orientations of $G$ up to a multiplicative $\exp(\varepsilon)$ factor.

 We denote the busy beaver function by BB.

BB(n) is the max time a Turing machine of size n takes to halt on the empty string.

(A particular model of TM and a notion of size has become standardized.)

BB(n) grows faster than any computable function. That is obviously interesting. What is less obvious (and  some of my co-bloggers disagree) the pursuit of actual values of BB is interesting. For an excellent overview of the BB numbers, written in 2020 (that is relevant) by Scott Aaronson, see here. (Computable and Aaronson are flagged by my spell check but I think they are spelled correctly.) 

When Scott's article appeared, BB(5) was not known. In June 2024 the value of BB(5) was discovered.  See Scott's blog on this, here. The value of BB(5) isn't even that big- its just 47,176,870. That's one of those numbers that is SMALL now but would have been LARGE in (say) 1964 (see my blog about a different number of that type here). 

What about BB(6)?

No, I am not going to announce that Scott announced it is now known. 

I am going to announced that Scott announced better lower bounds for BB(6) are now known. 

I won't restate the lower bounds since (a) Scott already has (see here) and (b) typesetting the bounds is hard (for me). 

SO, what to make of all this?

1) At the time of Scott's article it looked like BB(6) was large. How large was hard to say. Intuitions about how large BB(6) would be are hard to come by, so the new result is neither surprising nor unsurprising. 

2) We will never know BB(6). Shucky Darns!

3) Many of the results on BB are not published in refereed journals. However, the ones mentioned in the context of BB(5) and BB(6) were verified in Coq.  I doubt other parts of math could take this approach;  however, it is interesting that results can be verified via computer in this field. Indeed- I doubt a referee could verify the results without a computer aid. 

4) Why the interest in BB? Some speculation:

a) Computing power is such that one can actually get out some results (read Scott's blog on BB(5) for more on that).

b) The internet: there are not that many people working on BB but those that are can easily communicate with each other. 

c) Scott's article and his blog posts on it helped generate interest. Since I asked Scott to write the article for my open problems column, I get some credit here also (very little).

d) Results generate interest, and interest generates results.

e) Items a,b,c,d,e all help to reinforce each other. 

By gasarch

We prove that Boolean matrices with bounded $\gamma_2$-norm or bounded normalized trace norm must contain a linear-sized all-ones or all-zeros submatrix, verifying a conjecture of Hambardzumyan, Hatami, and Hatami. We also present further structural results about Boolean matrices of bounded $\gamma_2$-norm and discuss applications in communication complexity, operator theory, spectral graph theory, and extremal combinatorics. As a key application, we establish an inverse theorem for MaxCut. A celebrated result of Edwards states that every graph $G$ with $m$ edges has a cut of size at least $\frac{m}{2}+\frac{\sqrt{8m+1}-1}{8}$, with equality achieved by complete graphs with an odd number of vertices. To contrast this, we prove that if the MaxCut of $G$ is at most $\frac{m}{2}+O(\sqrt{m})$, then $G$ must contain a clique of size $\Omega(\sqrt{m})$.

Authors: Zehua Lai, Lek-Heng Lim, Tianyun Tang

We show that linearly constrained linear optimization over a Stiefel or Grassmann manifold is NP-hard in general. We show that the same is true for unconstrained quadratic optimization over a Stiefel manifold. We will establish the nonexistence of FPTAS for these optimization problems over a Stiefel manifold. As an aside we extend our results to flag manifolds. Combined with earlier findings, this shows that manifold optimization is a difficult endeavor -- even the simplest problems like LP and unconstrained QP are already NP-hard on the most common manifolds.

Authors: Oswin Aichholzer, Joseph Dorfer

We provide a linear time algorithm to determine the flip distance between two plane spanning paths on a point set in convex position. At the same time, we show that the happy edge property does not hold in this setting. This has to be seen in contrast to several results for reconfiguration problems where the absence of the happy edge property implies algorithmic hardness of the flip distance problem. Further, we show that our algorithm can be adapted for (1) compatible flips (2) local flips and (3) flips for plane spanning paths in simple polygons.

Authors: Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen, Shyam Narayanan, Sandeep Silwal

A hypothesis testing algorithm is replicable if, when run on two different samples from the same distribution, it produces the same output with high probability. This notion, defined by by Impagliazzo, Lei, Pitassi, and Sorell [STOC'22], can increase trust in testing procedures and is deeply related to algorithmic stability, generalization, and privacy. We build general tools to prove lower and upper bounds on the sample complexity of replicable testers, unifying and quantitatively improving upon existing results. We identify a set of canonical properties, and prove that any replicable testing algorithm can be modified to satisfy these properties without worsening accuracy or sample complexity. A canonical replicable algorithm computes a deterministic function of its input (i.e., a test statistic) and thresholds against a uniformly random value in $[0,1]$. It is invariant to the order in which the samples are received, and, if the testing problem is ``symmetric,'' then the algorithm is also invariant to the labeling of the domain elements, resolving an open question by Liu and Ye [NeurIPS'24]. We prove new lower bounds for uniformity, identity, and closeness testing by reducing to the case where the replicable algorithm satisfies these canonical properties. We systematize and improve upon a common strategy for replicable algorithm design based on test statistics with known expectation and bounded variance. Our framework allow testers which have been extensively analyzed in the non-replicable setting to be made replicable with minimal overhead. As direct applications of our framework, we obtain constant-factor optimal bounds for coin testing and closeness testing and get replicability for free in a large parameter regime for uniformity testing. We also give state-of-the-art bounds for replicable Gaussian mean testing, and, unlike prior work, our algorithm runs in polynomial time.

Authors: Jan Eube, Kelin Luo, Dorian Reineccius, Heiko Röglin, Melanie Schmidt

The connected $k$-median problem is a constrained clustering problem that combines distance-based $k$-clustering with connectivity information. The problem allows to input a metric space and an unweighted undirected connectivity graph that is completely unrelated to the metric space. The goal is to compute $k$ centers and corresponding clusters such that each cluster forms a connected subgraph of $G$, and such that the $k$-median cost is minimized. The problem has applications in very different fields like geodesy (particularly districting), social network analysis (especially community detection), or bioinformatics. We study a version with overlapping clusters where points can be part of multiple clusters which is natural for the use case of community detection. This problem variant is $\Omega(\log n)$-hard to approximate, and our main result is an $\mathcal{O}(k^2 \log n)$-approximation algorithm for the problem. We complement it with an $\Omega(n^{1-\epsilon})$-hardness result for the case of disjoint clusters without overlap with general connectivity graphs, as well as an exact algorithm in this setting if the connectivity graph is a tree.

Authors: Lorenzo Carfagna, Carlo Tosoni

We study the problem of indexing and compressing tries using a BWT-based approach. Specifically, we consider a succinct and compressed representation of the XBWT of Ferragina et al.\ [FOCS '05, JACM '09] corresponding to the analogous of the FM-index [FOCS '00, JACM '05] for tries. This representation allows to efficiently count the number of nodes reached by a given string pattern. To analyze the space complexity of the above trie index, we propose a proof for the combinatorial problem of counting the number of tries with a given symbol distribution. We use this formula to define a worst-case entropy measure for tries, as well as a notion of k-th order empirical entropy. In particular, we show that the relationships between these two entropy measures are similar to those between the corresponding well-known measures for strings. We use these measures to prove that the XBWT of a trie can be encoded within a space bounded by our k-th order empirical entropy plus a o(n) term, with n being the number of nodes in the trie. Notably, as happens for strings, this space bound can be reached for every sufficiently small k simultaneously. Finally, we compare the space complexity of the above index with that of the r-index for tries proposed by Prezza [SODA '21] and we prove that in some cases the FM-index for tries is asymptotically smaller.

Authors: Tomasz Kociumaka, Ali Shahali

The tree edit distance is a natural dissimilarity measure between rooted ordered trees whose nodes are labeled over an alphabet $\Sigma$. It is defined as the minimum number of node edits (insertions, deletions, and relabelings) required to transform one tree into the other. In the weighted variant, the edits have associated costs (depending on the involved node labels) normalized so that each cost is at least one, and the goal is to minimize the total cost of edits. The unweighted tree edit distance between two trees of total size $n$ can be computed in $O(n^{2.6857})$ time; in contrast, determining the weighted tree edit distance is fine-grained equivalent to the All-Pairs Shortest Paths problem and requires $n^3/2^{\Omega(\sqrt{\log n})}$ time [Nogler et al.; STOC'25]. These super-quadratic running times are unattractive for large but very similar trees, which motivates the bounded version of the problem, where the runtime is parameterized by the computed distance $k$, potentially yielding faster algorithms for $k\ll n$. Previous best algorithms for the bounded unweighted setting run in $O(nk^2\log n)$ time [Akmal & Jin; ICALP'21] and $O(n + k^7\log k)$ time [Das et al.; STOC'23]. For the weighted variant, the only known running time has been $O(n + k^{15})$. We present an $O(n + k^6\log k)$-time algorithm for computing the bounded tree edit distance in both the weighted and unweighted settings. Our approach begins with an alternative $O(nk^2\log n)$-time algorithm that handles weights and is significantly easier to analyze than the existing counterpart. We then introduce a novel optimization that leverages periodic structures within the input trees. To utilize it, we modify the $O(k^5)$-size $O(n)$-time universal kernel, the central component of the prior $O(n + k^{O(1)})$-time algorithms, so that it produces instances containing these periodic structures.