Theory of Computing Report

Authors: Yann Tal

We give a bounded-error quantum algorithm that, given a prime $p$, a divisor $q\mid(p-1)$, and an integer $0

Authors: Minho Cho, Andreas F. Holmsen, Attila Jung, Hong Liu

Helly, Carathéodory, and Radon numbers encode three kinds of finite certificates in a convexity space: for the emptiness of an intersection, for membership in a convex hull, and for the existence of intersecting hulls. We study exact versions of these certificates, in which a subfamily must preserve the whole intersection or a subset must preserve the whole hull. Our first main result shows that, for finite configurations in an arbitrary convexity space, five a priori different boundedness conditions are equivalent: VC-dimension, strong Helly number, strong Carathéodory number, comatching number, and strong Radon number (with the expected additive-one shift). We also obtain equivalent layered Tverberg-type decompositions and colorful consequences. The common mechanism is exposed by the bipartite incidence graph between points and a generating family. For finite spaces, the unique minimal generator yields a natural dual convexity space; we characterize double dualization and prove that the strong parameters are duality invariant. The same model gives a polynomial-size, $O(t^4)$, realization of Bukh's counterexample to the Calder-Eckhoff partition conjecture. Finally, we obtain the first Tverberg bound for separable convexity spaces that is simultaneously linear in the number of parts and polynomial in the Radon number. If an $S_3$-separable convexity space has Helly number $h$ and its halfspaces have VC-dimension $d$, then $r_t=O(dh\log h)\,t$; in particular, Radon number $r$ gives $r_t=O(r^2\log r)\,t$. The bound attains the weak-Eckhoff scale $O(rt)$ whenever the Helly number is bounded. For axis-parallel box convexity in $\mathbb{R}^k$, gives the optimal order $r_t=O(rt)$ uniformly in every dimension. This appears to be the first dimension-uniform estimate of weak-Eckhoff order for box convexity, whereas the previous direct theory was confined to dimension three.

Authors: Roman Parpalak, Denis Utkin

We describe algorithms for the exhaustive enumeration and classification of simple arrangements of $n$ pseudolines ($n$ odd) maximizing the number of triangular faces. The depth-first search enumerates reduced words for the longest permutation $w_0$ by branching only on the even-indexed generators, using pruning constraints imposed by the geometry of optimal arrangements. The approach handles both perfect arrangements with a regular triangular pattern and unavoidable deviations from it for $n \equiv 1 \pmod 6$. The output is classified into a hierarchy of equivalence classes: by commutation, by Euclidean transformations, and by projective transformations. For each projective class we recover its full symmetry group $G \subseteq S_{n+1}$ together with the orbit-stabilizer profile of its Euclidean subclasses. Completeness of the search and classification is proved: every wiring diagram is reached. We report full enumerations; e.g. for $n=27$, 85,562,064 wiring diagrams partitioned into 56,646 projective classes. For larger $n$ (up to $n=93$), where exhaustive enumeration is out of reach, we report partial (first-hit) results.

Authors: Ahmed Abdelkader, David M. Mount

The widespread use of gradient-based optimization has motivated the adaptation of various classical algorithms into differentiable solvers compatible with learning pipelines. In this paper, we investigate the enhancement of traditional geometric query problems such that the result consists of both the geometric function as well as its gradient. Specifically, we study the fundamental problem of distance queries against a set of points $P$ in $\mathbb{R}^d$, which also underlies various similarity measures for learning algorithms. The main result of this paper is a multiplicative $(1+\varepsilon)$-approximation of the Euclidean distance to $P$ which is differentiable at all points in $\mathbb{R}^d \setminus P$ with asymptotically optimal bounds on the norms of its gradient and Hessian, from a data structure with storage and query time matching state-of-the-art results for approximate nearest-neighbor searching. The approximation is realized as a regularized distance through a partition-of-unity framework, which efficiently blends multiple local approximations, over a suitably defined covering of space, into a smooth global approximation. In order to obtain the local distance approximations in a manner that facilitates blending, we develop a new approximate Voronoi diagram based on a simple point-location data structure, simplifying away both the lifting transformation and ray shooting.

Authors: Ahmed Abdelkader, David M. Mount

The efficient representation of convex bodies in multi-dimensional spaces is a fundamental problem in computational geometry. Several key developments were recently brought about using a number of constructions utilizing Macbeath regions. In this paper, we present a novel intrinsic approach for approximate membership testing, where we carry out the entire development based on structures derived from the Hilbert metric associated with a convex body $K$ in $\mathbb{R}^d$. First, we revisit the construction of economical Delone sets, deriving the size bound based on the notion of volume entropy. Second, we design a new query structure based on a simple covering by ellipsoids, where queries are answered by ray shooting. As an added bonus, the intrinsic viewpoint facilitates finger searching, where the query time can be bounded by the distance traveled in the Hilbert metric.

Authors: Alexander Schmidhuber, Matthew B. Hastings

Planted noisy $k$XOR and the strong refutation of random $k$XOR are governed by a conjectured trade-off between signal strength and time: Level $\ell$ of the Kikuchi hierarchy should achieve the smooth curve \begin{equation*} m\ \gtrsim\ ρ^{-2}n^{k/2}/\ell^{k/2-1}\ \text{clauses} \quad\Longleftrightarrow\quad \text{solvable in time }n^{O(\ell)}, \end{equation*} where $ρ$ is the bias of the planted signal or, for refutation, the target advantage. However, every spectral analysis of sparse $k$XOR to date loses polylogarithmic factors against this curve, a loss that enters the exponent of the running time. We show that a normalized variant of the Kikuchi hierarchy achieves the sharp conjectured trade-off, with no logarithmic loss, at every arity $k\ge3$. At the scale above, our algorithms achieve strong detection, weak recovery, and strong refutation; an additional cleanup step boosts weak recovery to exact recovery, and the refutation certificates yield sum-of-squares proofs of degree $O_k(\ell)$. We also prove matching lower bounds in the same model. The inference and refutation upper bounds transfer to more general planting laws and predicates. Finally, we give a quantum algorithm that achieves a quartic speedup over the classical spectral algorithms for detection and weak recovery. The proofs rest on two key ingredients: a normalization of the sparse Kikuchi matrix, and a sharp count of the closed walks in its trace expansion. We use a closely related trace-walk count to prove Feige's 2008 hypergraph Moore bound conjecture in a companion paper.

Authors: Sujoy Bhore, Timothy M. Chan, Pasin Manurangsi

We study the maximum coverage problem for geometric set systems: given a set of points, a set of geometric objects, and a number $k$, select $k$ objects maximizing the number of points inside their union. - We present a polynomial-time approximation algorithm with approximation factor strictly better than $1-1/e$ for any set system with linear 2-shallow cell complexity (or any set system that can be decomposed into a constant number of such set systems). The result also holds for the weighted maximum coverage problem, where objects have weights and we want to select objects with total weight within a given budget. The result applies to many types of geometric objects, including pseudodisks in 2D, fat axis-aligned rectangles in 2D, similar-size fat triangles in 2D, axis-aligned unit cubes in 3D. - For small $k$, we obtain a $(1-ε)$-approximation algorithm more generally for any set system with constant VC dimension, running in time exponential in $\tilde{O}(k/ε)$. This simplifies and improves Badanidiyuru, Kleinberg, and Lee's parameterized approximation scheme [SoCG'12] running in time exponential in $\tilde{O}(k^2/ε^5)$. - A continuous version of the geometric maximum coverage problem asks for $k$ objects maximizing the volume of their union. We give better approximation algorithms for this problem for certain families of objects; e.g., we obtain an EPTAS for fat convex objects in any constant dimension. - We complement our algorithms with several hardness results, e.g., APX-hardness for fat axis-aligned rectangles in 2D, $(1-1/e+ε)$-approximation hardness for axis-aligned boxes in a dimension dependent on $ε$, and a lower bound ruling out $n^{\mathop{\rm poly}(1/ε)}$-time PTASs for the continuous problem for axis-aligned boxes in 3D.

Authors: Sitan Chen, Ryan O'Donnell, Angelos Pelecanos, John Wright

In \emph{Online Shadow Tomography}, we are given copies of an unknown $d$-dimensional quantum state $ρ$, an adversary (adaptively) proposes a sequence of bounded observables $A^{(1)},\ldots,A^{(m)}$, and after each $A^{(t)}$ is given we must estimate $\Tr(A^{(t)}ρ)$ to within $\pm ε$. This is the direct quantum generalization of the classical problem of \emph{Adaptive Data Analysis}. %The ``offline'' case, in which $A^{(1)}, \ldots, A^{(m)}$ are given upfront, is also a well-studied problem. The main goal is to minimize the number of copies, $n$, required. Prior results for online Shadow Tomography were suboptimal in all three parameters $m, d, ε$, lagging behind the best known and classical rates~\cite{bassily2021algorithmic}, for which there is some evidence of optimality. In this work, we finally close this gap, giving a pair of algorithms matching the classical rates. The bound on the left is the first to achieve $o(\log^2 m)$-dependence together with $\poly(\log(d)/\eps)$; moreover, it improves all three exponents even in the \emph{Offline} Shadow Tomography setting. The bound on the right is known to be optimal among bounds independent of~$d$, and improves the best prior result by a $\sqrt{m} \log m$ factor. The key to our proof is a new framework for quantifying post-measurement damage, based on the quantum Efron--Stein decomposition.

Authors: Marco Fanizza, Ryan O'Donnell, Chirag Wadhwa

We study the sample complexity of estimating and testing fundamental unitarily invariant properties of unknown quantum states; namely, the tasks of spectrum estimation, von Neumann entropy estimation, and rank-testing. For $d$-dimensional states, and for every $γ>0$, we prove a sample complexity lower bound of $Ω(d^{2-γ})$ for spectrum estimation to constant sorted total-variation error, entropy estimation to constant additive error, and rank-testing to constant trace distance. Our hard instances are constructed from sandwiched products of Haar-random projectors, suitably normalized using a novel technique that lets us derive explicit expressions for high-order tensor moments of the resultant states. These moments can be expressed as symmetric functions of Jucys--Murphy elements of the symmetric group algebra. To show that two such mixtures are indistinguishable, we analyze the log-likelihood ratio and perform moment-matching, i.e., we set its low-order Jucys--Murphy components to zero. Indistinguishability is then obtained by bounding an $f$-divergence through the high-order components; the non-zero high-order terms and concentration of functions of Haar-random unitaries also imply separations in typical spectra, entropies, and ranks, proving all our lower bounds.

Authors: Asaf Etgar, Anna C. Gilbert, Jamie Tucker-Foltz

Given a graph $G$ labeled with positive distances on each edge, what is the fewest number of edge distances that must be modified for $G$ to become a metric? It is known that this metric repair problem is $\mathrm{NP}$-hard on general graphs, with prior work focusing on approximations and fixed-parameter tractability with respect to properties of the input distance function. In this paper, we ask what structural properties of the graph itself make metric repair tractable. On the positive side, we give pseudo-polynomial time algorithms for series-parallel graphs, and by generalization, graphs of bounded treewidth. An immediate consequence of this result is a new algorithm for the length-bounded multicut problem, with a parameterized runtime bound in terms of the treewidth of a modestly augmented graph. Surprisingly, pseudo-polynomial time turns out to be the best one can hope for: We complement our algorithm with a proof that metric repair is weakly $\mathrm{NP}$-hard even on graphs of pathwidth at most six. We also prove that planarity does not help either, as the problem remains strongly $\mathrm{NP}$-hard even on grid graphs.

Authors: Mehrad Abbaszadeh Minab, Pietro Caputo, Zongchen Chen, Mario Morellini, Alistair Sinclair

In recent years, nonlinear dynamics derived from kinetic theory have gained attention in the context of sampling configurations of spin systems such as the Ising model. We focus on nonlinear dynamics for the hard-core model, a canonical spin system with hard constraints that specifies a distribution over independent sets in a graph, weighted by their sizes. We explore two distinct types of nonlinear dynamics: the mean-field dynamics, which preserves the density (or average size) of independent sets, and the single-site dynamics, which preserves the marginal vector (i.e., the occupancy probabilities of the vertices). These dynamics are natural stochastic processes for sampling from the hard-core model with a specified density or marginal vector, respectively, both of which are canonical instances of maximum entropy distributions that have been studied in various contexts. In contrast to linear Markov chains, there is a significant lack of a fundamental theoretical framework for nonlinear dynamics. We develop foundational theoretical tools for analyzing nonlinear dynamics within the context of the hard-core model. We establish almost linear convergence of both the mean-field and single-site dynamics at sufficiently low density through novel coupling arguments. We also establish exponential decay of relative entropy for the mean-field dynamics all the way up to the critical density. Additionally, we design new algorithms for sampling from the hard-core distribution with either a specified density or a specified marginal vector. These algorithms are based on a related linear Markov chain, called the particle-system dynamics and inspired by the so-called Kac's program, that approximates the associated nonlinear dynamics. As we demonstrate in the paper, they are comparable in time complexity, but simpler to implement, than traditional approaches based on learning parameter values.

Authors: Xilin Tang, Yuqi Mai, William Kuszmaul, Alex Conway

Hash tables sit on the critical path of many systems, yet modern designs still force a trade-off between fast operations and high memory overhead. We revisit this trade-off and present Tiny Pointer Hash Tables (TPHT), a family of practical hash tables that make two ideas from theory work at system scale: compressing pointers down to a byte, and encoding keys compactly so less metadata is needed. We engineer these ideas into two complementary designs. Chained-TPHT targets maximal space savings, and is to the best of our knowledge the first simple and practical succinct hash table design, achieving a footprint less than the total data size with constant-time operations. Flattened-TPHT targets latency, organizing data to keep the common case within a single cache miss while retaining strong space efficiency. Both variants support dynamic resizing without global pauses and integrate cleanly with 64-bit keys and values. Across YCSB and microbenchmarks, TPHT advances the latency-space Pareto frontier: Chained-TPHT reaches 105.4% space efficiency, and Flattened-TPHT achieves 83.4% space efficiency with up to 89.3% higher throughput than strong baselines. Together, these results show that techniques primarily known in theory can be turned into production-ready hash tables that meaningfully reduce memory use while delivering state-of-the-art performance.

Authors: Jan Bulanek, Ravi Kumar, Raghu Meka, Jelani Nelson, Tamas Sarlos

We define the $M$-point query problem in data streams. Given a fixed matrix $M$, the goal is to maintain a vector $x$ under turnstile updates and answer each query $u$ with an estimate $\widehat{y}_u$ satisfying $|y_u-\widehat{y}_u| \leq \varepsilon \|x\|_1$, where $y=Mx$. We show that if $M$ admits a factorization $M=AB$, where $A$ and $B$ have space-efficient representations, then there is a streaming algorithm using $O(\varepsilon^{-1}\|A\|_{2\rightarrow\infty}\|B\|_{1\rightarrow 1}+(\varepsilon^{-1}\|A\|_{\infty\rightarrow\infty}\|B\|_{1\rightarrow 1})^{2/3})$ words of memory. An important special case is the lower-triangular all-ones matrix, which corresponds to the quantiles problem with additive error $\pm \varepsilon n$, where $n$ is the database size. Our framework generalizes the dyadic approach of Cormode and Muthukrishnan (J. Algorithms, 2005) for turnstile quantiles, and simplifies and improves the analysis of the state-of-the-art dyadic CountSketch algorithms of Wang et al. (SIGMOD, 2013) and Luo et al. (VLDB, 2016). Our approach is also related to the matrix mechanism of Li et al. (VLDB J., 2015) in differential privacy: given a database $x\in\mathbb{R}^U$ and a matrix $M$, the mechanism outputs a private approximation to $Mx$, with the privacy-error tradeoff governed by a matrix factorization norm of $M$. We also improve the prior lower bound for quantiles with deletions, showing a memory lower bound of $Ω(\varepsilon^{-1}\log U)$ words. We also show any factorization has $\|A\|_{2\rightarrow\infty}\|B\|_{1\rightarrow 1} = Ω((\log^{1.5} U) / \log\log U)$. This lower bound is new, and shows that for quantiles, the dyadic CountSketch is nearly optimal amongst factorization-based approaches.

I was watching a Jeopardy from 2004 (The Game Show Channel is rerunning Ken Jennings streak) and the following question raises a good question.

The contestants where Ken, Jerry, Jennifer.

In Double Jeopardy there was a category  Biblical Name The Same.

The clue was three last names (e.g., Driver, Sandler, West) and the correct response is a biblical name that is the first name of people with that last name (Adam: Adam Driver, Adam Sandler, Adam West).

What happened with Biblical Name The Same for 1200 shows an issue with the question.

Clue: Stewart, Graham, Grimes.

Jerry said  James. This was ruled incorrect.

Ken said Martha. This is correct.

Why is Martha Correct:

Martha Stewart is a well known TV personality focusing on home and hospitality.

Martha Graham was an American modern dancer, teacher, and choreographer (she died in 1991).

Martha Grimes is an American writer of detective fiction.

Frankly, the only one I had heard of was Martha Stewart.

But later they decided Jerry was right and gave him the points (Ken kept his points).  Here was Jerry's argument:

James Stewart was a well known  actor (died in 1997).

James Graham- the show said he was a British General in the 17th Century. I (Bill, not Jerry) looked up James Graham on Wikipedia- there are a lot of them. Four were under the category Military.  Of those, two were British. Neither was a General. One lived 1649-1730 so it may be him.

James Grimes-the show said he was a Senator involved with the impeachment of Andrew Johnson.  I (Bill) looked it up- Grimes was a Republican and it was his party that was trying to impeach, but he (and six other Republicans) broke rank and voted for acquittal. He and the others were bothered that the process had been manipulated. There were rumors they were bribed with patronage jobs or cash though I could not tell if this was true.

The category is problematic.

It is implicit that the three people have to be famous.

This raises two questions and a challenge

Two Questions: What is fame?  How do you measure it? 

Challenges: Let x,y \(\ge\) 2. 

 Find x  last names L1,...Lx  such that there are y first names F1,...,Fy

with F1-L1, F1-L2,...,F1-Lx famous AND

        F2-L1, F2-L2,..., F2-Lx famous AND

DOT DOT DOT

        Fy-L1, Fy-L2,...,Fy-Lx famous.

For the example above x=3 and y=2. You either try the easier case x=2, y=2, or a harder case like x=3, y=3. 

By gasarch

Reports that LLMs have killed the Erdős unit distance problem turn out to be greatly exaggerated. There is still plenty not yet understood about the problem.

The problem asks, for \(n\) points in the Euclidean plane, how many pairs can be at unit distance from each other? When Paul Erdős posed the problem in 1946, he observed that the graph of unit distances cannot contain a subgraph of the form \(K_{2,3}\), a complete bipartite subgraph with two vertices on one side and three on the other. One way to see this is to draw unit circles through the two vertices on one side of a supposed \(K_{2,3}\) subgraph. These cross each other at most twice, and their two crossing points are the only points that can be vertices on the other side of the subgraph. Through reasoning later generalized as the Kővári–Sós–Turán theorem, Erdős observed that this forbidden subgraph implies an \(O(n^{3/2})\) upper bound on the number of unit distances. More generally, the Kővári–Sós–Turán theorem implies that when \(K_{a,b}\) is forbidden from an \(n\)-vertex graph, the number of edges in the graph is \(O(n^{2-1/\min(a,b)})\). Subsequent researchers used different reasoning to reduce Erdős’s upper bound to \(O(n^{4/3})\).

Erdős also found a set of points with a slightly superlinear number of unit distances, \(n^{1+\omega(1/\log\log n)}\), by scaling a square grid with \(n\) points in it by a factor of \(1/r\), where \(r\) is chosen somewhat smaller than \(\sqrt n\) (so that a unit distance fits comfortably into the scaled grid) but so that \(r\) has many prime factors congruent to \(1\) mod \(4\). This leads to the existence of many integer right triangles with side length \(r\) and many copies of the hypotenuses of these triangles in the grid. For instance the image below shows many unit-length diagonal segments in an \(8\times 8\) grid scaled by \(r=5\), based on a \(3\)–\(4\)–\(5\) right triangle; the axis-parallel unit-length segments are not shown. Recent combinations of LLM and human effort have improved this lower bound to \(\Omega(n^{1.0358})\) (unverified, as of posting), disproving Erdős’s conjecture that the upper bound should be \(n^{1+o(1)}\). But there is still a lot of room between the lower bound exponent of \(1.0358\) and the upper bound exponent of \(4/3\).

What about higher dimensions? In three dimensions there is another gap between a lower bound exponent of \(4/3\) and an upper bound exponent of \(295/197\approx 1.4975\). But there it stops. Already in four dimensions one can obtain arbitrarily large sets of points with dense complete bipartite graphs of unit distances, for instance by placing \(n/2\) points each on two perpendicular circles of radii \(3/5\) and \(4/5\) (Pythagoras again!) in the \(xy\)- and \(zw\)-planes.

Or does it stop? One obvious feature of Erdős’s scaled grid example is that it contains many collinear points. It is not obvious why this should be helpful for creating many unit distances, because each point can only have two unit-distance neighbors on each line. The new improved examples for the unit distance problem take the form of projections of higher-dimensional lattices into the plane (with carefully chosen algebraic properties generalizing the existence of many integer right triangles) and these too have many collinear points. This naturally raises the question: when points in the plane have no lines through three or more points, how does this forbidden pattern affect the number of unit distances that these restricted point sets can have? It’s still nonlinear: one can project any hypercube into the plane so that all its edges have unit distances, producing for a suitable projection non-collinear point sets with \(\Omega(n\log n)\) unit distances. I don’t know of any examples with asymptotically larger numbers than the hypercube, but perhaps I’m missing some known constructions.

In \(d\)-dimensional space, the analogous restriction is that no \(d+1\) points lie on a hyperplane. The common neighbors of any two points \(p\) and \(q\) do all lie on a hyperplane (the hyperplane that perpendicularly bisects segment \(pq\)) so this restriction causes us to forbid the subgraph \(K_{2,d+1}\). (We can rephrase this idea as the statement that, for any system of unit spheres whose tangencies contain a biclique \(K_{a,b}\) with \(\min(a,b)\ge 2\), the centers of the spheres on each side of the biclique must be coplanar; this is analogous to a statement on bicliques of non-unit spheres with \(\min(a,b)\ge 3\) from my recent paper on sphere tangencies and unit distances, but much easier.) By the Kővári–Sós–Turán theorem, forbidding the subgraph \(K_{2,d+1}\) implies that, for a \(d\)-dimensional point set with no \(d+1\) points on a hyperplane, there can be at most \(O(n^{3/2})\) unit distances.

Can a matching \(\Omega(n^{3/2})\) lower bound be achieved, in high enough dimensions, or alternatively, is there some limiting exponent \(c<3/2\) (perhaps even \(c=1\)) so that point sets with no \(d+1\) points on a hyperplane have \(n^{c+o(1)}\) unit distances? I don’t know.

(Discuss on Mastodon)

By David Eppstein

A branching program is a labeled directed graph that, on each input $x$, induces an $s$-$t$ connectivity instance. Nondeterministic branching programs (NBPs) accept an input if there exists an accepting path, whereas parity branching programs ($\oplus$BPs) accept if the number of accepting paths is odd. Wigderson (Structure in Complexity Theory Conference, 1994) showed that NBPs can be simulated by $\oplus$BPs with the aid of nonuniform advice, establishing \[ NL/poly\subseteq\oplus L/poly. \] In this short note, we observe that the recent breakthrough of Chatterjee, Ghosh, Gurjar, Raj, and Thierauf, placing bipartite perfect matching in deterministic NC, yields a uniform version of Wigderson's theorem. Specifically, we show that every nondeterministic branching program can be transformed, in deterministic logspace, into an equivalent polynomial-size parity branching program. More generally, for every fixed prime $p$, every nondeterministic branching program admits a logspace-uniform simulation by a polynomial-size mod-$p$ branching program. In complexity-theoretic terms, this establishes $NL\subseteq\oplus L$ and, more generally, $NL\subseteq \text{Mod}pL$ for every fixed prime $p$.

Saturday afternoon, July 25, was quite magical for me: all three beautiful talks were closely related to my interests and to my own work. Here is a brief personal description of the lectures, with links to the slides and papers, followed by a more detailed account of each talk.

Jinyoung Park gave a beautiful talk entitled “Thresholds,” concerning an array of conjectures about the location of thresholds for monotone properties and some of their applications. She concentrated on three conjectures: the Kahn–Kalai conjecture, also known as the expectation-threshold conjecture; the second Kahn–Kalai conjecture; and Talagrand’s discrete convexity conjecture. Here are the links to the proceedings paper and the slides.

Tom Braden and Nicholas Proudfoot gave a beautiful talk entitled “Intersection Cohomology Without Spaces,” devoted to a major theme in algebraic combinatorics: geometric structures can survive, and remain powerful, even in settings where the geometry itself does not exist. They discussed three examples: Kazhdan–Lusztig polynomials for Coxeter groups, toric -polynomials for polytopes, and Kazhdan–Lusztig–Stanley polynomials for matroids. Here are the links to the proceedings paper and to the slides.

Raghu Meka gave a beautiful talk entitled “Structure vs Randomness Redux.” The talk focused mainly on the new bounds of Meka and Zander Kelley for the density of sets of integers containing no three-term arithmetic progression. In my view, this is among the most important mathematical results of the past few years. The method relies on a new version of the “structure versus randomness” paradigm, and it has led to important progress in both additive combinatorics and theoretical computer science. Here are the links to the proceedings paper and the slides.

Breaking news

On another matter: OpenAI reported today on the solution of ten major mathematical problems.

Some personal comments

1. I wrote about the Kahn–Kalai conjecture in several earlier posts. (In my lectures and posts, I was often imprecise about the distinction between the first and second conjectures.) Although both Jeff and I were skeptical about the conjecture, in our paper we proposed a program for proving it based on strong inverse forms of discrete isoperimetric inequalities. The central inverse conjecture, Conjecture 6(a) in our paper, is still open, although some stronger versions (6(b) and 6(c)) turned out to be false. Another part of the program, Conjecture 7, was also refuted. This was the subject of our first AI+Polymath project, in which the counterexample was found with the help of AI; see this post.
2. Of the three topics discussed by Tom and Nicholas, the one I have studied most closely is the second: toric -vectors of polytopes. Beyond the major achievement of extending the theory from rational polytopes to arbitrary polytopes, an important remaining challenge is to extend it further to strongly regular CW-spheres—that is, regular CW-spheres in which the intersection of any two cells is itself a cell. Karim Adiprasito’s solution of the -conjecture for triangulated spheres—see this post and this one—may offer hope in this direction. Another important problem is to understand the combinatorial consequences of the results arising from algebraic geometry, whether “with spaces” or “without spaces.” See also this post.
3. I have followed progress on Roth’s theorem and Szemerédi’s theorem for many years, including here on the blog. (I reported on the Kelley-Meka breakthrough in this 2023 post, and see, for example, also  this 2020 post; this 2010 post; this 2009 post; , and this 2016 post.) From time to time, I even tried to work on these problems myself.
4. I have many fond memories connected with the mathematics of these three lectures, with the speakers, and with many of the other mathematicians involved.

Let me move now to a more detailed description of the three talks.

With Jinyoung Park and Hari Bercovici

Jinyoung Park: Thresholds

Jinyoung Park’s lecture, simply titled “Thresholds,” was organized around the question: What drives thresholds? Let be a finite set and let be the random subset obtained by choosing every element independently with probability . For an increasing family , its threshold is defined by . A basic lower bound comes from the first-moment method. We call -small if it can be covered by simple witnesses whose total expected contribution satisfies , and we let be the largest such . Park discussed three fundamental questions concerning the relation between this simple expectation bound and the actual threshold.

The first question was the Kahn–Kalai conjecture, which asserted that the first-moment bound always determines the threshold up to a logarithmic factor. In its strengthened form, proved by Park and Huy Tuan Pham,

where is the size of the largest minimal member of . Earlier, Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Park had proved Talagrand’s fractional version, replacing ordinary covers by fractional covers. The dual language of spread measures turned out to be particularly powerful: once one constructs a probability distribution on the desired combinatorial structures for which no fixed set of elements occurs too often, the threshold theorem can be applied. This circle of ideas gives remarkably short routes to the correct threshold orders for perfect hypergraph matchings, Hamiltonian cycles, bounded-degree spanning trees, and several other difficult problems. The logarithmic factor cannot in general be removed, as illustrated by coupon-collector phenomena.

The second Kahn–Kalai conjecture is more concrete and remains open. Given a graph , let be the smallest for which the expected number of copies in of every subgraph is at least . Clearly , and the conjecture asserts that

where is the number of vertices of . This is stronger than the general theorem because it asks us to use only the obvious subgraph witnesses, rather than arbitrary and possibly nonsymmetric covers. Recent work of Quentin Dubroff, Jeff Kahn, and Park proves the bound with an additional factor , and proves the conjectured bound itself in the sparse regime . Thus the remaining question is whether the complicated abstract witnesses defining can always be replaced, at constant cost, by the natural subgraphs of .

Park’s third theme was Talagrand’s discrete convexity conjecture. For a decreasing family , let

and let .

The conjecture says that there are universal constants and such that, whenever has sufficiently large -measure, the exceptional family is -small. In words, boundedly many unions of members of a large decreasing family should cover almost the entire discrete cube, apart from an exceptional set whose smallness has an explicit first-moment explanation. The Park–Pham theorem gives a related statement with but with a necessary logarithmic loss in ; Talagrand’s conjecture predicts that allowing a bounded number of unions eliminates this loss. Talagrand described this as his “lifetime favorite problem,” and it remains open.

Tom Braden, Nicholas Proudfoot, with Pierre Deligne and George Lusztig

Tom Braden and Nicholas Proudfoot: Intersection Cohomology Without Spaces.

The second lecture, by Tom Braden and Nicholas Proudfoot, was entitled “Intersection Cohomology Without Spaces.” Ordinary cohomology behaves beautifully for smooth projective varieties, satisfying Poincaré duality, the hard Lefschetz theorem, and the Hodge–Riemann relations. For singular varieties, ordinary cohomology may lose these properties, but intersection cohomology restores them. Besides the global groups one has local intersection cohomology groups  , which measure the singularity of near . Their graded dimensions often assemble into polynomials of central importance in combinatorics and representation theory.

Braden and Proudfoot presented three parallel examples. For Coxeter groups one obtains the Kazhdan–Lusztig polynomials; for convex polytopes one obtains Stanley’s -polynomials; and for matroids one obtains the Kazhdan–Lusztig polynomials of matroids. All three belong to Stanley’s general theory of Kazhdan–Lusztig–Stanley, or KLS, polynomials associated with a ranked poset and a suitable collection of polynomials called a -kernel. The KLS-polynomials are defined recursively, together with the crucial degree condition

From their recursive definitions it is far from evident that their coefficients should be nonnegative. Geometry explains this by identifying them with Poincaré polynomials

of appropriate local intersection cohomology groups.

The relevant geometric spaces exist only in special cases. For Weyl groups they are Schubert varieties in flag varieties; for rational polytopes they are toric varieties; and for realizable matroids they are arrangement Schubert varieties. But the combinatorial polynomials make sense for arbitrary Coxeter groups, nonrational polytopes, and nonrealizable matroids, where no corresponding algebraic variety exists. The remarkable development described in the lecture is that one can nevertheless construct the intersection cohomology groups themselves: by Soergel bimodules or moment-graph sheaves for Coxeter groups, by intersection cohomology sheaves on fans for polytopes, and by intersection cohomology modules for matroids. Thus the title “intersection cohomology without spaces” is quite literal: the algebraic and combinatorial shadows of the geometric theory continue to exist even after the underlying geometric space has disappeared.

The common framework uses sheaves of graded modules on finite posets. The strata of a variety are replaced by the elements of the poset, and the intersection cohomology sheaf is constructed inductively: after the data have been defined above an element , the stalk at is obtained as a minimal free module mapping onto the already known boundary data. This elementary-looking construction is only the beginning. The deep part is proving that the resulting graded vector spaces have the required dimensions, and this demands combinatorial analogues of hard Lefschetz and the Hodge–Riemann relations. These theories give much more than coefficientwise nonnegativity. For example, intersection cohomology of matroids was a central ingredient in the proof of the Dowling–Wilson top-heavy conjecture: if is the lattice of flats of a rank- matroid, then

The lecture offered a striking illustration of a major theme in modern combinatorics: geometric structures can survive, and remain powerful, even in settings where the geometry itself does not exist.

Remark (for the experts): The construction of the IH modules of a matroid that Tom and Nicholas outlined in the final slides (especially 23 and 24) is not the one that appears in the paper “Singular Hodge theory for combinatorial geometries”. (The resulting modules are the same for the two constructions.) They are currently finishing the papers with the new construction, to be posted soon.

Raghu Meka Raghu Meka: Structure vs Randomness Redux.

Raghu Meka’s lecture was entitled “Structure vs Randomness Redux.” The classical structure-versus-randomness paradigm says that a complicated mathematical object can either be decomposed into structured pieces or shown to behave like a random object. Meka described a new and remarkably successful version of this paradigm, developed in works with Amir Abboud, Nick Fischer, Zander Kelley, and Shachar Lovett. Its central principle is

Roughly speaking, an object is spread if its density does not increase substantially when we restrict it to any large natural substructure—an affine subspace or a Bohr set for additive problems, and a rectangle for matrices. A spread object need not itself look random. The surprising assertion is that after combining two spread objects, by convolution or matrix multiplication, the result becomes close to uniform.

The first application was the classical problem of three-term arithmetic progressions. How large can a set be if it contains no distinct satisfying

Behrend’s celebrated construction gives progression-free sets of density . After a long sequence of results beginning with Roth’s theorem, the best upper bounds remained only polylogarithmic in . Kelley and Meka made a striking jump to the stretched-exponential bound

for some absolute constant . The proof first passes to finite vector spaces. There, either has increased density on a low-codimensional affine subspace, or is spread. In the latter case its normalized convolution satisfies, schematically,

and this mixing forces many solutions to . Thus one obtains a particularly clean density-increment argument: either we already have many progressions, or we move to a smaller ambient space where the set is denser.

A key ingredient in this theory is a new decoupling inequality. The quantities one wants to estimate often involve products such as

in which the factors are dependent because they share variables. Decoupling replaces such an expression by related expressions involving more independent copies of the variables, where analytic estimates are much easier to apply. Two further ideas are essential. Spectral positivity converts unexpectedly small values into comparable upward deviations, which can drive a density increment; and sifting uses dependent sampling to locate the substructure on which this increased density occurs. These tools make the slogan “spreadness implies mixing” applicable far beyond ordinary additive convolution.

The final application concerned finding triangles and Boolean matrix multiplication. For a tripartite graph with adjacency functions , , and , the normalized number of triangles is

Abboud, Fischer, Kelley, Lovett, and Meka proved a new spread regularity lemma: every graph can be decomposed algorithmically into a controlled number of pieces, each of which is either sparse or spread. Sparse pieces can be handled directly, while on spread pieces the product of the relevant adjacency matrices mixes, making triangle detection easy. This leads to a combinatorial algorithm for Boolean matrix multiplication, and hence for triangle detection, with running time

a super-polylogarithmic improvement over the earlier combinatorial algorithms. The broader message of Meka’s lecture was that this new version of structure versus randomness provides a common explanation for breakthroughs in additive combinatorics, communication complexity, and fast algorithms.

 

By Gil Kalai

We study pseudorandom bit generators for Boolean linear sums modulo a fixed integer $M$. A distribution $X\in\{0,1\}^n$ $\varepsilon$-fools these tests if, for every $a\in\mathbb{Z}_M^n$, the distribution of \[ \sum_{i=1}^n a_iX_i \pmod M \] is $\varepsilon$-close in statistical distance to the corresponding distribution under independent uniform bits. Lovett, Reingold, Trevisan, and Vadhan constructed generators with optimal seed length for every fixed prime-power modulus. We extend this result to every fixed modulus of the form \[ M=2^{t}\cdot p^{k}, \] where $t,k\ge 0$ and $p$ an odd prime. Specifically, we give an explicit generator with seed length \[ O_M\!\left(\log n+\log\frac{1}{\varepsilon}\right), \] which is optimal up to the constant depending on $M$. Our main contribution is a modulus-doubling reduction that transforms any generator fooling Boolean linear sums modulo $m$ into one fooling such sums modulo $2m$, while preserving the optimal asymptotic seed length.

• ACM considers allowing LLMs to read its digital library (\(\mathbb{M}\)) and requests feedback on this choice.

• Daedalus’ labyrinth (\(\mathbb{M}\)), a puzzle game dual to loopy/slitherlink.

• Voronoi go (\(\mathbb{M}\)), a variant of go where you can play anywhere on the board (not just intersections).

• Human mathematicians are being outcounterexampled (\(\mathbb{M}\)). Kevin Buzzard of the Xena Lean formalization project on recent counterexamples to the unit distance problem and Jacobian conjecture.

• 3-boundary surfaces for 3-component links (\(\mathbb{M}\)) with crochet, 3d-printed, and vector graphics illustrations.

• Innovations in Graph Theory added to DOAJ (\(\mathbb{M}\)).

• zbMATH digitizes 50 years of its old reviews (\(\mathbb{M}\)).

• Three new Wikipedia articles about mathematics books (\(\mathbb{M}\)), posted by Samuel Adrian Antz: Characteristic Classes (1974) by John Milnor and Jim Stasheff, Instantons and Four-Manifolds (1984) by Dan Freed and Karen Uhlenbeck, and The Geometry of Four-Manifolds (1990) by Simon Donaldson and Peter Kronheimer.

• AI in scientific publishing: Slower, worse, and more expensive (\(\mathbb{M}\), via). H. Holden Thorp notes that the rapid increase in AI-generated research is increasing rather than decreasing the need for human effort, in checking the research, and likens the resulting effects on human workers to those in the industrial revolution’s shift from craftspeople to factory workers.

• The existence of designs (\(\mathbb{M}\)), posted to arXiv in 2014 by Peeter Keevash, has finally been accepted for publication in the Annals of Mathematics, 12.5 years later.

• Three recent algorithms preprints on arXiv make some strong and interesting claims (\(\mathbb{M}\)):

  • “Bellman–Ford in almost-linear time”, by Hair, Li, Li, and Zhang, arXiv:2607.19346, computes single-source shortest paths in a directed graph with real weights, allowed to be negative but with no negative cycles, in time \(O(m^{1+o(1)})\), building on recent subquadratic breakthroughs by overlapping authors.

  • “Splay trees are almost dynamically optimal”, by Chmel, Haeupler, Hladík, Koucký, Roeyskoe, Rozhoň, Sladký, and Tarjan, arXiv:2607.18498, proves a competitive ratio of \(O(\log\log n(\log\log\log n)^3)\), the first nontrivial competitiveness for splay trees. Tango trees have a slightly better proven bound but unlike splay trees cannot be \(O(1)\)-competitive.

  • “Shortest paths with linear edge weights”, by Chillara, Gajjar, and Raja, arXiv:2607.21055, considers shortest -paths in a directed graph whose weights vary linearly as a function of one or more parameters. Different parameter settings give different paths, but how many? The answer was known to be \(n^{\Theta(\log n)}\) for a single parameter, with weaker bounds for more. The new preprint proves a bound of the same form for any fixed number of parameters.

  You might have thought that such old and well-established topics in algorithms research as shortest paths and balanced binary search trees would be very stable, but instead things are still changing rapidly.

• Wikimedia refuses to recognize a union for its employees (\(\mathbb{M}\)) after a supermajority of workers signed union cards requesting it.

• A long thread about variants of Kőnig’s infinity lemma in relation to computability theory.

• On using computational hardness to resolve a mathematical conjecture (\(\mathbb{M}\)). Noam Zeilberger points to “A system of interaction and structure III: The complexity of BV and pomset logic” (Lê Thành Dũng Nguyên and Lutz Straßburger, doi:10.46298/lmcs-19(4:25)2023) where an incompatibility of complexity classes for provability in two conjecturally-equal logics led to a counterexample to their equality.

• I don’t know why it took me so long to realize it (\(\mathbb{M}\)), but my phone’s HP 16C programmer’s calculator app turns out to be surprisingly useful for mixing hex-coded html/svg colors.

By David Eppstein

Authors: Péter Madarasi

The Kemeny rule aggregates rankings by minimizing their total Kendall-tau distance from an aggregate order. We prove that Kemeny Score is NP-complete for exactly three unweighted rankings, even when every candidate pair is split $2$-to-$1$. On the same profiles, the winner, unique-winner, and possible- and necessary-precedence problems are $Θ_2^p$-complete, while recognizing a Kemeny-optimal or uniquely Kemeny-optimal aggregate is coNP-complete. The hard instances induce tournaments of majority dimension exactly $3$. The reduction also determines the exact maximum-cut value from the optimal Kemeny score and recovers a maximum cut from any Kemeny-optimal aggregate. For every fixed $q\geq3$ and $\lceil q/2\rceil\leq s\leq q$, minimum pairwise support $s$ yields a sharp dichotomy: the score problem is NP-complete, the winner and precedence problems are $Θ_2^p$-complete, and the recognition problems are coNP-complete when $3s\leq2q$; for $3s>2q$, the majority tournament is transitive and its unique topological order is the unique Kemeny-optimal aggregate. Exact support $s$ suffices in the hard case when $s>q/2$, and supports in ${s,s+1}$ suffice when $s=q/2$. These results give complete fixed-profile-size classifications and transfer to Slater orders, permutation medians, and maximum-likelihood central rankings in the Mallows model. Finally, a six-copy construction proves NP-completeness of both Kemeny Score and Kendall--Tau Center for three pairwise-equidistant rankings that still split every pair $2$-to-$1$. For $N$ output candidates, their common distance is $\frac23\binom N2$, the largest possible for an equidistant triple. The construction gives affine formulas for both optimal values, characterizes all Kemeny-optimal output orders, and shows that the output has a unique Kemeny-optimal order and a unique center exactly when the input has a unique Kemeny-optimal order.

Authors: Pasin Manurangsi

We study the complexity of computing the Threshold dimension of a hypothesis class and its variant, the Extended threshold dimension. For the latter, we prove that it is both NP-hard and co-NP-hard, which (partially) answers an open question of Dmitriev et al. (SODA 2026). Furthermore, by relating the problem to a variant of Maximum Balanced Biclique, we prove strong hardness of approximation for both dimensions, including in the parameterized setting. As an intermediate result, we also prove hardness (of approximation) results for computing the ladder index and the semi-ladder index (Fabianski et al., STACS 2019), which have recently been used in the design of fixed-parameter tractable algorithms.

Authors: Tianhang Lu, Runtian Ren, Shengcai Liu, Ke Tang

This paper studies learning-augmented and randomized online aggregation with delays on a line metric. We consider advice given as online suggested service lengths, and evaluate the algorithms in terms of robustness and consistency. For each $λ\in (0,1]$, we first propose a deterministic learning-augmented \textsc{Balance} algorithm that is $(4/λ+1/λ^2)$-robust and $(4+λ)$-consistent. We also propose a randomized algorithm for the problem in the classical adversarial model, which is $(e+1)$-competitive against an oblivious adversary, improving over the deterministic $5$-competitive \textsc{Balance} benchmark~\cite{bienkowski2013chain}. Notably, this competitive ratio is even lower than the lower bound of $4$ for deterministic online algorithms. Moreover, we establish a lower bound of $e$ on the competitive ratio of randomized online algorithms, improving the previous lower bound of $e/(e-1)$. Besides, we combine the two ideas and obtain a randomized learning-augmented algorithm that is $(e/λ+1/λ^2)$-robust and $(e+λ)$-consistent. Finally, we conduct numerical experiments to complement our theoretical analysis and evaluate the empirical performance of our algorithms.

Authors: Mahendra Kumar R, Renjith P, Aadhavan S, Sadagopan N

A connected graph G is said to be a bisplit graph if the vertex set of G can be partitioned into a stable set and a complete bipartite graph. We establish the following dichotomy with chordality being the parameter; for chordal bisplit graphs, Hamiltonian cycle (HCYCLE) and Hamiltonian path (HPATH) problems are polynomial-time solvable, and for chordal bipartite bisplit graphs, HCYCLE (HPATH) is NP-complete. We further strengthen the result of [1] and show that HCYCLE (HPATH) is polynomial-time solvable on P5-free chordal bipartite graphs (bipartite chain graphs) and NP-complete on P10-free chordal bipartite graphs. By using our polynomial results on HCYCLE (HPATH) as a framework, we solve many variants and generalizations of HCYCLE (HPATH), which are also reported in this paper.

Authors: Jesús Gacías Franco

By examining the relationship between the support function of convex geometry and the Euler Characteristic Transform (ECT) of topological data analysis, we develop new tools and suggest variations on some common ECT pipelines. Specifically, we put forward new definitions of ECT-induced pseudodistances, which have the advantage of being invariant under common euclidean isometries and require no cutoff parameter to compare shapes with distinct Euler characteristic. These definitions rely on a generalization of the convex geometric concept of the Steiner point, which we define in general as a distinguished point given by the ECT. We also show how convex geometry provides a path to recover interesting geometric information of a flat shape from its ECT, namely, its perimeter, for which we give an explicit formula. By building on these concepts and leveraging persistent homology, we define Steiner barcodes as an isometry invariant feature of shapes, as well as homological variants of the support function and Steiner point. Finally, we put these constructions to the test in shape classification tasks, providing lightweight features for aligned and misaligned datasets.

Authors: Markus Wallinger, Oscar Navarro, Stephen G. Kobourov

Trees arise in many applications and computing nice tree layouts is a classical problem in information visualization. In many practical settings, vertices need to be represented as rectangles with a given width and height rather than as points. When an order over the children of each vertex is given, polynomial-time algorithms are known that produce drawings adhering to various drawing conventions. However, in many applications, the order of children carries no semantic meaning, and choosing it well can significantly reduce the drawing's width. In this paper, we study the problem \textsc{Min-Width Tree Drawing with Reordering} (\textsc{MWD}): given a rooted tree whose vertices have prescribed widths, find a sibling order at each internal vertex that minimizes the width of the resulting layered drawing. We show that the problem is \textsf{NP}-complete, even on binary trees with unit-width vertices. We present a mixed integer linear program that solves \textsc{MWD} exactly on moderately sized instances, and a heuristic that is fast and delivers good results in practice. We evaluate both approaches against a baseline on synthetic and real-world datasets, where reordering reduces drawing width by a median of $\approx20\%$ and by up to $\approx55\%$ on individual instances. The heuristic computes its layouts in under a second and, when the MILP proves optimality, it stays within $25\%$ of the optimal width in three-quarters of all instances.

Authors: Tongyang Li, Fengning Ou, Xinzhao Wang, Penghui Yao, Pei Yuan, Shengyu Zhang

Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM). We initiate the study of the $T$ count of sparse QROM, in which only $s$ of the $2^n$ addresses store nonzero data. We prove asymptotically optimal $T$-count bounds $Θ(\sqrt{sm} + \sqrt{sn})$ with square-root dependence on the support size $s$ and message length $m$. Our upper bounds use a multilevel hashing scheme, while our lower bounds reduce sparse QROM to state preparation and use counting arguments for adaptive Clifford+$T$ circuits. The lower bounds thus hold even when mid-circuit measurements and classically controlled operations are allowed. As applications, we obtain matching $T$-count bounds $Θ(\sqrt{sn} + \sqrt{s\log(1/\varepsilon)} + \log(1/\varepsilon))$ for $s$-sparse state preparation and $Θ( \sqrt{2^n sn} + \sqrt{2^n s\log(s/\varepsilon_{\mathrm{BE}})} + \log(s/\varepsilon_{\mathrm{BE}}))$ for block encoding of $s$-sparse matrices, where $\varepsilon$ and $\varepsilon_{\mathrm{BE}}$ are the precision of state preparation and block encoding, respectively.

Authors: Robert Ganian, Manolis Vasilakis, Simon Wietheger

Instance selection is a vital technique for mitigating the computational bottlenecks of nearest-neighbor classification in large-scale supervised clustering. A classical theoretical formulation of this objective is the Minimum Consistent Subset (MCS) problem. While recent research has explored its complexity on unweighted graphs to uncover structural boundaries of tractability, arbitrary metric spaces are much more accurately modeled by (edge-)weighted graphs. In this paper, we develop a comprehensive fine-grained complexity map of MCS on both unweighted and weighted graphs. As our main result, we introduce a $3^{c \cdot(\mathrm{tw}+1)}\cdot n^{\mathrm{tw}+\mathcal{O}(1)}$ algorithm for $n$-vertex $c$-colored MCS instances on weighted graphs of treewidth $\mathrm{tw}$, substantially improving upon the previous state-of-the-art algorithm for unweighted MCS on trees both in terms of generality and running time. We complement this positive result with a series of lower bounds that rule out asymptotic improvements to the running time for both weighted and unweighted graphs under the Exponential Time Hypothesis (ETH). Moreover, we improve the recent slightly superexponential vertex-cover based algorithm for unweighted MCS (AAAI 2026) to a single-exponential one, and rule out further improvements to subexponential running times under the ETH. Together, our results strictly delineate the algorithmic boundaries of consistent subset selection across diverse metric structures.

Authors: Shuichi Hirahara, Naoto Ohsaka

In the Maxmin $q$-CSP Reconfiguration problem, given a satisfiable $q$-CSP instance and a pair of its satisfying assignments, we are asked to transform one assignment into the other by repeatedly changing the value assigned to a single variable. The objective is to find such a transformation that maximizes the minimum fraction of satisfied constraints along the transformation. In this paper, we prove that for any $q \geq 2$ and $\varepsilon > 0$, Maxmin $q$-CSP Reconfiguration is $\mathsf{PSPACE}$-hard to approximate within a factor of $\frac{1}{2^{q-1}}+\varepsilon$. To complement this hardness result, we prove that a $\bigl(\frac{1}{2^{q-1}}-\varepsilon\bigr)$-factor approximation for Maxmin $q$-CSP Reconfiguration is in $\mathsf{NP}$ in the perfect completeness case. These results establish the optimal $\mathsf{PSPACE}$-hardness of approximating Maxmin $q$-CSP Reconfiguration for every $q \geq 2$ under $\mathsf{NP} \neq \mathsf{PSPACE}$.

Authors: Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray

Many geometric stabbing problems admit natural covering LPs in which each constraint is a union of consecutive traces on ordered candidate sets. We prove a transfer theorem showing that every fixed finite, bounded-arity integrality-gap instance of this form yields a matching hardness ratio under the Unique Games Conjecture. Using the strict-CSP framework of Kumar, Manokaran, Tulsiani, and Vishnoi [SODA 2011], we construct the required connected local distributions by randomized rounding and a full-support perturbation. Given a fractional vector $x$ on a block, the rounding selects candidate $i$ with marginal probability $x_i$ and hits each consecutive trace $T$ with probability $\min\{1,x(T)\}$. We obtain three tight UGC thresholds. First, for every fixed $d\ge 2$, stabbing arbitrary-size axis-parallel $d$-cubes with coordinate hyperplanes has threshold $d$. For $d=2$, the hardness holds for arbitrary-size squares and establishes threshold $2$ for rectangle and square stabbing, matching the $2$-approximation of Gaur, Ibaraki, and Krishnamurti [ESA 2000]. Second, stabbing horizontal segments with horizontal and vertical lines has threshold $e/(e-1)$, matching the $e/(e-1)$-approximation of Kovaleva and Spieksma [ESA 2004]. Third, separated $d$-interval transversal has threshold $d$ for every fixed $d\ge 2$, closing under UGC the gap left by the $d$-approximation of Ben-David, Grant, Ma, and Sharpe [CCCG 2012].

Authors: Jincheng Guan, Shuai Shao, Ke Shi

The weighted Eulerian orientation counting problem ($\#\mathrm{EO}$) plays a key role in the complexity classification program for Holant problems. A recent result established an $\mathrm{FP}^{\mathrm{NP}}$ versus $\#\mathrm{P}$-hard dichotomy for $\#\mathrm{EO}$ problems. The tractable side of this dichotomy can be characterized by functions admitting quasi-polymorphisms of the ternary XOR operation, leaving open whether these cases on the $\mathrm{FP}^{\mathrm{NP}}$ side are in fact in FP. In this paper, we settle this question by giving a polynomial-time algorithm for all cases on the $\mathrm{FP}^{\mathrm{NP}}$ side. Consequently, we obtain a complete FP versus $\#\mathrm{P}$ dichotomy for counting weighted Eulerian orientations, and further for complex-valued Holant problems with an odd-arity signature. Our algorithm is based on a linear programming relaxation, but we use it in a nonstandard way. Instead of proving that the relaxation is integral and solving the problem directly from an optimal LP solution, we use the relaxation as a structural tool to lift the quasi-polymorphism condition to an ordinary polymorphism condition. This reveals an affine local structure of the constraint functions, which leads to tractability.

Authors: Zhili Chen, Zhan Yu

We study the problem of learning an unknown Markovian open-system generator from access to its physical time evolution. This generator, called a Lindbladian, contains Hamiltonian and dissipative coefficients indexed by an exponentially large family of possible Pauli terms. We propose an efficient algorithm that learns arbitrary Lindbladians from time evolution under minimal assumptions. For a Lindbladian of dynamical strength at most $Λ$, the algorithm estimates every coefficient to error $ε$ using $\widetilde O(Λ^2/ε^2)$ experiments and $\widetilde O(Λ/ε^2)$ total evolution time, together with polynomial classical running time. The algorithm consists of two nonadaptive, ancilla-free, and control-free stages: 1. The support-learning stage outputs a candidate support of size $\mathrm{poly}(Λ/η)$ that contains every Hamiltonian and dissipative coordinate of magnitude at least $η$, using $\widetilde O(Λ^2/η^2)$ experiments with preparations of product Pauli eigenstates and single-qubit Pauli measurements. 2.The coefficient-learning stage estimates all coefficients in any candidate support of size $M$ to error $ε$, using $\widetilde O(Λ^2\log M/ε^{2})$ experiments with preparations of random stabilizer states and measurements in random Clifford bases. Composing the two stages identifies and estimates every coefficient of an arbitrary Lindbladian in polynomial time. The experiment-count and total-evolution-time scalings match the lower bounds up to logarithmic factors, so the algorithm is nearly optimal for learning arbitrary Lindbladians.

Authors: Alexandra Lassota, Krzysztof Sornat

We study the computational complexity of winner determination problems in approval-based committee elections under Thiele voting rules. These form a class of rules parameterized by a fixed weight vector that specifies how a voter's satisfaction depends on the number of approved candidates elected. We first analyze the structure of optimal solutions based on the sets of voters who approve each candidate---that is, how voters' approval ballots induce dependencies between candidates---revealing constraints on a winning committee under any fixed Thiele voting rule. Using this, we design FPT algorithms for Proportional Approval Voting (PAV) and other Thiele rules on a natural restricted domain known as the Voter Interval (VI) domain---that is, after a suitable ordering of voters, each candidate is approved by a consecutive interval of voters. In particular, we show that every Thiele rule on VI is FPT with respect to a parameter for which the problem is NP-hard on general instances, even when the parameter takes constant values. Our results advance the understanding of the computational complexity of PAV on Voter Interval instances, which remains one of the central open questions in this area. We further resolve two open questions from the literature on PAV (and other Thiele voting rules) by providing a polynomial-time algorithm for instances where each candidate is approved by at most two voters, and an FPT algorithm parameterized by the total score of a winning committee.

Authors: Sotiris Kanellopoulos

In perpetual scheduling theory, the Pinwheel Covering problem asks, given $n$ frequencies $f_i$, whether there exists an infinite schedule such that every $f_i$ consecutive entries contain at most one occurrence of $i\in [n]$. This models $n$ agents taking turns at executing a job, with a recovery period before working again. Pinwheel Covering is, in a sense, the dual of Pinwheel Packing (also known as Pinwheel Scheduling), which similarly asks for at least one occurrence of $i$ in every $f_i$ consecutive entries. The complexity of both problems is a major open question: both are known to be in PSPACE, but PSPACE-hardness remains unknown. Recently, a finite version of Pinwheel Packing requiring only $k$ occurrences of $i\in [n]$ was introduced by [Kanellopoulos et al., SODA 2026] and proven to be strongly NP-complete. In this work we introduce $k$-Visits Covering, the analogous finite version of Pinwheel Covering, establishing strong NP-completeness even for $k=2$. As a corollary, we obtain that a generalization of Pinwheel Covering with varying frequencies is strongly NP-hard. To the best of our knowledge, this is the first strong NP-hardness result in the covering setting. We complement these results with a linear-time algorithm for $2$-Visits Covering with two distinct frequencies and a randomized polynomial-time algorithm when the number of distinct frequencies is constant. Lastly, we study the density thresholds of $k$-Visits Covering and prove that no non-trivial density bounds exist, contrasting the finite packing version.

Authors: Jan-Henrik Haunert, Joshua Marc Könen, Heiko Röglin, Tarek Stuck

A problem that occurs in different applications in geographical information science is to generate compact regions from areas on a map. This is important, e.g., in the context of electoral districting to avoid gerrymandering. A common measure for the compactness of a region is the Polsby-Popper score, which measures how close a given region is to a circle based on its area and perimeter. We assume that a polygonal subdivision of the plane is given and study the problem of selecting a subset of the polygonal faces that maximizes the Polsby-Popper score, given by $\frac{4πA}{P^2}$, where $A$ is the area of the selected shape and $P$ is its perimeter. We consider the more general task of maximizing $\frac{A}{P^α}$ for an arbitrary $α>1$, which we call the $α$-circularity problem. We perform the first rigorous study of its complexity and show that it is weakly NP-hard if $α\in (1,2]$. Furthermore, for $α>1$ we present a pseudopolynomial time algorithm for this problem.

Authors: Sebastian Angrick, Ben Bals, Paweł Gawrychowski, Solon P. Pissis, Yuki Yonemoto

We consider directed graphs in which the nodes are labeled with strings. A walk in such a graph naturally corresponds to the concatenation of the visited nodes' labels. These graphs are widely used in bioinformatics to compactly describe large collections of highly similar genomes. Given such a graph $G=(V,E)$ and a pattern of length $m$, we seek a walk whose corresponding string has an occurrence of the pattern. We call this the SMLG problem. Amir et al. [J. Algorithms, 2000] showed that SMLG can be solved in $\mathcal{O}(m|E| + N)$ time, where $N$ is the total length of all node labels. Equi et al. [ACM Trans. Algorithms, 2023] showed that this is essentially optimal (under SETH). The existing lower bound assumes that the sought walk is of length $Θ(|V|)$. Thus, we might be able to bypass this lower bound by restricting the walk length to $b-1$, which naturally reduces to having as input a directed graph whose set of nodes is partitioned into $b$ blocks. Then, we seek a walk in this graph that starts in the first block and ends in the last block. We call this the $b$-SMBG problem. We provide a more fine-grained classification that essentially settles the complexity of $b$-SMBG parameterized by $b$: (1) We give a near-linear-time algorithm for $b=3$. (2) We show that there is no combinatorial algorithm improving over the state-of-the-art $\mathcal{O}(m|E| + N)$ bound for any $b\ge 4$. (3) We also present a fast matrix multiplication-based algorithm yielding an improvement for $b \in \mathcal{O}(1)$, which is conditionally optimal. (4) Finally, we show that under SETH, for any $b \in ω(\log |V|)$, no algorithm can improve over the state of the art.

Authors: Gabriel Carmona, Paolo Ferragina, Giovanni Manzini, Francesco Tosoni

In this paper, we study static, computation-friendly, lossless compression formats for graphs, focusing on memory locality and operational efficiency of $k^2$-trees. We observe that their traditional level-wise layouts suffer from poor cache performance due to weak locality, especially in operations such as matrix-vector and matrix-matrix operations. To address this limitation, we propose four depth-first representations of $k^2$-trees: a plain depth-first layout (EDF-1), a balanced-parenthesis representation (BP), and their compressed variants (CEDF and CBP). We further introduce a linear-time compression method based on suffix and LCP arrays to identify and compress identical subtrees. We experimentally evaluate the execution time, the disk space, and the peak-memory usage of our approaches against classical level-wise $k^2$-trees and DFUDS-based representations across two real and one synthetic dataset (i.e., Web Graphs, Wikidata, and random adjacency matrices) over the above linear-algebra operations. Results show that our depth-first layouts are competitive and often superior than known approaches: CEDF achieves the best compression in most settings, EDF-1 and CEDF reduce the peak memory usage consistently, and performance varies by workload, with different layouts excelling in different operations and data regimes. Overall, this work demonstrates that depth-first layouts of $k^2$-trees provide a practical and efficient alternative to traditional layouts, improving both compression and computational performance in matrix operations.

Authors: David García-Soriano, Antoine Schohn

We give an $(1.3865+\varepsilon)$-approximation for correlation clustering in complete graphs, improving the previous best factor of $1.485+\varepsilon$ of Cao et al.\ (STOC'24). Our two key contributions are independent: an efficient approximate separation oracle for the cluster-LP dual and a new rounding scheme. The dual separation task is the CCMinRatio problem: for signed vertex weights $q$, minimize $cost(S)/q(S)$ over sets with $q(S)>0$; here $cost(S)$ measures the correlation clustering disagreements attributed to $S$ in any clustering in which $S$ is a cluster. We give a randomized $(1+\varepsilon)$-approximation in time $2^{poly(1/\varepsilon)}(n+\langle q\rangle)^{O(1)}$. Via the ellipsoid method, this yields a $(1+\varepsilon)$-approximation of the fractional cluster-LP optimum, along with exactly feasible primal and dual solutions certifying its value and a per-instance certificate. The algorithm works directly on the original instance, without a global preclustering: a new localization technique restricts the search to a small universe while preserving a violation, after which weak regularity handles the resulting dense quadratic minimization. Our rounding scheme retains the cluster-based procedure of Cao et al.\ but uses a continuous conditional pivot rule whose analysis rests on a single variance inequality with explicit weights and an exact computer-assisted verification of the resulting polynomial inequalities. This also places the integrality gap of the cluster LP in the narrow range [4/3,1.3865].

Authors: Jayant Chandwani, Pranav M R, Anand Jat, Anshu Ostwal, Diptendu Chatterjee, Anand Narasimhamurthy

The Multi-Depot Capacitated Vehicle Routing Problem (MDCVRP) asks for minimum-cost delivery tours from several capacitated depots to a set of customers. Like most vehicle-routing variants it is NP-hard, so practical solvers must trade solution quality against speed. We revisit this trade-off through the lens of graph matching. Adapting a matching-based construction first developed for the Traveling Tournament Problem, we present two algorithms, Cluster-First and Match-First, that reduce routing to a sequence of minimum-weight matchings. This is more than a heuristic. We prove that for tours of up to two targets the matching formulation solves the MDCVRP exactly in polynomial time for any number of depots, and that both algorithms are constant-factor approximations, with a tight factor of two, in the structured regimes. This matching optimum coincides with the exact combinatorial-auction optimum, so the auction serves as a strong quality baseline. On instances of 1000 customers and 20 depots our methods match or slightly beat that baseline in tour length while running two to three orders of magnitude faster, in tens of milliseconds against tens of seconds, a scale at which exact and auction-based solvers become impractical. Because Cluster-First routes each depot independently, the approach also re-routes cheaply when new customers arrive.

Authors: Zhao Song

We prove an improved restricted isometry bound for Gaussian partial circulant matrices with arbitrary prescribed sampling sets. There is a universal constant $C>0$ such that the following holds. Let $1\leq K\leq m\leq N$ be positive integers, let $Ω\subset\mathbb Z_N$ be any fixed set with $|Ω|=m$, and let $g\sim\mathcal N(0,I_N)$. For every $δ,η\in(0,1)$, the normalized partial circulant matrix generated by $g$ has the RIP of order $K$ with constant at most $δ$, with probability at least $1-η$ over the draw of $g$, provided \[ m\geq Cδ^{-2}K \max\{\log^2(eK)\log(2N)\log(em),\log(2/η)\}. \] The proof refines the Maurey entropy step in the chaos-process argument by combining a noncommutative Khintchine inequality with a Schatten moment estimate controlled by $m$, replacing one factor $\log(2N)$ in the Krahmer--Mendelson--Rauhut bound by $\log(em)$.

Authors: Awnon Bhowmik, Mahmudul Hasan

Let \(T_n\) be the lower-triangular prefix-sum matrix and let \(\cfrob(T_n)\) and \(\ctwo(T_n)\) be the factorization costs that govern mean and maximum per-coordinate squared error of the Laplace matrix mechanism under pure \(\eps\)-differential privacy, for \(\eps>0\). We prove \(\cfrob(T_n),\ctwo(T_n)=Θ\bigl((\log(n+1))^{3/2}\bigr)\) with no sign, sparsity, or squareness restriction and with arbitrary finite inner dimension. Consequently, within the pure-\(\eps\)-DP matrix-mechanism class the optimized maximum and mean squared errors are both \(Θ(\eps^{-2}\log^{3}(n+1))\). Under the factorization contract of Arkhipov and Kalinin (arXiv:2607.08963v1), who prove the matching lower order for factors with entries in \(\{0,1\}\) and state the arbitrary-factor extension as open, the theorem below establishes the order for arbitrary real factors. The lower bound runs through a \(p\)-nuclear obstruction: an aggregate column-width estimate \(D_k(T_n)\asymp n^{3/2}k^{-1/2}\), valid in the low-rank range \(1\leq k\leq n/16\), for the prefix chain, fed into the classical approximation-space conversion of Pietsch and Hinrichs--Pietsch, becomes harmonic at the critical exponent \(p=2/3\), and Hölder's inequality transfers it to both factorization costs. The same computation determines \(\nucpow_p(T_n)\) for each fixed \(0

The Princeton DeCenter invites applications for Postdoctoral Fellows (and more senior researchers) beginning February 2027. Fellows will join an interdisciplinary community advancing research on blockchain, decentralized technologies, and their applications across computer science, economics, law, political science, philosophy, and related fields at Princeton University.

Website: https://apply.interfolio.com/185365
Email: decenter@princeton.edu

By shacharlovett

There is a lot of anxiety about ai wiping off mathematics, including theoretical computer science. It’s funny that we wanted ai to cut *their* jobs, and instead it’s *our* jobs that are cut (maybe). My expectation of what is going to happen is rather flat, and I am open to various scenarios. Still I wanted to make some points.

First, at the moment of this writing, I am not so worried about ai killing the field. There are so many problems in math, and the literature is so unmanageably vast and technical, that I am not particularly shocked that using massive resources one can solve *some* problems. It is very different if the resources can solve *the* problems. For example I, and I am sure many others, have tried to use ai to solve problems in computational complexity and so far didn’t get much. I do find ai to be a very useful assistant, but so are many other things. It may be that the next level of solving target problems (as opposed to finding targets) may prove the most difficult to reach.

I want to suggest an option for the community to put ourselves in a position of strength, in case one really fears the impact of ai. I think ai can easily enough be “frozen” and made much less useful for future research. The way to do this is simple: We could stop feeding it. It was humiliating enough to post papers online only to be asked later by the publisher to pay for “gold open access.” But now that there is this new way to exploit, plagiarize, and monetize our creations on a massive scale, it may be too much. Suppose starting immediately all new math is communicated in ways that ai can’t easily scrape. There are many ways to do this; we could still put papers online, but allow only much more limited access, compatible with human beings but not ai scraping. It coud be similar to what is done for example at the Internet archive, where you can read a book but not easily download it. I am not going to go more in details. While ai would remain very useful for things on the table until that moment, I think it would quickly become much less useful for new lines of research, series of papers building on each other, etc. This would put the community in a position of strength as keeper of knowledge. After a while, things could be reassessed.

We should not forget that the models can do math only because back then we chose to be nice and so taught them how to do it for free.

By Manu

Tenure-track position in theoretical computer science. Two course per semester teaching load, competitive salary. UNF’s School of Computing offers BS, MS, and PhD degrees in Computing. Candidates must have earned Ph.D. by start date of August 2, 2027.

Website: https://unf.wd5.myworkdayjobs.com/unfjobs/job/Jacksonville-FL/Professor—Computing–Open-Rank-_JR103390
Email: indika.kahanda@unf.edu

By shacharlovett

Authors: Igor S. Sergeev

It is shown that the $\mathsf{OR}$-rank (covering rank) of the $2^n \times 2^n$ unique disjointness matrix is $n^{O(1)}(3/2)^n$, hence the known lower bound $1.5^n$ turns out to be essentially tight. By the way, an upper bound $1.89^n$ is obtained for the $\mathsf{SUM}$-rank (partition rank) of this matrix.

Authors: Ramin Javadi, Hossein Shokouhi

Given a graph $G=(V,E)$, a (proper) $k$-coloring for $G$ is a vertex coloring with $k$ colors such that every two adjacent vertices receive different colors. Suppose that the vertex set $V$ is partitioned into some groups, a proper coloring is called fair if for every color class, the difference between the number of vertices in any two groups does not exceed a given threshold. In this paper, we investigate the parameterized complexity of the fair coloring problem with respect to the structural parameters of the input graph. In particular, we prove that the problem is W[1]-hard with respect to the number of groups for forests and also graphs of modular-width two, even when the number of colors is equal to two. On the positive side, we prove that when the number of colors is equal to two, then the problem is FPT with respect to neighborhood diversity of the input graph. Moreover, in general, the problem is FPT with respect to neighborhood diversity and the number of groups. As a by-product, we prove that unary vector bin packing problem is W[1]-hard with respect to the dimension.

Authors: Fangqi Dong, Alex Lombardi, Fermi Ma

The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every $n$-qubit unitary $U$ is computable by efficient quantum circuits relative to some classical oracle $f = f_U$ depending on $U$. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly$(n)$ parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries $P\lvert x\rangle = \lvert π(x)\rangle$, as well as random alternating-basis phase unitaries $F_2 \cdot H^{\otimes n} \cdot F_1$. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries $\lvert x\rangle\mapsto α_x \lvert x\rangle$, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.

Authors: Theodoros Yianni, Nyan Raess, Farid Shahandeh

Generalized contextuality is a canonical distinguishing property of nonclassical generalized probabilistic theories, in particular quantum mechanics. Methods for certification and characterization of generalized contextuality of a given generalized probabilistic theory are well developed for prepare-measure and single-stage prepare-transform-measure scenarios. In a recent work [arXiv:2512.10000], a bottom-up, statistics-first linear-algebraic framework for contextuality in prepare-measure scenarios was introduced. We extend this approach to operational scenarios with sequential transformations with an arbitrary number of stages. We give a full decision procedure for contextuality of such scenarios within operational theories and analyze its computational complexity. In particular, our decision procedure has a complexity linearly exponential in the minimum generalized probabilistic theory (GPT) dimension, and polynomial in the number of procedures. We demonstrate our framework and approach through multiple examples, including Spekkens' toy theory and the 8-state single-qubit stabilizer theory. In particular, we construct an operational theory in which contextuality manifests itself only in the sequential structure of the transformations. Our findings thus shed new light on the significant role of compositional structures in the phenomenon of generalized contextuality.

Authors: Matan Gilboa

In a hedonic game, agents need to be partitioned into coalitions, and have a preference order over partitions. A partition is called strongly popular if it beats any other partition in a majority vote among the agents. We focus on the fundamental class of additively separable hedonic games (ASHGs), where agents have additive valuations that induce their preferences. We prove that determining the existence of strongly popular partitions in ASHGs is complete for PCW, a recently introduced complexity class which lies in between $P^{NP}$ and $S_2^P$ (Gilboa et al., 2025). This settles an open problem by Brandt and Bullinger (2022) and Bullinger and Gilboa (2025).

Authors: Tomoyo Kikuchi, Takashi Kanai

Convex Collision-Free Regions (CCFR) is a collision handling method that explicitly represents local convex feasible regions to enforce non-penetration. Each feasible region is constructed from surrounding mesh primitive configurations, including edge-edge and vertex-face interactions. The resulting convex region represents admissible non-penetrating vertex displacements at the current configuration. Existing collision handling methods for deformable body simulation have largely relied on implicit representations of feasibility, resulting in either compromised robustness for secondary collisions and codimensional contacts or tight coupling with specific nonlinear optimization schemes. Our formulation constructs feasible regions independently for each vertex, defined prior to penetration, inherently accounts not only for primary collisions but also for secondary collisions and codimensional contacts, enabling highly scalable and parallelizable collision handling. These feasible regions encode geometric non-penetration constraints independently of physical contact response models. CCFR does not rely on nonlinear optimization and is compatible with simulation frameworks such as Extended Position-Based Dynamics (XPBD) that do not explicitly maintain interior feasibility during iterative updates. The effectiveness of CCFR is demonstrated across cloth, hair, wire, particle systems, and codimensional contact scenarios, showing versatile and efficient collision handling.

Authors: Chris Kapulkin, Kyle Koyanagi

We show stability of persistent path homology of path complexes. As a consequence, we deduce the stability of persistent path homology of hypergraphs and of sequence hypergraphs, and recover the known stability result for digraphs, originally due to Chowdhury and Mémoli.