Theory of Computing Report

The Cayley-Bacharach theorem and its applications

Cosmin Pohoata’s new and beautiful blog post presents several combinatorial applications of the Cayley–Bacharach theorem. Let me also mention his earlier post, in which he gave a new proof of Jamison’s direction tree theorem: every finite noncollinear point set in admits a admits a direction tree—that is, a spanning tree whose edges have pairwise distinct directions.

In January, after a long break, Cosmin wrote another post presenting an entropy-based proof of an interesting product–sum theorem over finite fields.

Some direction trees from Jamison’s original paper

By Gil Kalai

This is Part 2 of a blogged essay “Steampunk Data Science.” A table of contents is here.

Though nutrition science of his time suggested otherwise, Stephen Babcock knew you couldn’t feed cows coal. He would devote his life to finding the best diet for cattle and, in the process, precipitate the discovery of vitamins.

In 1888, Babcock moved to Madison to chair the Department of Agricultural Chemistry at the University of Wisconsin. Agriculture was big business in Wisconsin, and the university was founded as a land-grant institution tasked with emphasizing research and education in agriculture as part of its core academic mission. We all now know Wisconsin as the dairy state, but in the mid-1800s, Wisconsin’s primary export was wheat. However, after seasonal blights and competition from more southernly midwestern states like Iowa, Wisconsin farmers began to shift their emphasis. By the turn of the century, 90% of Wisconsin farms reared dairy cows. By 1915, Wisconsin produced more dairy than any other state in the country.1

This transition to dairy farming was the product of an ambitious public-private partnership between the state’s farmers, government, and university. The university had a mandate to improve the economic and social conditions of Wisconsin. As part of this mission, they established an agricultural research station on the western edge of campus. You can still visit barns and silos. Though it sounds unusual today, the top biologists and chemists in the 1800s devoted major research efforts to improving agriculture.

A particularly important question for farmers was how to feed their livestock. Cows, in particular, are large, hungry animals and are expensive to feed. With the inherently low margins of farming, farmers wanted to spend as little on them as possible. A central research theme in 1800s Agricultural Chemistry was finding the least expensive diet that produced healthy, large cows that gave delicious milk and bore healthy offspring.

When Babcock arrived in Wisconsin, modern nutrition theory was in its infancy. Protein had been discovered in 1838, and most nutritionists understood that it was essential to a healthy diet. As often happens after a revolutionary discovery, the conventional advice from scientific experts focused too strongly on their newly discovered nutrient. Wilbur Atwater had devised a method to determine the available protein and caloric energy in foods based on nitrogen content. From this, nutritional guidelines were proposed to maximize protein at the cheapest price possible.

You couldn’t buy big tubs of whey isolate in 1887, and the table above lists some potential alternatives for the protein-conscious. Each quantity of food could be purchased for 25 cents in 1887 dollars.2 If price and protein were the only concerns and intestinal distress could be dismissed, a person would eat nothing but beans.

Having grown up on a farm himself, Babcock knew this conventional wisdom was suspect. He would ridicule Atwater and his colleagues, asking why we didn’t just feed cows dung or soft coal, as both cleared the bar for available energy and nitrogen content.

Farmers’ intuitions about feed suggested value in variety when it came to feeding cows. Babcock figured they must do this for a reason. Although these grains had similar macronutrients, no single grain would be sufficient for healthy animals. What would happen if cows were only fed single grains? If cows were only fed wheat, or only corn, or only barley, balanced so the protein and mineral content were the same, would this still yield thriving cattle?

Babcock pressured his dean to allow him to run an experiment. He proposed purchasing some young calves, raising them on single feeds, and comparing their development. The university had ample resources to tend and manage the cows, and Babcock would oversee the scientific reporting.

The dean balked. Such an interdisciplinary project would be nothing but a headache. He’d have to marshal support from the Animal Husbandry department, and they were demanding resources for their pet-breeding projects. Cows were expensive! Couldn’t Babcock pursue research on food chemistry without raising his own animals?

Though disappointed, Babcock found he could succeed in the lab without animals. In the next few years, he devised simple tests that would revolutionize dairy farming. His most famous discovery was a simple procedure to test the fat content of milk. This test could be done by civilians and allowed people to determine whether impurities had been added to the milk to dilute it or if someone had skimmed cream off the top. Moreover, farmers could use Babcock’s test to select cows that produced higher fat milk for breeding. In addition to his innovations, Babcock was an engaging, committed teacher and held forums with farmers to discuss best practices and current challenges. By 1900, Babcock had become a Wisconsin celebrity. He was a fixture in both the academic and farming circles across the state.3

Despite his extraordinary academic success and impact, Babcock never gave up on his single-grain experiment. He finally got his way in 1907 upon his retirement. Babcock was succeeded by Erwin Hart, who loved Babcock’s research proposal. Hart marshaled the resources for the experiment.

The university purchased 16 cows that were divided into four groups. Each of the groups of cows was fed a special diet. The first group was only fed corn, the second group only wheat, the third group only oats, and the fourth group an equal combination of the three grains. They then waited to see what would happen.

Subscribe now

By Ben Recht

Last week I had the pleasure of meeting Alex Bellos in Oxford. Among other things Bellos writes the Guardian Monday puzzle column. He gave me a copy of his latest book, Puzzle Me Twice, where the obvious answer is not correct. I got more right than wrong, but I hated being wrong. Here is one of those puzzles, Sistery Mystery (page 28), which is a variation of a puzzle from Rob Eastaway. 

Puzzle 1: Suppose the probability of a girl is 51% independently and uniformly over all children. In expectation, who has more sisters, a boy or a girl?

Go ahead and try to solve this before reading further.

In any family with both boys and girls, each boy will have one more sister than each girl. For example in a family with four girls, each boy has four sisters and each girl only has three. Thus boys have more sisters on average.

Wrong, it's exactly the same. To see this consider Alex, the sixth child of a ten-child family. The number of Alex's sisters is independent of Alex's gender. This is a pretty robust result, it doesn't depend on the probability of a child being a girl, or if we allow non-binary children, or if the distributions aren't identical, say the probability of a girl is higher for later kids in a family. All you need is independence.

So what's wrong with my initial intuition that in every family boys have more sisters than girls. Eastaway suggests this gets balanced by the families of a single gender, but this happens rarely for large families. Instead it's a variation of Simpson's paradox. The naive argument doesn't account for the fact that girls are overrepresented in girl-heavy families. Consider a family of two boys and eight girls. Each of the two boys has eight sisters but four times as many girls have seven sisters, which adds to the expected value more to the girls than the boys.

If you lose independence the solution may not hold, for example if we have identical twins. 

I'll leave you with one more puzzle.

Puzzle 2: Suppose you are in a country where each family has children until they get their first boy. In this country, do boys or girls have more sisters on average?

Answer below.

In Puzzle 2 we lose independence and if Alex is a girl, she's more likely to be in a family with many girls. Indeed if boys and girls have equal probability, when you work out the infinite sums in expectation a boy will have one sister and a girl will have two.

By Lance Fortnow

Authors: Antonio Cruciani, Avinandan Das, Massimo Equi, Henrik Lievonen, Diep Luong-Le, Augusto Modanese, Jukka Suomela

Common definitions of the "standard" LOCAL model tend to be sloppy and even self-contradictory on one point: do the nodes update their state using an arbitrary function or a computable function? So far, this distinction has been safe to neglect, since problems where it matters seem contrived and quite different from e.g. typical local graph problems studied in this context. We show that this question matters even for locally checkable labeling problems (LCLs), perhaps the most widely studied family of problems in the context of the LOCAL model. Furthermore, we show that assumptions about computability are directly connected to another aspect already recognized as highly relevant: whether we have any knowledge of $n$, the size of the graph. Concretely, we show that there is an LCL problem $Π$ with the following properties: 1. $Π$ can be solved in $O(\log n)$ rounds if the \textsf{LOCAL} model is uncomputable. 2. $Π$ can be solved in $O(\log n)$ rounds in the computable model if we know any upper bound on $n$. 3. $Π$ requires $Ω(\sqrt{n})$ rounds in the computable model if we do not know anything about $n$. We also show that the connection between computability and knowledge of $n$ holds in general: for any LCL problem $Π$, if you have any bound on $n$, then $Π$ has the same round complexity in the computable and uncomputable models.

Authors: Amir Shpilka, Yann Tal

We study deterministic polynomial identity testing (PIT) and reconstruction algorithms for depth-$4$ arithmetic circuits of the form \[ Σ^{[r]}\!\wedge^{[d]}\!Σ^{[s]}\!Π^{[δ]}. \] This model generalizes Waring decompositions and diagonal circuits, and captures sums of powers of low-degree sparse polynomials. Specifically, each circuit computes a sum of $r$ terms, where each term is a $d$-th power of an $s$-sparse polynomial of degree $δ$. This model also includes algebraic representations that arise in tensor decomposition and moment-based learning tasks such as mixture models and subspace learning. We give deterministic worst-case algorithms for PIT and reconstruction in this model. Our PIT construction applies when $d>r^2$ and yields explicit hitting sets of size $O(r^4 s^4 n^2 d δ^3)$. The reconstruction algorithm runs in time $\textrm{poly}(n,s,d)$ under the condition $d=Ω(r^4δ)$, and in particular it tolerates polynomially large top fan-in $r$ and bottom degree $δ$. Both results hold over fields of characteristic zero and over fields of sufficiently large characteristic. These algorithms provide the first polynomial-time deterministic solutions for depth-$4$ powering circuits with unbounded top fan-in. In particular, the reconstruction result improves upon previous work which required non-degeneracy or average-case assumptions. The PIT construction relies on the ABC theorem for function fields (Mason-Stothers theorem), which ensures linear independence of high-degree powers of sparse polynomials after a suitable projection. The reconstruction algorithm combines this with Wronskian-based differential operators, structural properties of their kernels, and a robust version of the Klivans-Spielman hitting set.

Authors: Philip Z. Maymin

I prove that competitive market outcomes require computational intractability. If P = NP, firms can efficiently solve the collusion detection problem, identifying deviations from cooperative agreements in complex, noisy markets and thereby making collusion sustainable as an equilibrium. If P != NP, the collusion detection problem is computationally infeasible for markets satisfying a natural instance-hardness condition on their demand structure, rendering punishment threats non-credible and collusion unstable. Combined with Maymin (2011), who proved that market efficiency requires P = NP, this yields a fundamental impossibility: markets can be informationally efficient or competitive, but not both. Artificial intelligence, by expanding firms' computational capabilities, is pushing markets from the competitive regime toward the collusive regime, explaining the empirical emergence of algorithmic collusion without explicit coordination.

Authors: Alexander R. Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu

Locally Decodable Codes (LDCs) are error-correcting codes $C\colonΣ^n\rightarrow Σ^m,$ encoding \emph{messages} in $Σ^n$ to \emph{codewords} in $Σ^m$, with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length $m$ that is super-polynomial in $n$, for codes with constant query complexity and constant alphabet size. In a very surprising result, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (SICOMP 2006) show how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we study RLDCs in the standard Hamming-error setting. We prove an exponential lower bound on the length of Hamming RLDCs making $2$ queries (even adaptively) over the binary alphabet. This answers a question explicitly raised by Gur and Lachish (SICOMP 2021) and is the first exponential lower bound for RLDCs. Combined with the results of Ben-Sasson et al., our result exhibits a ``phase-transition''-type behavior on the codeword length for some constant-query complexity. We achieve these lower bounds via a transformation of RLDCs to standard Hamming LDCs, using a careful analysis of restrictions of message bits that fix codeword bits.

Authors: Petar Hristov, Ingrid Hotz, Talha Bin Masood

We present an exact and efficient algorithm for computing the Reeb space of a bivariate PL map. The Reeb space is a topological structure that generalizes the Reeb graph to the setting of multiple scalar-valued functions defined over a shared domain, a situation that frequently arises in practical applications. While the Reeb graph has become a standard tool in computer graphics, shape analysis, and scientific visualization, the Reeb space is still in the early stages of adoption. Although several algorithms for computing the Reeb space have been proposed, none offer an implementation that is both exact and efficient, which has substantially limited its practical use. To address this gap, we introduce singular arrange and traverse, a new algorithm built upon the arrange and traverse framework. Our method exploits the fact that, in the bivariate case, only singular edges contribute to the structure of Reeb space, allowing us to ignore many regular edges. This observation results in substantial efficiency gains on datasets where most edges are regular, which is common in many numerical simulations of physical systems. We provide an implementation of our method and benchmark it against the original arrange and traverse algorithm, showing performance gains of up to four orders of magnitude on real-world datasets.

Authors: David Knapp, Johannes Albrecht Holke, Thomas Spenke, Carsten Burstedde

The forest-of-refinement-trees approach allows for dynamic adaptive mesh refinement (AMR) at negligible cost. While originally developed for quadrilateral and hexahedral elements, previous work established the theory and algorithms for unstructured meshes of simplicial and prismatic elements. To harness the full potential of tree-based AMR for three-dimensional mixed-element meshes, this paper introduces the pyramid as a new functional element type; its primary purpose is to connect tetrahedral and hexahedral elements without hanging edges.We present a well-defined space-filling curve (SFC) for the pyramid and detail how the unique challenges on the element and forest level associated with the pyramidal refinement are resolved. We propose the necessary functional design and generalize the fundamental global parallel algorithms for refinement, coarsening, partitioning, and face ghost exchange to fully support this new element. Our demonstrations confirm the efficiency and scalability of this complete, hybrid-element dynamic AMR framework.

Authors: Mikael Vejdemo-Johansson

Sol LeWitt famously enumerated all the incomplete open cubes, finding 122 of these connected, non-planar subsets of the edges of the cube. Since then, while several projects have revisited the cube enumeration, no such enumeration has been published for any other interesting solid. In this paper we present work on enumerating all the incomplete open platonic solids, finding 6 tetrahedra, 122 cubes (just like LeWitt), 185 octahedra, 2\,423\,206 dodecahedra and 16\,096\,166 icosahedra.

Authors: Petr Chmel, Aditi Dudeja, Michal Koucký, Ian Mertz, Ninad Rajgopal

We develop catalytic algorithms for fundamental problems in algorithm design that run in polynomial time, use only $\mathcal{O}(\log(n))$ workspace, and use sublinear catalytic space matching the best-known space bounds of non-catalytic algorithms running in polynomial time. First, we design a polynomial time algorithm for directed $s$-$t$ connectivity using $n \big/ 2^{Θ(\sqrt{\log n})}$ catalytic space, which matches the state-of-the-art time-space bounds in the non-catalytic setting [Barnes et al., 1998], and improves the catalytic space usage of the best known algorithm [Cook and Pyne, 2026]. Furthermore, using only $\mathcal{O}(\log(n))$ random bits we get a randomized algorithm whose running time nearly matches the fastest time bounds known for space-unrestricted algorithms. Second, we design polynomial time algorithms for the problems of computing Edit Distance, Longest Common Subsequence, and the Discrete Fréchet Distance, again using $n \big/ 2^{Θ(\sqrt{\log n})}$ catalytic space. This again matches non-catalytic time-space frontier for Edit Distance and Least Common Subsequence [Kiyomi et al., 2021].

Authors: Roman Edenhofer

We prove a space-space trade-off for directed $st$-connectivity in the catalytic space model. For any integer $k \leq n$, we give an algorithm that decides directed $st$-connectivity using $O(\log n \cdot \log k+\log n)$ regular workspace and $O\left(\frac{n}{k} \cdot \log^2 n\right)$ bits of catalytic memory. This interpolates between the classical $O(\log^2 n)$-space bound from Savitch's algorithm and a catalytic endpoint with $O(\log n)$ workspace and $O(n\cdot \log^2 n)$ catalytic memory. As a warm-up, we present a catalytic variant of Savitch's algorithm achieving the endpoint above. Up to logarithmic factors, this matches the smallest catalyst size currently known for catalytic logspace algorithms, due to Cook and Pyne (ITCS 2026). Our techniques also extend to counting the number of walks from $s$ to $t$ of a given length $\ell\leq n$.

Authors: Ilias Diakonikolas, Daniel M. Kane

We study the complexity of smoothed agnostic learning, recently introduced by~\cite{CKKMS24}, in which the learner competes with the best classifier in a target class under slight Gaussian perturbations of the inputs. Specifically, we focus on the prototypical task of agnostically learning halfspaces under subgaussian distributions in the smoothed model. The best known upper bound for this problem relies on $L_1$-polynomial regression and has complexity $d^{\tilde{O}(1/σ^2) \log(1/ε)}$, where $σ$ is the smoothing parameter and $ε$ is the excess error. Our main result is a Statistical Query (SQ) lower bound providing formal evidence that this upper bound is close to best possible. In more detail, we show that (even for Gaussian marginals) any SQ algorithm for smoothed agnostic learning of halfspaces requires complexity $d^{Ω(1/σ^{2}+\log(1/ε))}$. This is the first non-trivial lower bound on the complexity of this task and nearly matches the known upper bound. Roughly speaking, we show that applying $L_1$-polynomial regression to a smoothed version of the function is essentially best possible. Our techniques involve finding a moment-matching hard distribution by way of linear programming duality. This dual program corresponds exactly to finding a low-degree approximating polynomial to the smoothed version of the target function (which turns out to be the same condition required for the $L_1$-polynomial regression to work). Our explicit SQ lower bound then comes from proving lower bounds on this approximation degree for the class of halfspaces.

Authors: Kimon Fountoulakis, David Martínez-Rubio

We study the degree-weighted work required to compute $\ell_1$-regularized PageRank using the standard one-gradient-per-iteration accelerated proximal-gradient method (FISTA). For non-accelerated local methods, the best known worst-case work scales as $\widetilde{O} ((αρ)^{-1})$, where $α$ is the teleportation parameter and $ρ$ is the $\ell_1$-regularization parameter. A natural question is whether FISTA can improve the dependence on $α$ from $1/α$ to $1/\sqrtα$ while preserving the $1/ρ$ locality scaling. The challenge is that acceleration can break locality by transiently activating nodes that are zero at optimality, thereby increasing the cost of gradient evaluations. We analyze FISTA on a slightly over-regularized objective and show that, under a checkable confinement condition, all spurious activations remain inside a boundary set $\mathcal{B}$. This yields a bound consisting of an accelerated $(ρ\sqrtα)^{-1}\log(α/\varepsilon)$ term plus a boundary overhead $\sqrt{vol(\mathcal{B})}/(ρα^{3/2})$. We provide graph-structural conditions that imply such confinement. Experiments on synthetic and real graphs show the resulting speedup and slowdown regimes under the degree-weighted work model.

Authors: Qiming Cui, Michael Dinitz

We revisit the central online problem of ski rental in the "algorithms with predictions" framework from the point of view of distributional predictions. Ski rental was one of the first problems to be studied with predictions, where a natural prediction is simply the number of ski days. But it is both more natural and potentially more powerful to think of a prediction as a distribution p-hat over the ski days. If the true number of ski days is drawn from some true (but unknown) distribution p, then we show as our main result that there is an algorithm with expected cost at most OPT + O(min(max({eta}, 1) * sqrt(b), b log b)), where OPT is the expected cost of the optimal policy for the true distribution p, b is the cost of buying, and {eta} is the Earth Mover's (Wasserstein-1) distance between p and p-hat. Note that when {eta} < o(sqrt(b)) this gives additive loss less than b (the trivial bound), and when {eta} is arbitrarily large (corresponding to an extremely inaccurate prediction) we still do not pay more than O(b log b) additive loss. An implication of these bounds is that our algorithm has consistency O(sqrt(b)) (additive loss when the prediction error is 0) and robustness O(b log b) (additive loss when the prediction error is arbitrarily large). Moreover, we do not need to assume that we know (or have any bound on) the prediction error {eta}, in contrast with previous work in robust optimization which assumes that we know this error. We complement this upper bound with a variety of lower bounds showing that it is essentially tight: not only can the consistency/robustness tradeoff not be improved, but our particular loss function cannot be meaningfully improved.

Authors: Robin A. Heinonen

The exact leading asymptotics of solutions to the symmetric linear search problem are obtained for any positive probability density on the real line with a monotonic, sufficiently regular tail. A similar result holds for densities on a compact interval.

Authors: Vinicius Tikara Venturi Date, Leandro Miranda Zatesko

The string repetitiveness measures $χ$ (the size of a smallest suffixient set of a string) and $r$ (the number of runs in the Burrows--Wheeler Transform) are related. Recently, we have shown that the bound $χ\leq 2r$, proved by Navarro et al., is asymptotically tight as the size $σ$ of the alphabet increases, but achieving near-tight ratios for fixed $σ> 2$ remained open. We introduce a \emph{2-branching property}: a cyclic string is 2-branching at order~$k$ if every $(k{-}1)$-length substring admits exactly two $k$-length extensions. We show that 2-branching strings of order~$k$ yield closed-form ratios $χ/r = (2σ^{k-1}+1)/(σ^{k-1}+4)$. For order~$3$, we give an explicit construction for every $σ\geq 2$, narrowing the gap to~$2$ from $O(1/σ)$ to $O(1/σ^2)$. For $σ\in \{3,4\}$, we additionally present order-$5$ instances with ratios exceeding~$1.91$.

Authors: Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou

We study adversarially robust algorithms for insertion-deletion (turnstile) streams, where future updates may depend on past algorithm outputs. While robust algorithms exist for insertion-only streams with only a polylogarithmic overhead in memory over non-robust algorithms, it was widely conjectured that turnstile streams of length polynomial in the universe size $n$ require space linear in $n$. We refute this conjecture, showing that robustness can be achieved using space which is significantly sublinear in $n$. Our framework combines multiple linear sketches in a novel estimator-corrector-learner framework, yielding the first insertion-deletion algorithms that approximate: (1) the second moment $F_2$ up to a $(1+\varepsilon)$-factor in polylogarithmic space, (2) any symmetric function $\cal{F}$ with an $\mathcal{O}(1)$-approximate triangle inequality up to a $2^{\mathcal{O}(C)}$ factor in $\tilde{\mathcal{O}}(n^{1/C}) \cdot S(n)$ bits of space, where $S$ is the space required to approximate $\cal{F}$ non-robustly; this includes a broad class of functions such as the $L_1$-norm, the support size $F_0$, and non-normed losses such as the $M$-estimators, and (3) $L_2$ heavy hitters. For the $F_2$ moment, our algorithm is optimal up to $\textrm{poly}((\log n)/\varepsilon)$ factors. Given the recent results of Gribelyuk et al. (STOC, 2025), this shows an exponential separation between linear sketches and non-linear sketches for achieving adversarial robustness in turnstile streams.

Authors: Eduar Castrillo Velilla

The Weisfeiler-Lehman (WL) hierarchy is a cornerstone framework for graph isomorphism testing and structural analysis. However, scaling beyond 1-WL to 3-WL and higher requires tensor-based operations that scale as O(n^3) or O(n^4), making them computationally prohibitive for large graphs. In this paper, we start from the Original-DRESS equation (Castrillo, Leon, and Gomez, 2018)--a parameter-free, continuous dynamical system on edges--and show that it distinguishes the prism graph from K_{3,3}, a pair that 1-WL provably cannot separate. We then generalize it to Motif-DRESS, which replaces triangle neighborhoods with arbitrary structural motifs and converges to a unique fixed point under three sufficient conditions, and further to Generalized-DRESS, an abstract template parameterized by the choice of neighborhood operator, aggregation function and norm. Finally, we introduce Delta-DRESS, which runs DRESS on each node-deleted subgraph G\{v}, connecting the framework to the Kelly-Ulam reconstruction conjecture. Both Motif-DRESS and Delta-DRESS empirically distinguish Strongly Regular Graphs (SRGs)--such as the Rook and Shrikhande graphs--that confound 3-WL. Our results establish the DRESS family as a highly scalable framework that empirically surpasses both 1-WL and 3-WL on well-known benchmark graphs, without the prohibitive O(n^4) computational cost.

Authors: Isaac Rudich, Louis-Martin Rousseau

Decision Diagrams (DDs) have emerged as a powerful tool for discrete optimization, with rapidly growing adoption. DDs are directed acyclic layered graphs; restricted DDs are a generalized greedy heuristic for finding feasible solutions, and relaxed DDs compute combinatorial relaxed bounds. There is substantial theory that leverages DD-based bounding, yet the complexity of constructing the DDs themselves has received little attention. Standard restricted DD construction requires $O(w \log(w))$ per layer; standard relaxed DD construction requires $O(w^2)$, where $w$ is the width of the DD. Increasing $w$ improves bound quality at the cost of more time and memory. We introduce implicit Decision Diagrams, storing arcs implicitly rather than explicitly, and reducing per-layer complexity to $O(w)$ for restricted and relaxed DDs. We prove this is optimal: any framework treating state-update and merge operations as black boxes cannot do better. Optimal complexity shifts the challenge from algorithmic overhead to low-level engineering. We show how implicit DDs can drive a MIP solver, and release ImplicitDDs.jl, an open-source Julia solver exploiting the implementation refinements our theory enables. Experiments demonstrate the solver outperforms Gurobi on Subset Sum.

Authors: Keigo Oka

The Unix command \texttt{find} is among the first commands taught to beginners, yet remains indispensable for experienced engineers. In this paper, we demonstrate that \texttt{find} possesses unexpected computational power, establishing three Turing completeness results using the GNU implementation (a standard in Linux distributions). (1) \texttt{find} + \texttt{mkdir} (a system that has only \texttt{find} and \texttt{mkdir}) is Turing complete: by encoding computational states as directory paths and using regex back-references to copy substrings, we simulate 2-tag systems. (2) GNU \texttt{find} 4.9.0+ alone is Turing complete: by reading and writing to files during traversal, we simulate a two-counter machine without \texttt{mkdir}. (3) \texttt{find} + \texttt{mkdir} without regex back-references is still Turing complete: by a trick of encoding regex patterns directly into directory names, we achieve the same power. These results place \texttt{find} among the ``surprisingly Turing-complete'' systems, highlighting the hidden complexity within seemingly simple standard utilities.

Authors: Julien Dallot, Yuval Emek, Yuval Gil, Maciej Pacut, Stefan Schmid

This paper introduces a new model for ML-augmented online decision making, called online algorithms with unreliable guidance (OAG). This model completely separates between the predictive and algorithmic components, thus offering a single well-defined analysis framework that relies solely on the considered problem. Formulated through the lens of request-answer games, an OAG algorithm receives, with each incoming request, a piece of guidance which is taken from the problem's answer space; ideally, this guidance is the optimal answer for the current request, however with probability $β$, the guidance is adversarially corrupted. The goal is to develop OAG algorithms that admit good competitiveness when $β= 0$ (a.k.a. consistency) as well as when $β= 1$ (a.k.a. robustness); the appealing notion of smoothness, that in most prior work required a dedicated loss function, now arises naturally as $β$ shifts from $0$ to $1$. We then describe a systematic method, called the drop or trust blindly (DTB) compiler, which transforms any online algorithm into a learning-augmented online algorithm in the OAG model. Given a prediction-oblivious online algorithm, its learning-augmented counterpart produced by applying the DTB compiler either follows the incoming guidance blindly or ignores it altogether and proceeds as the initial algorithm would have; the choice between these two alternatives is based on the outcome of a (biased) coin toss. As our main technical contribution, we prove (rigorously) that although remarkably simple, the class of algorithms produced via the DTB compiler includes algorithms with attractive consistency-robustness guarantees for three classic online problems: for caching and uniform metrical task systems our algorithms are optimal, whereas for bipartite matching (with adversarial arrival order), our algorithm outperforms the state-of-the-art.

Authors: Ria Stevens, Fangshuo Liao, Barbara Su, Jianqiang Li, Anastasios Kyrillidis

We approach the Max-3-Cut problem through the lens of maximizing complex-valued quadratic forms and demonstrate that low-rank structure in the objective matrix can be exploited, leading to alternative algorithms to classical semidefinite programming (SDP) relaxations and heuristic techniques. We propose an algorithm for maximizing these quadratic forms over a domain of size $K$ that enumerates and evaluates a set of $O\left(n^{2r-1}\right)$ candidate solutions, where $n$ is the dimension of the matrix and $r$ represents the rank of an approximation of the objective. We prove that this candidate set is guaranteed to include the exact maximizer when $K=3$ (corresponding to Max-3-Cut) and the objective is low-rank, and provide approximation guarantees when the objective is a perturbation of a low-rank matrix. This construction results in a family of novel, inherently parallelizable and theoretically-motivated algorithms for Max-3-Cut. Extensive experimental results demonstrate that our approach achieves performance comparable to existing algorithms across a wide range of graphs, while being highly scalable.

This is Part 1 of a blogged essay “Steampunk Data Science.” A table of contents is here.

In a back-and-forth with Ryan Briggs about the “crisis” of hiding null results in political science, Stephen Wild asked a loaded question.

“How different is the current situation from the past, whether it be 50 years ago or 150 years ago? Phrased in another, slightly more provocative way, what if it’s always been this way?”

In response, Ryan suggested that quantitative social science is very young and is getting better, and can be fixed. I’m not sure. Quantitative social science is only young by relative standards. You could argue the modern discipline starts after the French Revolution with academic bureaucrats like Adolphe Quetelet in the 1800s. Udny Yule was using linear regression to suss out the causation of poverty in 1900. John Maynard Keynes wrote about probabilistic methods for understanding society in the 1920s. The first application of machine learning techniques to the prediction of prison recidivism was in 1928.

While quantitative social science isn’t new, you could argue that we’ve reached a new crisis. Perhaps because of publish-or-perish incentives, science has reached new lows, where nothing is reproducible, and most published results are wrong. Researchers, journalists, and politicians alike complain that contemporary science faces a terrible reproduction crisis. People love writing meta-analyses like the one I wrote about last week. Psychology has been in crisis for a decade. Cancer research is in crisis. Machine learning is in crisis.

Conventional wisdom suggests that the reproduction crisis threatens the fundamental legitimacy of the sciences. Operatives in the United States federal government have been using this “crisis” as an excuse to slash science funding and attack universities. All of this panic begs Stephen’s question of when science used to be better. It implicitly suggests that there was a golden age when all published results were true, and scientists diligently reproduced each other’s work.

Is this true? Was reproduction a core element of prior scientific or engineering revolutions?

It’s not hard to find people decrying the demise of science throughout history. I wrote about when Science Magazine dedicated an entire editorial section to worrying about the public’s turn against science in 1957. The fifties were supposedly the wonder years. You want to go back even further? Read Charles Babbage complaining about the state of affairs in 1830.

Now, you might argue, like Ryan does, that better methods ameliorated these crises. That somehow doing science better fixed the fields. The null hypothesis significance test, the metascientist’s best friend, is barely one hundred years old. Is it true that the science of the 1800s was doomed and hopeless because they couldn’t run randomized controlled trials and compute p-values?

In the midst of the covid lockdowns, I also found myself intrigued by this question and started digging into how science was done before the formalization of statistics. How did we figure out which interventions worked before the null hypothesis test? I ended up dumping this research into a long essay about one of the most important discoveries in human-facings sciences of the early 20th century: vitamins.

Some discoveries have simple, pithy origins, like finding mold in a petri dish. But discovering the body’s need for vitamins took decades, as physicians, biologists, and chemists assembled evidence from an array of confusing empirical findings from many distant parts of the world. There were dozens of erroneous hypotheses put forward as truths in the literature. There were sloppy data practices and poorly documented experimental protocols. But through this confusion, clarity eventually coalesced into a completely new understanding of diet and disease.

I wrote this up about four years ago, but I’ve never figured out how to publish it. Initially, I thought it would be a core part of my book on automated decision making, The Irrational Decision (preorder now! It helps the substack), but the vitamin story ended up being too much of a prequel. The discovery of vitamins happened two world wars before the development of the computer. It happened a decade before the formalization of statistics. That it’s one of the last major discoveries of the pre-data scientific age is why I find the story so fascinating.

Since The Irrational Decision comes out in two weeks, it feels appropriate to put out the prequel now. My plan is to interleave two threads: I’ll continue my liveblogging of class, and I’ll tell the story of the history of vitamins as a quintessential case study of the human-facing sciences before the mathematical formalization of statistical inference.

The discovery of vitamins and deficiency diseases shows how a chaotic lack of reproducibility might be core to science itself, and that we were quite capable of making sense of the natural world before we had access to spreadsheets and statistics software. I’ll try to convince you that none of our fancy modern machinery would have helped at all. Both then and now, there are no formal paths to discovery.

Subscribe now

By Ben Recht

We study deterministic polynomial identity testing (PIT) and reconstruction algorithms for depth-$4$ arithmetic circuits of the form \[ \Sigma^{[r]}\!\wedge^{[d]}\!\Sigma^{[s]}\!\Pi^{[\delta]}. \] This model generalizes Waring decompositions and diagonal circuits, and captures sums of powers of low-degree sparse polynomials. Specifically, each circuit computes a sum of $r$ terms, where each term is a $d$-th power of an $s$-sparse polynomial of degree $\delta$. This model also includes algebraic representations that arise in tensor decomposition and moment-based learning tasks such as mixture models and subspace learning. We give deterministic worst-case algorithms for PIT and reconstruction in this model. Our PIT construction applies when $d>r^2$ and yields explicit hitting sets of size $O(r^4 s^4 n^2 d \delta^3)$. The reconstruction algorithm runs in time $\textrm{poly}(n,s,d)$ under the condition $d=\Omega(r^4\delta)$, and in particular it tolerates polynomially large top fan-in $r$ and bottom degree $\delta$. Both results hold over fields of characteristic zero and over fields of sufficiently large characteristic. These algorithms provide the first polynomial-time deterministic solutions for depth-$4$ powering circuits with unbounded top fan-in. In particular, the reconstruction result improves upon previous work which required non-degeneracy or average-case assumptions. The PIT construction relies on the ABC theorem for function fields (Mason-Stothers theorem), which ensures linear independence of high-degree powers of sparse polynomials after a suitable projection. The reconstruction algorithm combines this with Wronskian-based differential operators, structural properties of their kernels, and a robust version of the Klivans-Spielman hitting set.

Authors: Ondřej Ježil, Dimitrios Tsintsilidas

Student-Teacher Games are a model of computation in which a computationally restricted Student attempts to produce a string satisfying a refutable property, while an all-powerful Teacher refutes incorrect candidates by providing counterexamples. By the classical result of Krajíček, Pudlák, and Takeuti [KPT90], such games capture the witnessing of $\forall\exists\forall$-formulas in bounded arithmetic. In this paper, we introduce subclasses of total search problems in the polynomial hierarchy, classified by the number of rounds and candidate answers per round required for a Student at the corresponding level to solve them. Assuming the polynomial hierarchy does not collapse, we separate these classes for different number of rounds and queries. As applications we obtain the following results: (a) We study theories of bounded arithmetic axiomatized by fine-grained variants of length induction and bounded collection. We prove a general witnessing theorem connecting their $\forall\exists\forall$-consequences to the appropriate classes of Student-Teacher Games. Under the non-collapse of the polynomial hierarchy, we separate these theories. (b) These conditional separations resolve two open problems in bounded arithmetic: one by Buss and Ressayre [Bus85, CK93] on the strength of bounded collection, and one by Pollett [Pol97] on the difference between strict and non-strict double length induction. (c) Finally, we extend the unprovability of circuit upper bounds due to Krajíček and Oliveira [KO17] to the theory $PV_1+BB(Σ^b_1)$, and the unprovability of strong co-nondeterministic circuit lower bounds due to Pich and Santhanam [PS21] to the theory $PV_1+LLIND(sΣ^b_1)$. By the preceding separations, both theories strictly extend $PV_1$ assuming $NP\nsubseteq P/poly$.

Authors: A. R. Balasubramanian, Vitor Greati, Revantha Ramanayake

For substructural logics with contraction or weakening admitting cut-free sequent calculi, proof search was analyzed using well-quasi-orders on $\mathbb{N}^d$ (Dickson's lemma), yielding Ackermannian upper bounds via controlled bad-sequence arguments. For hypersequent calculi, that argument lifted the ordering to the powerset, since a hypersequent is a (multi)set of sequents. This induces a jump from Ackermannian to hyper-Ackermannian complexity in the fast-growing hierarchy, suggesting that cut-free hypersequent calculi for extensions of the commutative Full Lambek calculus with contraction or weakening ($\mathbf{FL_{ec}}$/$\mathbf{FL_{ew}}$) inherently entail hyper-Ackermannian upper bounds. We show that this intuition does not hold: every extension of $\mathbf{FL_{ec}}$ and $\mathbf{FL_{ew}}$ admitting a cut-free hypersequent calculus has an Ackermannian upper bound on provability. To avoid the powerset, we exploit novel dependencies between individual sequents within any hypersequent in backward proof search. The weakening case, in particular, introduces a Karp-Miller style acceleration, and it improves the upper bound for the fundamental fuzzy logic $\mathbf{MTL}$. Our Ackermannian upper bound is optimal for the contraction case (realized by the logic $\mathbf{FL_{ec}}$).

Authors: Wei Feng, Haiyong Zheng

We propose a template-driven triangulation framework that embeds raster- or segmentation-derived boundaries into a regular triangular grid for stable PDE discretization on image-derived domains. Unlike constrained Delaunay triangulation (CDT), which may trigger global connectivity updates, our method retriangulates only triangles intersected by the boundary, preserves the base mesh, and supports synchronization-free parallel execution. To ensure determinism and scalability, we classify all local boundary-intersection configurations up to discrete equivalence and triangle symmetries, yielding a finite symbolic lookup table that maps each case to a conflict-free retriangulation template. We prove that the resulting mesh is closed, has bounded angles, and is compatible with cotangent-based discretizations and standard finite element methods. Experiments on elliptic and parabolic PDEs, signal interpolation, and structural metrics show fewer sliver elements, more regular triangles, and improved geometric fidelity near complex boundaries. The framework is well suited for real-time geometric analysis and physically based simulation over image-derived domains.

Authors: Chris Gartland, Mikhail Ostrovskii, Yuval Rabani, Robert Young

We prove that the distortion of any embedding into $L_1$ of the transportation cost space or earth mover distance over a $d$-dimensional grid $\{1,\dots m\}^d$ is $Ω(\log N)$, where $N$ is the number of vertices and the implicit constant is universal (in particular, independent of dimension). This lower bound matches the universal upper bound $O(\log N)$ holding for any $N$-point metric space. Our proof relies on a new Sobolev inequality for real-valued functions on the grid, based on random measures supported on dyadic cubes.

Authors: Aditya Acharya, Auguste Henry Gezalyan, David M. Mount, Danesh Sivakumar

The forward and reverse Funk weak metrics are fundamental distance functions on convex bodies that serve as the building blocks for the Hilbert and Thompson metrics. In this paper we study Voronoi diagrams under the forward and reverse Funk metrics in polygonal and elliptical cones. We establish several key geometric properties: (1) bisectors consist of a set of rays emanating from the apex of the cone, and (2) Voronoi diagrams in the $d$-dimensional forward (or reverse) Funk metrics are equivalent to additively-weighted Voronoi diagrams in the $(d-1)$-dimensional forward (or reverse) Funk metrics on bounded cross sections of the cone. Leveraging this, we provide an $O\big(n^{\ceil{\frac{d-1}{2}}+1}\big)$ time algorithm for creating these diagrams in $d$-dimensional elliptical cones using a transformation to and from Apollonius diagrams, and an $O(mn\log(n))$ time algorithm for 3-dimensional polygonal cones with $m$ facets via a reduction to abstract Voronoi diagrams. We also provide a complete characterization of when three sites have a circumcenter in 3-dimensional cones. This is one of the first algorithmic studies of the Funk metrics.

Authors: Haitao Wang

Chan [JACM, 2010] gave a data structure for maintaining the convex hull of a dynamic set of 3D points under insertions and deletions, supporting extreme-point queries. Subsequent refinements by Kaplan, Mulzer, Roditty, Seiferth, and Sharir [DCG, 2020] and Chan [DCG, 2020] preserved the framework while improving bounds. The current best result achieves $O(\log^2 n)$ amortized insertion time, $O(\log^4 n)$ amortized deletion time, and $O(\log^2 n)$ worst-case query time. These techniques also yield dynamic 2D Euclidean nearest neighbor searching via duality, where the problem becomes maintaining the lower envelope of 3D planes for vertical ray-shooting queries. Using randomized vertical shallow cuttings, Kaplan et al. [DCG, 2020] and Liu [SICOMP, 2022] extended the framework to dynamic lower envelopes of general 3D surfaces, obtaining the same asymptotic bounds and enabling nearest neighbor searching under general distance functions. We revisit Chan's framework and present a modified structure that reduces the deletion time to $O(\log^3 n \log\log n)$, while retaining $O(\log^2 n)$ amortized insertion time, at the cost of increasing the query time to $O(\log^3 n / \log\log n)$. When the overall complexity is dominated by deletions, this yields an improvement of roughly a logarithmic factor over previous results.

Authors: László Kozma, Michal Opler

Matrix multiplication is a fundamental task in almost all computational fields, including machine learning and optimization, computer graphics, signal processing, and graph algorithms (static and dynamic). Twin-width is a natural complexity measure of matrices (and more general structures) that has recently emerged as a unifying concept with important algorithmic applications. While the twin-width of a matrix is invariant to re-ordering rows and columns, most of its algorithmic applications to date assume that the input is given in a certain canonical ordering that yields a bounded twin-width contraction sequence. In general, efficiently finding such a sequence -- even for an approximate twin-width value -- remains a central and elusive open question. In this paper we show that a binary $n \times n$ matrix of twin-width $d$ can be preprocessed in $\widetilde{\mathcal{O}}_d(n^2)$ time, so that its product with any vector can be computed in $\widetilde{\mathcal{O}}_d(n)$ time. Notably, the twin-width of the input matrix need not be known and no particular ordering of its rows and columns is assumed. If a canonical ordering is available, i.e., if the input matrix is $d$-twin-ordered, then the runtime of preprocessing and matrix-vector products can be further reduced to $\mathcal{O}(n^2+dn)$ and $\mathcal{O}(dn)$. Consequently, we can multiply two $n \times n$ matrices in $\widetilde{\mathcal{O}}(n^2)$ time, when at least one of the matrices consists of 0/1 entries and has bounded twin-width. The results also extend to the case of bounded twin-width matrices with adversarial corruption. Our algorithms are significantly faster and simpler than earlier methods that involved first-order model checking and required both input matrices to be $d$-twin-ordered.

Authors: Gabriel Bathie, Paul Huber, Guillaume Lagarde, Akka Zemmari

We study the sensitivity of the Lempel-Ziv 77 compression algorithm to edits, showing how modifying a string $w$ can deteriorate or improve its compression. Our first result is a tight upper bound for $k$ edits: $\forall w' \in B(w,k)$, we have $C_{\mathrm{LZ77}}(w') \leq 3 \cdot C_{\mathrm{LZ77}}(w) + 4k$. This result contrasts with Lempel-Ziv 78, where a single edit can significantly deteriorate compressibility, a phenomenon known as a *one-bit catastrophe*. We further refine this bound, focusing on the coefficient $3$ in front of $C_{\mathrm{LZ77}}(w)$, and establish a surprising trichotomy based on the compressibility of $w$. More precisely we prove the following bounds: - if $C_{\mathrm{LZ77}}(w) \lesssim k^{3/2}\sqrt{n}$, the compression may increase by up to a factor of $\approx 3$, - if $k^{3/2}\sqrt{n} \lesssim C_{\mathrm{LZ77}}(w) \lesssim k^{1/3}n^{2/3}$, this factor is at most $\approx 2$, - if $C_{\mathrm{LZ77}}(w) \gtrsim k^{1/3}n^{2/3}$, the factor is at most $\approx 1$. Finally, we present an $\varepsilon$-approximation algorithm to pre-edit a word $w$ with a budget of $k$ modifications to improve its compression. In favorable scenarios, this approach yields a total compressed size reduction by up to a factor of~$3$, accounting for both the LZ77 compression of the modified word and the cost of storing the edits, $C_{\mathrm{LZ77}}(w') + k \log |w|$.

Authors: Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju, Clement Svendsen

In this paper, we consider the problem of replicable realizable PAC learning. We construct a particularly hard learning problem and show a sample complexity lower bound with a close to $(\log|H|)^{3/2}$ dependence on the size of the hypothesis class $H$. Our proof uses several novel techniques and works by defining a particular Cayley graph associated with $H$ and analyzing a suitable random walk on this graph by examining the spectral properties of its adjacency matrix. Furthermore, we show an almost matching upper bound for the lower bound instance, meaning if a stronger lower bound exists, one would have to consider a different instance of the problem.

Authors: Keigo Oka, Naoki Inaba, Akira Iino

You find a stain on the wall and decide to cover it with non-overlapping stickers of a single identical shape (rotation and reflection are allowed). Is it possible to find a sticker shape that fails to cover the stain? In this paper, we consider this problem under polyomino constraints and complete the classification of always-coverable stain shapes (polyominoes). We provide proofs for the maximal always-coverable polyominoes and construct concrete counterexamples for the minimal not always-coverable ones, demonstrating that such cases exist even among hole-free polyominoes. This classification consequently yields an algorithm to determine the always-coverability of any given stain. We also show that the problem of determining whether a given sticker can cover a given stain is $\NP$-complete, even though exact cover is not demanded. This result extends to the 1D case where the connectivity requirement is removed. As an illustration of the problem complexity, for a specific hexomino (6-cell) stain, the smallest sticker found in our search that avoids covering it has, although not proven minimum, a bounding box of $325 \times 325$.

Authors: Bhaskar DasGupta, Katie Kruzan

In recent years extensions of manifold Ricci curvature to discrete combinatorial objects such as graphs and hypergraphs (popularly called as "network shapes"), have found a plethora of applications in a wide spectrum of research areas ranging over metabolic systems, transcriptional regulatory networks, protein-protein-interaction networks, social networks and brain networks to deep learning models and quantum computing but, in contrast, they have been looked at by relatively fewer researchers in the algorithms and computational complexity community. As an attempt to bring these network Ricci-curvature related problems under the lens of computational complexity and foster further inter-disciplinary interactions, we provide a formal framework for studying algorithmic and computational complexity issues for detecting critical edges in an undirected graph using Ollivier-Ricci curvatures and provide several algorithmic and inapproximability results for problems in this framework. Our results show some interesting connections between the exact perfect matching and perfect matching blocker problems for bipartite graphs and our problems.

Authors: Avinandan Das

This paper investigates the semi-streaming complexity of \textit{$k$-partial coloring}, a generalization of proper graph coloring. For $k \geq 1$, a $k$-partial coloring requires that each vertex $v$ in an $n$-node graph is assigned a color such that at least $\min\{k, °(v)\}$ of its neighbors are assigned colors different from its own. This framework naturally extends classical coloring problems: specifically, $k$-partial $(k+1)$-coloring and $k$-partial $k$-coloring generalize $(Δ+1)$-proper coloring and $Δ$-proper coloring, respectively. Prior works of Assadi, Chen, and Khanna [SODA~2019] and Assadi, Kumar, and Mittal [TheoretiCS~2023] show that both $(Δ+1)$-proper coloring and $Δ$-proper coloring admit one-pass randomized semi-streaming algorithms. We explore whether these efficiency gains extend to their partial coloring generalizations and reveal a sharp computational threshold : while $k$-partial $(k+1)$-coloring admits a one-pass randomized semi-streaming algorithm, the $k$-partial $k$-coloring remains semi-streaming intractable, effectively demonstrating a ``dichotomy of one color'' in the streaming model.

Authors: Jakub Ruszil, Artur Polański, Adam Roman, Jakub Zelek

The article studies edge coverage for control flow graphs extended with explicit constraints. Achieving a given level of white-box coverage for a given code is a classic problem in software testing. We focus on designing test sets that achieve edge coverage \textit{while respecting additional constraints} between vertices. The paper analyzes how such constraints affect both the feasibility and computational complexity of edge coverage. The paper discusses five types of constraints. POSITIVE constraints require at least one test path where a given vertex precedes another. NEGATIVE constraints forbid any such test path. ONCE constraints require exactly one test path with a single occurrence of one vertex before another. MAX ONCE constraints allow such precedence in at most one test path. ALWAYS constraints require every test path containing a given vertex to also contain another vertex later on the same path. Each type models a different test requirement, such as mandatory flows, semantic exclusions, or execution cost limits. We investigate the computational complexity of finding a test set that achieves edge coverage and respects a given set of constraints. For POSITIVE constraints, the existence of an edge covering test set is decidable in polynomial time by extending standard edge coverage constructions with additional paths for each constraint. For NEGATIVE, MAX ONCE, ONCE, and ALWAYS constraints, the decision problem is NP-complete. The proofs rely on polynomial reductions from variants of SAT. The NP-completeness results hold even for restricted graph classes, including acyclic graphs, for all these four constraints. Finally, we study the fixed-parameter tractability of the NEGATIVE constraint. Although the general problem is NP-complete, the paper presents an FPT algorithm with respect to the number of constraints.

Authors: Paul Paschmanns, Vera Traub

The Steiner Tree problem asks for the cheapest way of connecting a given subset of the vertices in an undirected graph. One of the most prominent linear programming relaxations for Steiner Tree is the Bidirected Cut Relaxation (BCR). Determining the integrality gap of this relaxation is a long-standing open question. For several decades, the best known upper bound was 2, which is achievable by standard techniques. Only very recently, Byrka, Grandoni, and Traub [FOCS 2024] showed that the integrality gap of BCR is strictly below 2. We prove that the integrality gap of BCR is at most 1.898, improving significantly on the previous bound of 1.9988. For the important special case where a terminal minimum spanning tree is an optimal Steiner tree, we show that the integrality gap is at most 12/7, by providing a tight analysis of the dual-growth procedure by Byrka et al. To obtain the general bound of 1.898 on the integrality gap, we generalize their dual growth procedure to a broad class of moat-growing algorithms. Moreover, we prove that no such moat-growing algorithm yields dual solutions certifying an integrality gap below 12/7. Finally, we observe an interesting connection to the Hypergraphic Relaxation.

Authors: Felix Thaler, Sebastian Keller

We have developed a compressed neighbor list for short-range particle-particle interaction based on a space- filling curve (SFC) memory layout and particle clusters. The neighbor list can be constructed efficiently on GPUs, supporting NVIDIA and AMD hardware, and has a memory footprint of only 4 bytes per particle to store approximately 200 neighbors. Compared to the highly-optimized domain-specific neighbor list implementation of GROMACS, a molecular dynamics code, it has a comparable cluster overhead and delivers similar performance in a neighborhood pass. Thanks to the SFC-based data layout and the support for varying interaction radii per particle, our neighbor list performs well for systems with high density contrasts, such as those encountered in many astrophysical and cosmological applications. Due to the close relation between SFCs and octrees, our neighbor list seamlessly integrates with octree-based domain decomposition and multipole-based methods for long-range gravitational or electrostatic interactions. To demonstrate the coupling between long- and short-range forces, we simulate an Evrard collapse, a standard test case for the coupling between hydrodynamical and gravitational forces, on up to 1024 GPUs, and compare our results to the analytical solution.

Authors: Gero Ellmies, Till Fluschnik

We study the problem of robustly reconnecting habitats via the placement of green bridges at minimum total cost. Habitats are fragmented into patches and we seek to reconnect each habitat such that it remains connected even if any of its patches becomes unavailable. Formally, we are given an undirected graph with edge costs, a set of fixed green bridges represented as a subset of the graph's edges, a set of habitats represented as vertex subsets, and some budget. We decide whether there exists a subset of the graph's edges containing all fixed green bridges such that, for each habitat, the induced subgraph on the solution edges is 2-vertex-connected, and the total cost does not exceed the budget. We also study the 2-edge-connectivity variant, modeling the case where any single reconnecting green bridge may fail. We analyze the computational complexity of these problems, focusing on the boundary between NP-hardness and polynomial-time solvability when the maximum habitat size and maximum vertex degree are bounded by constants. We prove that for each constant maximum habitat size of at least four there exists a small constant maximum degree for which the problems are NP-hard, and complement this with polynomial-time algorithms yielding partial dichotomies for bounded habitat size and degree.

Authors: Fateme Abbasi, Martin Böhm, Jarosław Byrka, Matin Mohammadi, Yongho Shin

We study Facility Location with Matching, a Facility Location problem where, given additional information about which pair of clients is compatible to be matched, we need to match as many clients as possible and assign each matched client pair to a same open facility at minimum total cost. The problem is motivated by match-making services relevant in, for example, video games or social apps. It naturally generalizes two prominent combinatorial optimization problems -- Uncapacitated Facility Location and Minimum-cost Maximum Matching. Facility Location with Matching also generalizes the Even-constrained Facility Location problem studied by Kim, Shin, and An (Algorithmica 2023). We propose a linear programming (LP) relaxation for this problem, and present a 3.868-approximation algorithm. Our algorithm leverages the work on bifactor-approximation algorithms (Byrka and Aardal, SICOMP 2012); our main technical contribution is a rerouting subroutine that reroutes a fractional solution to be supported on a fixed maximum matching with only small additional cost. For a special case where all clients are matched, we provide a refined algorithm achieving an approximation ratio of 2.218. As our algorithms are based on rounding an optimal solution to the LP relaxation, these approximation results also give the same upper bounds on the integrality gap of the relaxation.

Authors: Duncan Adamson, Paul G Spirakis

\emph{Temporal graphs} are a generalisation of (static) graphs, defined by a sequence of \emph{snapshots}, each a static graph defined over a common set of vertices. \emph{Exploration} problems are one of the most fundamental and most heavily studied problems on temporal graphs, asking if a set of $m$ agents can visit every vertex in the graph, with each agent only allowed to traverse a single edge per snapshot. In this paper, we introduce and study \emph{always $S$-connected} temporal graphs, a generalisation of always connected temporal graphs where, rather than forming a single connected component in each snapshot, we have at most $\vert S \vert$ components, each defined by the connection to a single vertex in the set $S$. We use this formulation as a tool for exploring graphs admitting an \emph{$(r,b)$-division}, a partitioning of the vertex set into disconnected components, each of which is $S$-connected, where $\vert S \vert \leq b$. We show that an always $S$-connected temporal graph with $m = \vert S \vert$ and an average degree of $Δ$ can be explored by $m$ agents in $O(n^{1.5} m^3 Δ^{1.5}\log^{1.5}(n))$ snapshots. Using this as a subroutine, we show that any always-connected temporal graph with treewidth at most $k$ can be explored by a single agent in $O\left(n^{4/3} k^{5.5}\log^{2.5}(n)\right)$ snapshots, improving on the current state-of-the-art for small values of $k$. Further, we show that interval graph with only a small number of large cliques can be explored by a single agent in $O\left(n^{4/3} \log^{2.5}(n)\right)$ snapshots.

Authors: Thomas Erlebach, Kelin Luo, Wen Zhang

Given a fleet of drones with different speeds and a set of package delivery requests, the collaborative delivery problem asks for a schedule for the drones to collaboratively carry out all package deliveries, with the objective of minimizing the total travel time of all drones. We show that the best non-preemptive schedule (where a package that is picked up at its source is immediately delivered to its destination by one drone) is within a factor of three of the best preemptive schedule (where several drones can participate in the delivery of a single package). Then, we present a constant-factor approximation algorithm for the problem of computing the best non-preemptive schedule. The algorithm reduces the problem to a tree combination problem and uses a primal-dual approach to solve the latter. We have implemented a version of the algorithm optimized for practical efficiency and report the results of experiments on large-scale instances with synthetic and real-world data, demonstrating that our algorithm is scalable and delivers schedules of excellent quality.

Authors: Sankardeep Chakraborty, Roberto Grossi, Ren Kimura, Giulia Punzi, Kunihiko Sadakane, Wiktor Zuba

In computational genomics, many analyses rely on efficient storage and traversal of $k$-mers, motivating compact representations such as spectrum-preserving string sets (SPSS), which store strings whose $k$-mer spectrum matches that of the input. Existing approaches, including Unitigs, Eulertigs and Matchtigs, model this task as a path cover problem on the deBruijn graph. We extend this framework from paths to branching structures by introducing necklace covers, which combine cycles and tree-like attachments (pendants). We present a greedy algorithm that constructs a necklace cover while guaranteeing, under certain conditions, optimality in the cumulative size of the final representation. Experiments on real genomic datasets indicate that the minimum necklace cover achieves smaller representations than Eulertigs and comparable compression to the Masked Superstrings approach, while maintaining exactness of the $k$-mer spectrum.

Authors: Sajjad Hashemian

Motivated by Johnson--Lindenstrauss dimension reduction, amplitude encoding, and the view of measurements as hash-like primitives, one might hope to compress an $n$-point approximate nearest neighbor (ANN) data structure into $O(\log n)$ qubits. We rule out this possibility in a broad quantum sketch model, the dataset $P$ is encoded as an $m$-qubit state $ρ_P$, and each query is answered by an arbitrary query-dependent measurement on a fresh copy of $ρ_P$. For every approximation factor $c\ge 1$ and constant success probability $p>1/2$, we exhibit $n$-point instances in Hamming space $\{0,1\}^d$ with $d=Θ(\log n)$ for which any such sketch requires $m=Ω(n)$ qubits, via a reduction to quantum random access codes and Nayak's lower bound. These memory lower bounds coexist with potential quantum query-time gains and in candidate-scanning abstractions of hashing-based ANN, amplitude amplification yields a quadratic reduction in candidate checks, which is essentially optimal by Grover/BBBV-type bounds.

Authors: Pei Heng, Yi Sun, Jianhua Guo

The decomposition of undirected graphs simplifies complex problems by breaking them into solvable subgraphs, following the philosophy of divide and conquer. This paper investigates the relationship between atom decomposition and the maximum cardinality search (MCS) ordering in general undirected graphs. Specifically, we prove that applying a convex extension to the node numbered $1$ and its neighborhood in an MCS ordering yields an atom in the graph. Furthermore, based on the MCS ordering, we introduce a recursive algorithm for decomposing an undirected graph into its atoms. This approach closely aligns with the results of chordal graph decomposition. As a result, minimal triangulation of the graph is no longer required, and the identification of clique minimal separators is avoided. In the experimental section, we combine the proposed decomposition algorithm with two existing convex expansion methods. The results show that both combinations significantly outperform the existing algorithms in terms of efficiency.

Authors: Jakub Lemiesz, Dingqi Yang, Philippe Cudré-Mauroux

We introduce EdgeSketch, a compact graph representation for efficient analysis of massive graph streams. EdgeSketch provides unbiased estimators for key graph properties with controllable variance and supports implementing graph algorithms on the stored summary directly. It is constructed in a fully streaming manner, requiring a single pass over the edge stream, while offline analysis relies solely on the sketch. We evaluate the proposed approach on two representative applications: community detection via the Louvain method and graph reconstruction through node similarity estimation. Experiments demonstrate substantial memory savings and runtime improvements over both lossless representations and prior sketching approaches, while maintaining reliable accuracy.

Authors: Bartłomiej Bosek, Jadwiga Czyżewska, Evangelos Kipouridis, Wojciech Nadara, Michał Pilipczuk, Karol Węgrzycki, Anna Zych-Pawlewicz

We present a dynamic data structure for representing binary $n\times n$ matrices that are $d$-twin-ordered, for a~fixed parameter $d$. Our structure supports cell queries and single-cell updates both in $\Oh(\log \log n)$ expected worst case time, while using $\Oh_d(n)$ memory; here, the $\Oh_d(\cdot)$ notation

Authors: Kalina Jasińska, John Kuszmaul, Gyudong Lee

In the cup game, an adversary distributes 1 unit of water among $n$ cups every time step. The player then selects a single cup from which to remove 1 unit of water. In the bamboo trimming problem, the adversary must choose fixed rates for the cups, and the player is additionally allowed to empty the chosen cup entirely. Past work has shown that the optimal backlog in these two settings is $Θ(\log n)$ and 2 respectively. The greedy algorithm has been shown in previous work to be exactly optimal in the general cup game and asymptotically optimal in the bamboo setting. The greedy algorithm has been conjectured [16] to achieve the exactly optimal backlog of 2 in the bamboo setting as well. In this paper, we prove a lower bound of $2.076$ for the backlog of the greedy algorithm, disproving the conjecture of [16]. We also introduce a new algorithm, a hybrid greedy/Deadline-Driven, which achieves backlog $O(\log n)$ in the general cup game, and remains exactly optimal for the bamboo trimming problem and the fixed-rate cup game -- this constitutes the first algorithm that achieves asymptotically optimal performance across all three settings. Additionally, we introduce a new model, the semi-oblivious cup game, in which the player is uncertain of the exact heights of each cup. We analyze the performance of the greedy algorithm in this setting, which can be viewed as selecting an arbitrary cup within a constant multiplicative factor of the fullest cup. We prove matching upper and lower bounds showing that the greedy algorithm achieves a backlog of $Θ(n^{\frac{c-1}{c}})$ in the semi-oblivious cup game. We also establish matching upper and lower bounds of $2^{Θ(\sqrt{\log n})}$ in the semi-oblivious cup flushing game. Finally, we show that in an additive error setting, greedy is actually able to achieve backlog $Θ(\log n)$, via matching upper and lower bounds.