Theory of Computing Report

Earlier this week I posted a list of arguments why smoothed analysis is a poor model to study the running time of the simplex method. (Hence why we introduced by-the-book analysis which has none of those problems.)

One thing I mentioned was that the standard Klee-Minty cube is stable under zero-preserving perturbations. Someone asked me for a proof. Since there is currently no written source for this lore, I will write a quick proof here.

Let's start with some traditional Klee-Minty cubes:

\[\begin{aligned} \operatorname{maximize} \quad &x_d \\ \operatorname{subject~to} \quad & 0 \leq x_1 \leq 1 \\ & 0.2 x_{j-1} \leq x_j \leq 1-0.2 x_{j-1} \qquad \forall j \in \{2,\dots,d\}. \end{aligned}\]

Assume the inequalities are ordered as shown: first we list both inequalities for \(j=2\) and then both inequalities for \(j=3\) and so on.

We shift the means slightly and then perturb all non-zero coefficients. This yields a linear program

\[\begin{aligned} \operatorname{maximize} \quad x_d \hphantom{\leq}& \\ \operatorname{subject~to} \quad 0.1 + \alpha_1 \leq& (1+\gamma_1) x_1 \\ & (1+\delta_1) x_1 \leq 0.9+\varepsilon_1 \\ 0.1 + \alpha_j + (0.2 + \beta_j) x_{j-1} \leq& (1+\gamma_j) x_j \\ & (1+\delta_j) x_j \leq (0.9+\varepsilon_j) - (0.2 + \eta_j) x_{j-1} \qquad \forall j \in \{2,\dots,d\}. \end{aligned}\]

Theorem. If \(\alpha,\beta,\gamma,\delta,\varepsilon,\eta \in [-0.05,0.05]^d\) then Bland's rule takes exponentially many pivot steps.

Proof. We go by induction. We prove that there are exactly \(2^d\) bases, and Bland's rule will visit all bases when it starts at the basis minimizing \(x_d\) and works to maximize \(x_d\). All basic feasible solutions \(x\) satisfy \(x \in [0,1]^d\). The Bland path is reversible: if we start at the basis maximizing \(x_d\) and we use Bland's rule to minimize \(x_d\) then the same bases are visited but in reverse order.

We can check the base case \(d=1\) easily. The starting basis consists of the constraint \(0.1 + \alpha_1 \leq (1+\gamma_1)x_1\) and the end basis consists of the constraint \((1+\delta_1)x_1 \leq 0.9 + \varepsilon_1\). The two basic feasible solutions \(\frac{0.1 + \alpha_1}{1+\gamma_1}\) and \(\frac{0.9+\varepsilon_1}{1+\delta_1}\) are easily verified to be in \([0,1]\).

When \(d \geq 2\), assume that the induction statement has been proven for \(d-1\). The starting basis for \(d\) consists of all lower-bounding constraints: \(0.1 + \alpha_1 \leq (1+\gamma_1)x_1\) and \(0.1 + \alpha_j + (0.2+\beta_j)x_{j-1}\leq(1+\gamma_j)x_j\) for all \(j \in \{2,\dots,d\}\).

Take the Bland path for \(d-1\), and append to every basis in it the constraint \(0.1 + \alpha_j + (0.2+\beta_j)x_{j-1} \leq (1+\gamma_j)x_j\). These bases are now bases for the KM-cube in \(d\) variables. The associated basic solutions are identical on coordinates \(1,\dots,d-1\) and have \(x_d = \frac{0.1 + \alpha_j + (0.2+\beta_j)x_{d-1}}{1+\gamma_j}\). The Bland path for \(d-1\) contains \(2^{d-1}\) bases and increases the value of \(x_{d-1}\) in every step. Since \(1+\gamma_d \in [0.95,1.05]\) and \(0.1 + \alpha_d \in [0.05,0.15]\) and \(0.2 + \beta_d \in [0.15,0.25]\) and \(x_{d-1} \in [0,1]\) we get \(x_d \in [0, 0.43]\).

When we consider the constraint \((1+\delta_d)x_d \leq (0.9+\varepsilon_d)-(0.2+\eta_d)x_{d-1}\), we see that the left-hand side is at most \(1.05 \cdot 0.43 \leq 0.46\) and the right-hand side is at least \(0.85-0.25 = 0.6\). That is all we needed to check in order to verify that the bases constructed so far are feasible.

Every step on our path so far is improving. Due to our chosen ordering of the inequalities, the constraint \(0.1 + \alpha_j + (0.2+\beta_j)x_{j-1} \leq (1+\gamma_j)x_j\) will not leave the basis until there is no other possible improving direction left. Hence our path so far is all part of the Bland path for our KM-cube in \(d\) variables.

At the end of our path so far, Bland's rule will pivot out the constraint \(0.1 + \alpha_j + (0.2+\beta_j)x_{j-1} \leq (1+\gamma_j)x_j\) and pivot in \((1+\delta_d)x_d \leq (0.9+\varepsilon_d)-(0.2+\eta_d)x_{d-1}\), since it is the only available improving move.

Now take again the Bland path for \(d-1\), but reverse its order and append to every basis in it the constraint \((1+\delta_d)x_d \leq (0.9+\varepsilon_d)-(0.2+\eta_d)x_{d-1}\). This yields \(2^{d-1}\) more bases for the \(d\)-variable KM-cube. Because we reversed the order, the Bland path is decreasing \(x_{d-1}\). Since \(0.2+\eta_d > 0\) and \(1+\delta_d > 0\), the path is thus increasing the value of \(x_d\). We have now constructed our full Bland path of \(2^d\) bases. It remains to show that these final \(2^{d-1}\) bases are feasible and in \([0,1]^d\). Note that \(1+\delta_d \in [0.95,1.05]\), \(0.9+\varepsilon_d \in [0.85,0.95]\) and \(0.2+\eta_d \in [0.15,0.25]\). Since \(x_{d-1} \in [0,1]\) we get \(x_d = \frac{0.9+\varepsilon_d - (0.2+\eta_d)x_{d-1}}{1+\delta_d} \in [0.57, 1]\). The only constraint that can lead to infeasiblity is \(0.1 + \alpha_j + (0.2+\beta_j)x_{j-1} \leq (1+\gamma_j)x_j\) but its left-hand side is at most \(0.4\) and its right-hand side is at least \(0.57\), hence the bases are all feasible. QED

Interpretation

This theorem directly shows us that Bland's rule has exponential complexity under both relative and zero-preserving smoothed analysis. When we rescale the inequalities by large numbers in the standard way, it follows directly that Dantzig's most-negative reduced cost rule has exponential complexity for relative smoothed analysis.

In my previous post I interpreted the above theorem by stating that zero-preserving smoothed analysis is a dead end. While I stand by that statement, I do want to give a second possible interpretation.

Namely, you can conclude that Bland's rule is just bad.^[1] More specifically: Bland's rule is purely combinatorial in nature. Perturbations are (stochastic) geometry. It is no wonder that Bland's pivoting decisions fail to benefit from perturbations. Dantzig's rule is also bad of course. In this case, specifically because it fails to be scale-invariant with respect to rescaling the inequalities. Dantzig thus similarly fails to be a geometrically-steered pivot rule.

When your pivot rule does incorporate the ambient geometry, you can do significantly better than zero-preserving smoothed analysis. In fact, in the by-the-book paper we bound the running time of a simplex method in a much weaker probabilistic model: only the right-hand side is perturbed.^[2] That is part of why we are so proud of the BTB paper: its both mathematically stronger and scientifically more robust than what we had before.

[1]	Every practitioner will agree.

[2]	We use the semi-random shadow vertex pivot rule, which generally prefers steeper edges over shallower edges. Hence it incorporates the ambient geometry. The analysis also needs some additional minor assumptions to make the definitions make sense: RHS perturbations alone lack scale.

We prove that every De Morgan formula with $n$ leaves has a pointwise $1/3$-approximating real polynomial of degree $O(\sqrt n)$ and coefficient $\ell_1$-norm $2^{O(\sqrt n)}$. The standard approximate-degree theorem for formulas gives the same degree bound, but only yields the weaker coefficient estimate $2^{O(\sqrt n\log n)}$. Our proof constructs, for every formula, a span program with witness size $O(\sqrt n)$ and, additionally, $O(1)$ entrywise-absolute operator norm for the available-vector matrix. A standard span-program-to-polynomial argument then gives the desired approximating polynomial while preserving coefficient weight. We also show that the coefficient bound is tight up to constants in the exponent: the De Morgan formula for inner product modulo $2$ already gives a matching $2^{\Omega(\sqrt n)}$ lower bound for formulas with at most $n$ leaves, even regardless of the degree of the approximating polynomial.

We show that under a plausible number-theoretic conjecture, for any constant $s$ there exists an $s$-server private information retrieval (PIR) protocol that on an $n$-bit database requires communication $\exp(O((\log n)^{1/s} (\log \log n)^{1-1/s}))$. Previous constructions attaining the same communication required $2^{O(s)}$ servers. Our number-theoretic conjecture is implied by existing conjectures, namely the generalized repunit conjecture and Schinzel's hypothesis H (either one of these conjectures would suffice alone). Our result builds on the ``matching vector family + $S$-decoding polynomials'' framework pioneered by Efremenko (STOC 2009) and recently refined by Ghasemi, Kopparty, and Sudan (STOC 2025). The main ingredient is a framework for constructing $S$-decoding polynomials with only $k+1$ nonzero coefficients modulo special products of $k$ primes, resolving an open problem posed by Ghasemi and Kopparty (ITCS 2026). By the lower bound shown by Ghasemi and Kopparty, this is the minimum achievable sparsity. We also empirically validate our construction and make our result unconditional for all $s \leq 15$. We also apply our techniques to regimes where $s$ grows with $n$, showing under a stronger variant of our number-theoretic conjecture that the communication complexity of $s$-server matching-vector PIR can be superpolynomially reduced from the previous state of the art for any $s \leq \exp(o(\sqrt{\log \log n/\log \log \log n}))$. The main result for $s = O(1)$ and its proof were discovered in a GPT-5.5 Pro conversation prompted by the authors.

We describe a method that lifts an arbitrary polynomial $f$ with sparsity $s$ to a polynomial that requires a read-once oblivious algebraic program of width $s$ for every variable order. To do so, we introduce a technique for constructing a gadget based on erasure codes over finite fields, where each variable in $f$ is substituted with a monomial that encodes a codeword into the exponents of the monomial. To the best of our knowledge, our construction represents the first use of error-correcting codes in the context of lifting. As an application, we consider factor complexity, which studies how much the complexity of a polynomial can increase under factorization. Our result allows us to lift any gap in sparsity to the same gap in width in a generic manner.

For a directed graph $G = (V, E)$, we say that a weight function $\rho \colon E \to [M]$ is *min-isolating* if the minimum-weight path from $u$ to $v$ is unique for each pair of vertices $u, v \in V$ such that $v$ is reachable from $u$. If we could efficiently construct a polynomially-bounded min-isolating weight function for any given digraph (or even just for *layered* digraphs), it would follow that NL = UL, thanks to work by Reinhardt and Allender (SICOMP 2000). Van Melkebeek and Prakriya constructed an explicit, deterministic, min-isolating weight function for layered digraphs (SICOMP 2019). Their weight function is *oblivious*, i.e., it is a single weight function that works for all width-$w$ length-$n$ layered digraphs simultaneously, assigning a weight to each possible edge in the digraph without needing to know which edges are actually present. However, they use weights of magnitude $M = 2^{\Theta(\log n \cdot \log w)}$ instead of the desired $M = \mathrm{poly}(wn)$. In this work, we prove that every deterministic, oblivious weight function that is min-isolating for width-$w$ length-$n$ layered digraphs must use weights of magnitude $2^{\Omega(\log w \cdot \log n)}$. This rules out one possible method of proving NL = UL. Our proof is based on a connection with coding theory. A *solid burst error* is a vector $e \in \mathbb{Z}_q^n$ such that the support of $e$ is an interval. Using spectral graph theory methods, we prove that every code $\mathcal{C} \subseteq \mathbb{Z}_q^n$ that can detect solid burst errors with Hamming weight up to $d$ must satisfy $|\mathcal{C}| \leq q^{n - \Omega(\log d)}$, which is optimal. The best prior bound, by Das (BEEI 2012), says $|\mathcal{C}| \leq q^n / (d + 1)$ assuming the code is linear.

Authors: Hrishikesh Belagali, Thomas Van Camp, R. Pradeep, Sourin Das, Namit Anand, Ryan LaRose

Recent experiments on quantum computers have challenged the limits of classical computation in chemistry, simulating ground states of strongly correlated molecules. Many of these experiments have utilized the unitary cluster Jastrow ansatz, a quantum circuit inspired by the unitary coupled cluster ansatz that can be tailored to current quantum hardware. Notably, the largest experiment in Sci. Adv. 11, 25 (2025) executed a quantum circuit with 77 qubits and 10,570 gates on an IBM quantum computer and performed classical post-processing with up to 6400 nodes on Fugaku to compute ground state energies better than Hartree-Fock. In this work, we present a polynomial time classical algorithm to compute the energy of any single-layer unitary cluster Jastrow circuit, independent of locality constraints for quantum hardware. Our algorithm can reproduce the largest experiment from Sci. Adv. 11, 25 (2025) in less than a minute on a laptop, and through circuit optimization enabled by fast simulation we achieve a lower ground state energy than the experiment.

Authors: Alexander S. Kulikov, Ivan Mihajlin

The Edge Coloring problem is notoriously hard: it is still unknown whether it can be solved in time $2^{o(n^2)}$ (let alone $2^{O(n)}$), where $n$ is the number of nodes of the input graph. Can one explain the lack of such upper bounds by deriving a lower bound $2^{Ω(n^2)}$ from a lower bound for SAT, $3$-SUM, or APSP? In this note, we provide a negative answer for this question: if there is a reduction showing that Edge Coloring cannot be solved faster than in $α^{n^2}$ (where $α>1$ is an explicit constant) under a hypothesis that known algorithms for one of the problems mentioned above are optimal, then the corresponding hypothesis is false.

Authors: Yanwen Luo, Yuan Luo

We propose the first algorithm to morph geometric graphs on hyperbolic surfaces. It is based on a generalization of Tutte's spring embedding theorem on essentially 3-vertex-connected graphs. We describe the algorithms in detail and show experiments with triangulations and graphs on a hyperbolic surface of genus two, the Bolza surface, and a hyperbolic surface of genus three, the Klein quartic.

Authors: Johannes Schmidt, Mohamed Maizia, Victor Lagerkvist, Johannes K. Fichte

The propositional abduction problem is a well-known form of non-monotonic reasoning where we are asked to find an explanation of a given manifestation. Recently, there has been an influx of results asking more refined questions about the solution space rather than only individual solutions. For example, we might be interested in finding two solutions that are sufficiently far from each other (diverse solutions) in the solution space. In this paper we consider a related representation question where we ask if a given set of explanations S can represent any other explanation (that is, whether their symmetric difference is smaller than a given k). We first study this problem from a classical complexity perspective and obtain a complete classification. While only a handful of cases are tractable, the increase in complexity compared to classical abduction is often smaller than expected. We then study the parameterized complexity for several parameters and obtain new tractable and hard cases. Interestingly, a full parameterized complexity classification would require resolving the parameterized complexity of the covering radius problem from coding theory. To the best of our knowledge, no useful relationship between coding theory and non-monotonic reasoning has previously been established, but such connections seemingly become important when asking more complex questions about solution spaces.

Authors: Suryajith Chillara, Kshitij Gajjar, Nithish Raja

We study shortest paths in directed graphs whose edge weights are of the form $$ \mathsf{wt}(e) = a_{e,1} λ_1 + a_{e,2} λ_2 + a_{e,3} λ_3 + \cdots + a_{e,d} λ_d + a_{e,d+1}.$$ Here, each $a_{e,i}\in\mathbb{R}$ is a fixed constant for each edge $e$, whereas each $λ_i\in\mathbb{R}$ is common across the entire graph. So, there could be different shortest paths in the graph for different values of the $λ_i$'s. This is called the Parametric Shortest Paths problem, and has been studied since the 1980s. For $d=1$, Carstensen (1983) showed that the number of shortest paths in $n$-vertex graphs is at most $n^{O(\log n)}$. She also proved a matching lower bound of $n^{Ω(\log n)}$, later refined by Mulmuley & Shah (2001). For $d=2$, Gajjar & Radhakrishnan (2019) showed an upper bound of $n^{O(\log^2 n)}$. Barth, Funke & Proissl (2022) generalized their result to prove an upper bound of $n^{O_d(\log^d n)}$ for all positive integers $d$. The lower bound did not undergo any improvement over the years. In this paper, we close this long line of research by showing an $n^{O(d\log n)}$ upper bound for all positive integers $d$, exponentially improving the previous upper bound. We observe that a matching lower bound of $n^{Ω(d\log n)}$ can be obtained from earlier works. We also show that our proof can be adapted to work for undirected graphs with positive edge weights. Furthermore, for directed graphs whose edge weights are univariate polynomials of degree at most $q$, we prove an upper bound of $n^{O(\log{n}+\log{q})}$. Finally, building upon work on the Point Location problem by Ezra, Har-Peled, Kaplan & Sharir (2020), we construct a Shortest Path Oracle which takes as input a point $\overline{x}\in \mathbb{R}^d$, and outputs a shortest path at $\overlineλ=\overline{x}$ in sublinear time (for a wide regime of $d$).

Authors: Patrizio Angelini, Sabine Cornelsen, Giordano Da Lozzo, Seok-Hee Hong, Ignaz Rutter

Orthogonal planar drawings constitute a classical and mainstream research topic in graph drawing due to their clarity and wide applicability. In an orthogonal planar drawing of a graph, each face is represented as an orthogonal polygon, that is, a polygon whose edges are either horizontal or vertical. Yet a planar graph admits such a representation if and only if its maximum degree is at most four. In this paper, we consider planar polyline drawings of graphs with unrestricted maximum degree. We focus on drawings that are ``close to orthogonal'', where closeness is measured by the number of faces that are not orthogonal polygons. We show that, even when the input graph is triconnected and thus has a unique planar embedding, the problem of testing whether there exists a planar polyline drawing with at most $h$ non-orthogonal faces is NP-complete. Motivated by this computational hardness, we study parameterized and approximation algorithms. In the fixed-embedding setting, we prove that the problem admits linear-time FPT algorithms parameterized by (i) the outerplanarity index and (ii) the natural parameter $h$. In addition, we provide an FPT algorithm parameterized by the treewidth and a polynomial-time approximation scheme. In the variable-embedding setting, we give an FPT algorithm parameterized by treewidth for biconnected graphs.

Authors: Arnold Filtser, Hung Le, Nikolas Mählmann, Marcin Pilipczuk, Michał Pilipczuk

Fat minors are the metric analog of graph minors that are tailored to the analysis of metric (edge-weighted) graphs and, more generally, metric spaces having a suitable notion of shortest paths. Despite a large interest in this notion, not much is known about the structure of metric graphs excluding a fixed fat minor. We prove that if a metric graph $G$ excludes a fixed graph $H$ as a $δ$-fat minor, for some $δ>0$, then $G$ enjoys the metric analog of flatness (aka uniform quasi-wideness) - a structural property from the field of Sparsity. In essence, our flatness result says that for any $α\geq β$ large enough compared to $δ$, in every large enough set $A$ in $G$ one can find a sizable subset $B$ that becomes $α$-scattered after removing a bounded number of balls of radius $β$. We call this property drill-flatness. Notably, the proof only relies on excluding shallow fat minors: every branch set has radius at most $2α$. As a corollary, we prove that metric graphs that exclude a fixed $δ$-fat minor have bounded $\varepsilon$-scatter dimension if we consider only $\varepsilon$-scatters at distances large enough compared to $δ$. By combining this with the results of Abbasi et al. [FOCS 2023], we infer that the $k$-Center problem on instances excluding $H$ as a $δ$-fat minor admits an approximation algorithm that finds a solution of cost at most $(1+\varepsilon)\cdot\mathsf{OPT}+{\cal O}(δ/\varepsilon^2)$ in time ${\cal O}_{H,\varepsilon}(n^{{\cal O}(1)})$. This is one of the first algorithmic results for general fat-minor-free metrics. We also study drill-flatness in hereditary classes of (unweighted) graphs, where we obtain a characterization equating drill-flatness with excluding shallow induced minors. This is an induced analog of the equivalence between flatness and nowhere denseness - one of central results of Sparsity.

Authors: Sanjeev Khanna, Aaron Putterman, Junkai Song

In the cut-query model, an algorithm is given access to a graph $G = (V, E)$ \emph{only} via cut queries. This model has seen significant attention in the undirected graph setting, with works establishing $O(n)$ cut query algorithms for computing the global minimum cut, $\widetilde{O}(n^{3/2})$ cut query algorithms for all pairs minimum cut, and many more. However, despite this vast array of progress in designing sub-quadratic query algorithms for computing properties of undirected graphs, there has been \emph{no} progress in designing such algorithms in directed graphs. Indeed, even for basic problems like whether a vertex $t$ is reachable from a vertex $s$, the cut query complexity is only known to be bounded in the interval $[Ω(n), O(n^2 / \log n)]$. In this work, we begin a systematic study of these basic problems in directed \emph{acyclic} graphs (DAGs). In this setting, we show that reachability from a single vertex and even topological sorting are both computable in $O(n \log^3 n)$ many cut queries. As a consequence, we also obtain an algorithm which, for any \emph{arbitrary} directed graph $G$, uses only $O(n \log^3 n)$ cut queries and determines whether $G$ contains a cycle.

Authors: Ismail H. Toroslu

Multi-object tracking in dense crowds requires solving a bipartite assignment problem between detections and trajectories at every video frame. The classical Hungarian algorithm solves this in $O(N^3)$ time, which becomes a bottleneck for large scenes with hundreds of people. We propose an \emph{incremental} assignment algorithm that exploits the block-sparse structure of crowd tracking cost matrices --- dense within each crowd cluster, near-zero between clusters. We compute the exact same optimal $N \times N$ assignment as the Hungarian algorithm, but via an incremental strategy: we add one person at a time, exploiting the fact that after step $n-1$ the dual potentials are \emph{exactly optimal} for the $(n-1)\times(n-1)$ subproblem --- a strictly stronger condition than the intermediate feasibility maintained by the Hungarian algorithm during its $N$ outer iterations. Each new step therefore requires only a single augmenting path search from a certified optimal starting point. This avoids repeated full-matrix scans while guaranteeing an identical globally optimal result. A diagonal-reordering invariant keeps the data structure compact and cache-friendly. On realistic crowd benchmarks with $N \in [200, 5000]$ people organised into dense clusters, our algorithm achieves \textbf{3.7--6.5$\times$ speedup} over the Hungarian baseline while producing provably optimal matchings identical to those of Hungarian. The speedup grows with $N$ and remains stable beyond $N=3000$, making the method especially attractive for large-scale crowd scenes such as stadium exits and mass public events.

Authors: Patthadon Tantiameorn, Grittin Nuntasombat, Jittat Fakcharoenphol

Sketch data structures are very useful for computing statistics on streaming data, including network traffic, server requests, and financial transactions. In recent work, FermatSketch was introduced as an underlying data structure used to monitor changes in network states. It is a linear data structure that maintains an associated array of counters and supports listing all key-counter pairs while using almost linear space. Because it is linear, it can be used to monitor changes between two streams with space proportional to the number of items that change. The data structure is based on a hash table, and all key-counter pairs can be successfully listed when there are slots in the table with exactly one key hashed to them. We show how to relax this requirement by using additional computational resources when listing the key-counter pairs, thereby improving space efficiency with only a small overhead when collecting statistics. We achieve this by storing, for each bucket, multiple linear combinations of the counters whose coefficients are generated from the keys. With this information, certain linear systems can be solved to obtain the key-counter pairs. A preliminary experiment shows a significant reduction of memory needed for the data structure. Our work can be viewed as a trade-off between space and time.

Authors: Cornelius Brand, Robert Ganian, Mathis Rocton

In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networks remains incomplete even when dealing with the simplest kinds of activation functions. Indeed, while there has been a number of very recent results that establish ever-tighter lower bounds for the problem under linear and ReLU activation functions, less progress has been made towards the identification of novel polynomial-time tractable network architectures. In this article we obtain novel algorithmic upper bounds for training linear- and ReLU-activated neural networks to optimality which push the boundaries of tractability for these problems beyond the previous state of the art. In particular, for ReLU networks we establish the polynomial-time tractability of all architectures where hidden neurons have an out-degree of $1$, improving upon the previous algorithm of Arora, Basu, Mianjy and Mukherjee. On the other hand, for networks with linear activation functions we identify the first non-trivial polynomial-time solvable class of networks by obtaining an algorithm that can optimally train network architectures satisfying a novel data throughput condition.

Authors: Joel Daniel Andersson, Anamay Chaturvedi, Monika Henzinger, Roodabeh Safavi

Differential privacy under Continual Observation (CO) quantifies the loss in privacy that occurs when outputs generated using a stream of sensitive input data are published in the online setting. In this paper, we consider a more stringent notion of privacy compared to prior work wherein an individual's participation may shift the entire stream by a time-step. We define a new notion of edit-neighboring streams that captures this scenario. Our findings are as follows. First, we prove that on a stream of length $T$, every additive-noise mechanism incurs error $\tildeΩ(\min\{T^{1/3}/\varepsilon^{2/3}, T\})$ when required to be $\varepsilon$-DP under CO for edit-neighboring streams. This includes state-of-the-art continual counters constructed via the factorization mechanism that in the standard neighboring setting incur only polylogarithmic additive error. Second, we construct the first mechanisms with polylogarithmic additive error for our more stringent notion of privacy. We show that we can recover the same additive error as in the standard notion of privacy albeit with worse constant coefficients for both arbitrary input streams and sparse streams. Third, we show that the notion of edit-neighboring streams inhabits a `sweet-spot' in terms of generality and additive error incurred. More precisely, we show that the even more general notion of prefix-sum neighboring streams---which arises naturally in reductions for problems under CO---must incur additive error scaling as $\tildeΩ(\min\{T^{1/3}/\varepsilon^{2/3}, T\})$ for any mechanism that is $\varepsilon$-DP under continual observation. Finally, we show empirically on synthetic data that when compared with prior work, our mechanism achieves a superior trade-off between the success probability of a simple distinguishing attack, and the additive error incurred by the respective mechanisms.

Authors: Kavya Ravichandran

As humans, we face many decisions that require us to choose between sticking to something and giving up. This thesis uses algorithmic tools to derive insights about such decision-making problems in theoretical models, studying both near-optimal methods and outcomes of social and behavioral influences. Along the way, this thesis sheds light on what we gain and what we lose as we move from a messy and complex real world setting to a very general abstract model by studying various points along this spectrum. In Part I, we study algorithms for sequential decision-making in the improving multi-armed bandits problem. We provide nearly matching upper and lower bounds in the general case. Then, we then ask what is possible if we have access to similar instances to the one we wish to deploy our algorithm on. To that end, we provide guarantees in the data-driven algorithm design framework, showing that a polynomial number of samples is sufficient for learning good algorithms from a class of algorithms. In Part II, we study algorithmic approaches for problems in social epistemology. We start by analyzing what role theoretical models can play in the study of social problems. We then study social and behavioral influences in decision-making requiring investment. First, we provide mathematical formalism in which to study the formation of pessimism traps, a phenomenon identified by philosophers in which agents are influenced by their predecessors to engage in less-ambitious goals. We develop financial interventions to sustainably shift communities out of these traps. The second problem we study is the influence of grit as a behavioral trait in ambitious decision-making. Overall, these works seek to theoretically model phenomena in social epistemology and provide a framework for intervening algorithmically.

The Miller Institute is accepting nominations for its Miller Research Postdoc Fellowships in the basic sciences. The program provides exceptional, curious researchers with the opportunity to conduct research at UC Berkeley. Candidates are selected based on academic achievement, scientific promise, and a strong passion for interdisciplinary discovery.

Website: https://miller.berkeley.edu/nominate-apply/miller-research-fellowship
Email: millerinstitute@berkeley.edu

By shacharlovett

ICM 2026 starts today in Philadelphia; ICM 2030 will be in Glasgow

I am now in Philadelphia after a two-day meeting in New York of the General Assembly of the IMU (International Mathematical Union). Among its many activities, the IMU organizes the ICM (International Congress of Mathematicians).

ICM 2026 starts tomorrow later today (Thursday, July 23) here in Philadelphia, and it was just announced that ICM 2030 will take place in Glasgow. I will try to (slowly) blog about ICM 2026, continuing the tradition of my posts on ICM 2018 and ICM 2022. Yesterday there was an impressive reception event and I had the opportunity to reconnect briefly with man old friends.

A lecture at Columbia University

Yesterday I gave a lecture at Columbia University to a group of brilliant students, followed by a lively discussion. I spoke about some old problems and results in discrete geometry and reflected on how our understanding of them has evolved over the years.

Two quantum items

Here is a draft of my recent paper, The Fully Depolarizing Noise Conjecture for Entangled Physical States: A Twenty-Year Perspective. As always, comments and corrections are most welcome.

Amit Hagar (a philosopher of science from Indiana University) has written an interesting paper entitled The NISQ Trap: Eight Years of Demonstrations the Hardware was Built to Lose. (There is a post about it and an interesting discussion on Shtetl-Optimized.) This joins an earlier paper of Amit’s from 2009, Active Fault-Tolerant Quantum Error Correction: The Curse of the Open System and his subsequent book on the subject.

A lecture for Furstenberg’s birthday

I gave a talk in Hebrew at an evening celebrating Hillel Furstenberg’s 90th birthday. The talk was about Furstenberg’s contributions to enumerative combinatorics and their recent applications to algebraic circuit complexity. Here are the slides, and here is the raw video of the event. (My lecture 2:13:00.)

AI and math news

Two significant items: The Jacobian conjecture has been disproved (Claude; see this enlightening blog post by Terry Tao); the double cover conjecture has been proved (OpenAI).

By Gil Kalai

Authors: Frederic Koehler, Pui Kuen Leung

Let $\mathbb{K}\in\{\mathbb{R},\mathbb{C},\mathbb{H}\}$, put $β=\dim_{\mathbb{R}}\mathbb{K}$, and let $G_n^{\mathbb{K}}$ be an $n\times n$ matrix with i.i.d. standard $\mathbb{K}$-Gaussian entries, namely a standard $\mathbb{K}$-Ginibre matrix. We prove that the normalized row-ordered permanent $W_n^{\mathbb{K}}=\operatorname{per}_{\mathbb{K}}G_n^{\mathbb{K}}/\sqrt{n!}$ has a radial density $p_n^{\mathbb{K}}$ satisfying $\|p_n^{\mathbb{K}}\|_\infty=p_n^{\mathbb{K}}(0)\lesssim_βn^{(β+2)/4}$ and $\sup_{z\in\mathbb{K}}\mathbb{P}(|W_n^{\mathbb{K}}-z|\leq\varepsilon)\lesssim_βn^{(β+2)/4}\varepsilon^β$. In particular, for $\mathbb{K}=\mathbb{C}$, this resolves the Permanent Anticoncentration Conjecture of Aaronson and Arkhipov. The proof compares the squared Gaussian permanent with the squared (Study) determinant in Laplace-transform order.

Authors: Todor Antić, Jiří Fiala, Jelena Glišić, Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Jan Kratochvíl, Giuseppe Liotta, Morteza Saghafian, Maria Saumell, Krisztina Szilágyi, Pavel Valtr

Let $Γ$ be a straight-line crossing-free drawing of a tree $T$. A \emph{bad pair} in $Γ$ is a pair of non-adjacent vertices of $T$ whose Euclidean distance in $Γ$ is smaller than the length of the longest edge in the path connecting them in~$Γ$. When $Γ$ has no bad pairs, $Γ$ is a Euclidean Minimum Spanning Tree of its vertex set (or EMST-drawing for short). Deciding whether a tree of maximum degree at most six admits an EMST-drawing is known to be \NP-hard. In contrast, we characterize those caterpillars that admit an EMST-drawing. The characterization gives rise to a linear-time algorithm that decides if a caterpillar admits an EMST-drawing, and in the affirmative case, computes such a drawing. For caterpillars of maximum degree six, we further present a linear-time algorithm to compute a crossing-free straight-line drawing with the minimum number of bad pairs. For $n$-vertex trees with maximum vertex degree $Δ$, we prove the $Δ^2n\log n$ upper bound on the minimum number of bad pairs. In the special case of stars, we construct a drawing with the minimum number of bad pairs.

Authors: Saeed Odak, Jonathan Rollin, Torben Scheele

A graph is $k$-matching-planar if it admits a drawing in the plane such that, for every edge $e$, the edges crossing $e$ contain no matching of size greater than $k$. The class of $k$-matching-planar graphs generalizes other beyond-planar graph classes, such as $k$-planar and fan-planar graphs. In a $2$-layer drawing of a bipartite graph, the vertices of the two bipartition classes are placed on two parallel horizontal lines and edges are drawn as straight-line segments between them. We prove that every graph with a $2$-layer $k$-matching-planar drawing has pathwidth at most $2k+1$. Moreover, for every $k \geq 0$, we construct a graph with a $2$-layer $k$-matching-planar drawing whose pathwidth is $3\lfloor k/2\rfloor + 1$. On the algorithmic side, we consider the one-sided recognition problem where a fixed embedding of the vertices on one side is given. We show that this problem is NP-hard. On the other hand, we prove that the problem is fixed-parameter tractable with respect to $k$. Finally, we prove that the two-sided variant cannot be approximated within any constant factor in polynomial time unless $\operatorname{P}=\operatorname{NP}$.

Authors: Michael A. Bekos, Carla Binucci, Emilio Di Giacomo, Walter Didimo, Luca Grilli, Maria Eleni Pavlidi, Alessandra Tappini, Alexandra Weinberger

Linear layouts of graphs -- particularly \emph{stack} and \emph{queue} layouts -- are well-established types of representations in graph drawing, thanks to their connection with numerous theoretical and practical problems. In such layouts, all vertices are linearly ordered and the edges are partitioned into sets that avoid specific forbidden configurations: in a stack layout no two independent edges within the same set cross, whereas in a queue layout no two independent edges within the same set are nested. A central problem in this context is to determine, for a given graph $G$, its \emph{stack number} or \emph{queue number}, that is, the minimum number of sets into which the edges can be partitioned so that a corresponding stack or queue layout of $G$ exists. In this work, we introduce a relaxation of stack and queue layouts, which allows some forbidden patterns for the edges in the same set. Namely, for a given integer $k > 0$, a \emph{$k$-defective stack layout} (resp. a \emph{$k$-defective queue layout}) allows an edge to be in a crossing (resp. nesting) relationship with at most~$k$ edges within the same set. Our motivation is to extend the classes of graphs that admit linear layouts using a limited number of edge-partition sets, at the cost of allowing some defects. We study defective linear layouts both from a combinatorial and from an algorithmic perspective, providing an array of results across different graph classes and parameters.

Authors: Henrique Ennes, Clément Maria

The Solovay-Kitaev algorithm describes how to approximate, to arbitrary precision, a matrix in the special unitary group SU(d) using any fixed universal gate set. Although the algorithm scales as O(poly(log(1/$ε$))), where $ε$ is the maximum targeted approximation error, its running time depends exponentially on the qudit dimension d. This bad dependence can be traced to its explicit use of an $ε$_0-net of size 2 $Ω$(d^2) , which is queried O(poly(log(1/$ε$))) times throughout the execution. For this reason, the standard Solovay-Kitaev theorem is usually stated for fixed d, with the base net and its lookup cost absorbed into the constants. We study the algorithmic problem in the variabledimension regime and show how to avoid searching an exponentially large precomputed net for each target unitary. In particular, we introduce the notion of a good exponential basis and show that such a basis can replace the usual depth-zero net-search routine. This yields a modification of the algorithm in which the use of an explicit net is fully moved to a preprocessing step. For instruction sets that already contain, or allow the efficient construction of, a good exponential basis, the resulting online synthesis algorithm is polynomial in d and polylogarithmic in 1/$ε$. For arbitrary universal instruction sets, the exponential dependence on d^2 is not removed, but is isolated into a one-time additive preprocessing cost. Our technique uses differential-geometric methods to devise an integerized version of trotterization that replaces the depth-zero net query by a constructive local synthesis routine. The same framework also suggests possible extensions based on other discretized numerical integration schemes.

Authors: Nattawut Phetmak, Grittin Nuntasombat, Jittat Fakcharoenphol

We study an infinite variant of the coin-covering problem for periodic point sets in the plane. Given a point set of spacing $d$, we ask whether all of its points can be covered by pairwise non-overlapping unit disks. We consider the triangular lattice, the square lattice, and the honeycomb point set, and construct periodic motif patterns that certify several intervals of coverable spacings. For the triangular lattice, our constructions include single-family patterns with vertex, face, and off-lattice realizing centers, as well as multi-family patterns. For the honeycomb point set, additional native motifs fill gaps left by the triangular-lattice constructions. For the square lattice, we revisit the constructions of Alm et al., identify an unintended overlap in one motif realization, and give new patterns that recover part of the affected interval and establish an additional coverability interval.

Authors: Grittin Nuntasombat, Nattawut Phetmak, Jittat Fakcharoenphol

Given two sets of points in 3-dimensional space $R$ and $B$, we want to separate these two sets of points using a classifier based on linear constraints, while ensuring robustness against outliers. The problem was studied in $\mathbb{R}^2$ by Glazenburg et al. We follow their approach and present various algorithms for many types of classifiers under various definitions of outliers. Our algorithms rely mainly on the duality of points and planes in $\mathbb{R}^3$.

Authors: Songtao Mao

The low-degree method and its associated lower bounds are widely used to guide algorithm design and to provide evidence of computational hardness in average-case inference, high-dimensional statistics, random optimization, and related problems. This led to the low-degree conjecture, which predicts that when the low-degree advantage between a planted distribution and a uniform null distribution remains bounded, no efficient distinguisher can succeed after independent noise, provided that the planted distribution has permutation symmetry. Several works have produced counterexamples to variants of this conjecture or to versions for algorithms with higher time complexity, but the conjecture remained open in its standard binary, polynomial-time formulation. We disprove the polynomial-time low-degree conjecture by giving a family of examples in this setting. For every fixed integer $r\geq3$, we construct a permutation-invariant distribution $\mathbb{P}_n$ on simple graphs, with $\mathbb{Q}_n=G(n,1/2)$, such that every marginal of $\mathbb{P}_n$ on at most $D_n=Θ((\log n)^{r-1})$ edges is uniform. Therefore, the low-degree advantage is zero through degree $D_n$. Nevertheless, after every edge is independently resampled at a fixed positive rate, a deterministic rank test strongly distinguishes the resulting distribution from $\mathbb{Q}_n$ in polynomial time. The construction chooses a subspace of a Reed--Muller code whose nonzero polynomials have small absolute bias, selects points whose evaluation vectors have no short linear dependencies, and evaluates a random alternating bilinear form on pairs of these vectors. Our result shows that low-degree indistinguishability, a uniform null distribution, permutation invariance, and independent resampling do not by themselves imply polynomial-time hardness, and suggests that a valid general conjecture must impose an additional condition.

Authors: Jack Fitzsimons

Nikolov and Ullman asked whether k statistical queries on a universe of size T can be released under pure differential privacy with expected worst-coordinate error at the square-root rate suggested by known lower bounds. We prove their conjectured upper bound. For every database size n and privacy parameter $\varepsilon>0$, there is an $\varepsilon$-differentially private mechanism with expected error $O(\min\{1,\sqrt{\log(2T)\log(2k)/(\varepsilon n)}\})$. This matches the lower-bound dependence in the standard high-dimensional regimes where those bounds apply; the shifted logarithms and outer minimum make the upper bound valid without additional parameter assumptions. The construction starts from a selection-only private multiplicative weights transcript, then replaces its probability mass function by a distance-penalized likelihood envelope. To prove that the modification preserves accuracy, a likelihood-level Maurey argument upper-bounds each Hamming-ball maximum by a small family of auxiliary PMW laws. Renyi moment bounds control nearby balls, a direct mixture bound controls distant balls, and grouping radii at the privacy scale prevents an additional $1/\varepsilon$ factor in the error. The mechanism is information-theoretic. A companion Lean 4 development machine-checks the finite construction, pure privacy after deterministic decoding, and the displayed all-regimes upper bound.

Authors: Rajesh Jayaram, Honghao Lin, Vahab Mirrokni, David P. Woodruff

Multi-vector embeddings represent items by point clouds and compare query and document point clouds using Chamfer similarity, whereas single-vector embeddings use ordinary inner products. For singleton queries, Chamfer becomes maximum inner product similarity (MAX-IP). In our setting, MUVERA gives dimension $m^{O(1/\varepsilon^2)}$~\cite{dhulipala2024muvera}, whereas the previous lower bound $(\varepsilon^2m)^{Ω(1/\varepsilon)}$~\cite{jayaram2026expressive} left a gap between $1/\varepsilon$ and $1/\varepsilon^2$ in the exponent of $m$. We nearly close this gap. For every fixed $δ\in(0,1)$, there are constants $A_δ,c_δ>0$ such that, for all sufficiently small $\varepsilon>0$ and every $m\ge(1/\varepsilon)^{A_δ}$, there exist unit query vectors and document point clouds of at most $m$ unit vectors for which every single-vector approximation of all pairwise MAX-IP values to additive error $\varepsilon$ has dimension \[ D \ge m^{c_δ/\varepsilon^{2-2δ}}. \] This holds even for fully data-dependent representations chosen after seeing the dataset. It also applies to Chamfer because all queries are singletons. Since $δ$ can be arbitrarily small, the exponent approaches the $O(1/\varepsilon^2)$ dependence of the upper bound. The proof combines Sherstov's pattern matrix method with polynomial-size, constant-width DNF formulas computing functions of approximate degree $Ω(k^{1-δ})$. Uniform-width padding and a block encoding create an $Ω(\varepsilon)$ gap. A dummy coordinate then equalizes all false inputs, yielding a unit-sphere MAX-IP matrix that is an exact two-valued affine image of the DNF pattern matrix with gap at least $8\varepsilon$. This allows the approximate-rank bound to apply.

Authors: Kostas Lakis, Johannes Lengler, Adeline Pittet

We study distributed vertex colouring on Hyperbolic Random Graphs (HRGs), a geometric random graph model capturing key structural features of real-world networks. This provides a natural setting for analysing distributed algorithms beyond worst-case general graphs. We introduce Sequential Radial Colouring, a CONGEST algorithm using only efficient local computation. The algorithm achieves a near-optimal palette, colouring HRGs with $\frac{4}{3}χ$ colours and running in $O((\log\log n)^2)$ rounds a.a.s. We also give a variant that speeds this up to $O(\log\log n)$ rounds a.a.s., at the price of using $O(χ\log\log n)$ colours. Finally, for every constant $\varepsilon>0$, it runs in $O(1)$ rounds a.a.s. when $χ^{1+\varepsilon}$ colours are used. This greatly reduces the number of colours over the previous constant-round algorithm of Maus and Ruff (SODA 2026) by a factor of at least $n^{1/6}$. Our analysis contains a phase in which we consider a classical randomised colouring protocol on a (large) clique of the graph. We also delve deeper into this part of the analysis and improve upon previous results for colouring a clique $C$, bounding the number of rounds required as a function of the additive slack $s = |Ψ| - χ$, where $Ψ$ is the set of colours used. In particular, constant-round colouring is possible if and only if $s=|C|^{1+Ω(1)}$, while $s=|C|/\log |C|$ already gives the optimal $Θ(\log\log |C|)$ round complexity.

Authors: Diego Arroyuelo, Aidan Hogan, Gonzalo Navarro, Juan Reutter

We study how to evaluate basic graph patterns (BGPs) in a worst-case-optimal (wco) manner over {\em temporal} labeled graphs, where edges have an interval of temporal validity. We adopt a flexible query language in which users specify m quads of the form (subject, property, object, time), using constants or variables. The time component denotes the instant at which a particular edge is valid, and users may also include order relations between temporal constants or variables. The answer is the set of all valid variable assignments, including time. We describe an index structure that, for a temporal graph with N edges, requires O(N) space and can evaluate extended BGPs in wco time O(Q* m log N), where Q* represents the maximum number of solutions for query Q over any temporal graph with the same number of instants of edge validity. We use our index to adapt Leapfrog Triejoin to the temporal graph setting under any variable evaluation ordering. Our index further yields wco guarantees for related query types, including snapshot evaluation, version queries, and other temporal variants. Experiments on real-world datasets show that our approach answers realistic queries in milliseconds with low space overhead.

Authors: Sina Kalantarzadeh, Kanstantin Pashkovich

Prophet inequalities are a fundamental model for online decision-making under uncertainty. For matroid constraints, Kleinberg and Weinberg gave a tight $1/2$-approximation, but their algorithm uses adaptive thresholds that depend on the previously accepted elements. Specifically, the mechanism of Kleinberg and Weinberg accepts an arriving element if and only if it is feasible to add with respect to the matroid constraint and the value of the arriving element passes its threshold; but this threshold depends on the elements accepted so far and on the arriving element itself. Later, Feldman, Svensson, and Zenklusen showed that one can give a $1/4$-approximation for general matroids. Their algorithm is almost non-adaptive, i.e., it uses non-adaptive thresholds but changes the underlying matroid to another ``stricter'' matroid. Feldman, Svensson, and Zenklusen also showed that no constant approximation is possible in general matroids using non-adaptive thresholds if one does not change the underlying matroid. We give a new almost non-adaptive algorithm for matroid prophet inequalities that achieves a $1/2$ guarantee. We change the underlying matroid to a ``stricter'' new matroid that is a direct sum of several matroids. For each part of the new matroid, we precompute a single non-adaptive threshold. Once the elements start to arrive, we accept an arriving element as long as it is feasible with respect to the new ``stricter'' matroid and its value passes the precomputed threshold. In addition, we guarantee that our algorithm achieves the $1/2$ guarantee not simply with respect to the prophet's expected gain, but with respect to the stronger ex-ante relaxation value. Thus, we provide the first almost non-adaptive algorithm for the matroid prophet inequality that achieves the best-possible approximation guarantee of $1/2$.

Authors: Abhijeet Sahu, Harmit Singh, Soham Nandy, G. Ramakrishna

Spanning trees are fundamental structures in graph theory, essential for various applications such as network maintenance, routing adjustments, and many more. The dynamic nature of real-world networks requires efficient updates to these structures as the underlying graph evolves. Maintaining rooted spanning trees dynamically is particularly crucial for algorithms addressing 2-connected components and minimum-weighted spanning trees. In this paper, we address the challenge of maintaining a rooted spanning forest when a batch of edges are inserted or deleted. We present four novel fully dynamic parallel algorithms to update the spanning forest without reconstructing it from scratch. To the best of our knowledge, parallel algorithms for this problem remain largely unexplored. Our experiments on a diverse collection of real-world graphs using a GPU environment demonstrate a throughput of 2 million insertions and 1.4 million deletions per second, significantly outperforming state-of-the-art parallel static algorithms.

Authors: Qi Duan

In the three-terminal Reachability-Preserving Minimum Edge Cut problem, the input is an undirected edge-weighted graph with terminals \(s_1,s_2,t\). The objective is to delete a minimum-cost set of edges that separates \(t\) from both \(s_1\) and \(s_2\), while preserving connectivity between \(s_1\) and \(s_2\). We give a polynomial-time \(O(\log n)\)-approximation algorithm. The algorithm uses a probabilistic distribution of cut-dominating decomposition trees. A direct transfer of a connected tree solution to the original graph is not valid because a connected tree cluster may induce a disconnected vertex set in the graph. We overcome this obstruction by expanding every rooted tree cluster into the connected components it induces in the original graph. These components form a node-weighted auxiliary graph. A minimum node-weighted path in this auxiliary graph produces a connected feasible source side. The main structural observation is that the total graph-boundary cost of all connected components of a rooted tree cluster is no greater than the capacity of the corresponding tree edge. This permits the auxiliary path to be compared with a tree cut separating an optimal preserved \(s_1\)-\(s_2\) path from \(t\). Combining this comparison with the expected \(O(\log n)\) cut distortion of the decomposition trees proves the approximation guarantee.

Authors: Lunjia Hu, Kevin Tian, Chutong Yang

We study the problem of recalibrating an online predictor [KE17, OKS24]: given an arbitrary "hint" sequence of forecasts, the learner must output new predictions that are calibrated while incurring small excess error relative to the original forecasts, under a proper loss. We give an online algorithm that achieves $(\varepsilon, \varepsilon^2)$-recalibration for Lipschitz proper losses in $T \approx \varepsilon^{-3}$ rounds, using an imbalanced extension of the recent simultaneous Blackwell approachability reduction framework of [HTY26]. We show that this tradeoff is optimal by proving a matching lower bound for recalibrating against the squared loss. We also prove a companion $\mathcal{K}_2$-recalibration theorem that obtains the same tradeoffs up to a logarithmic factor. As our main application, we show how our recalibration algorithms can be combined with the online refinement method of [FH23] to obtain simultaneous $\varepsilon$-calibration and $\varepsilon^2$-calibeating for smooth proper losses at the same asymptotic rate, improving upon prior works that achieved these properties separately or with a worse $\varepsilon$ dependence. In particular, the $\mathcal{K}_2$ variant answers a question of [CHJL26] on simultaneously achieving near-optimal calibeating and calibration rates. We also derive extensions to settings with multiple hint sequences. Finally, we empirically evaluate our algorithms on a classification dataset undergoing distribution shift.

Authors: Ritabrata Barat, Siddharth Barman, Nirjhar Das, Sukruta Midigeshi

We study the problem of recovering the objective of a packing linear program when the algorithm accesses only comparison information about optimal solutions under varying constraint matrices. Motivated by optimization with comparison oracles (Cohen-Addad et al., STOC 2026) and preference feedback (Kaufmann et al., TMLR 2025), this strengthens inverse-optimization frameworks by replacing direct observations of optimal solutions with ordinal queries. We focus on the fractional knapsack problem, where the packing linear program (LP) has a single budget constraint specified by item prices, and the objective is determined by item values. This captures monopoly-pricing where a seller infers a buyer's unknown valuations for divisible items from comparison information. The algorithm queries an oracle with two price vectors, returning which optimal solution has the larger total packing or objective value. Such oracles abstract discrete-choice surveys of buyers choosing between differently priced alternatives. For fractional knapsack, we develop a polynomial-time algorithm recovering item values up to scale using $O(n \log(1/δ)+B^2)$ comparison queries, where $n$ is the number of items, $B$ is the knapsack capacity, and $δ$ is the value grid resolution. We complement this with an $Ω(n \log(1/δ))$ lower bound. A key insight is that in the comparison-oracle model, fractional knapsack is as general as packing LPs. Our algorithm solves the packing setting by treating a constraint matrix row as the price vector and zeroing the rest. The $Ω(n \log(1/δ))$ lower bound continues to hold for packing LPs, making our upper bound essentially best possible, up to a linear-factor gap. Finally, we extend our algorithm to profit-maximization, yielding a comparison-oracle analogue of the revealed-preference result of Amin et al. (AAAI 2015).

Authors: Eric Price, Kevin Tian, Zhiyang Xun, Yusong Zhu

Modern LLM deployments use a number of implementation choices and inference optimizations (e.g., batching, custom kernels, and quantization) on top of fixed weights, so two engines serving "the same model" can produce meaningfully different distributions. We study the problem of estimating the total variation (TV) distance between two length-$n$ autoregressive distributions to additive error $\varepsilon$, under three access models. (1) Under sample access, we use $\widetilde{O}(n^2 K/\varepsilon^2)$ queries, where $K$ is the maximum support of the next-token distribution. This improves upon the $\widetilde{O}(n^3 m/\varepsilon^5)$-query estimator of Meel et al. (2025), where $m \geq K$ is the total size of the token alphabet. (2) Under logit access, we use $O(n/\varepsilon^2)$ queries, and this is tight. (3) Under noisy logit access, we smoothly interpolate between the above two guarantees: if probability values are given to relative error $σ$, we use $\widetilde{O}((n+n^2σ^2)/\varepsilon^2)$ queries. We complement our theoretical results with an empirical evaluation of our algorithms, for example measuring the distance between SGLang and vLLM serving identical weights. Our experiments highlight the robustness and practicality of estimating the total variation distance, which remains estimable where the KL divergence is infinite. Our code is available at https://github.com/XunZhiyang/llm-tv-estimation.

Back in the 90s when I was a young professor at the University of Chicago, we would have a Complexity Class of the Week where I would take some interesting complexity class, write down on a white board everything we knew about it with some open problems and students and faculty would muse over it. When I started the blog in 2002, I took the concept online. 

My first Complexity Class of the Week post covered the class \(S_2^P\). Recently Rahul Santhanam said to me "\(L_2^P\) is the new \(S_2^P\)". So for one week only, I'm bringing back the complexity class of the week to talk about \(L_2^P\), the set of problems reducible to the linear ordering principle. 

Recall the \(S_2^P\) courtroom: a polynomial-time judge, two lawyers submitting written arguments, one arguing the string is in the language, the other arguing it's out, and neither seeing the other's brief. For \(L_2^P\) we add one rule: the judge's rulings must be transitive. Each lawyer submits an argument that the judge can compare in polynomial time, where the judge in his mind ranks all the arguments in a linear order. The best argument wins.

The linear ordering principle states that any total linear order of a finite set has a unique minimum element. Oliver Korten and Toni Pitassi define the Linear Ordering Principle (LOP)  as a total search problem: given a circuit \(C(x,y)\) purporting to compute a linear ordering on \(\{0,1\}^n\), find either the minimum element or a witness that one of the order axioms fails (a violation of antisymmetry or transitivity). \(L_2^P\) is the class of languages polynomial-time Turing reducible to LOP. Korten and Pitassi show polynomial-time many-one, Turing and even \(\mathrm{P^{NP}}\) reductions to LOP all give the same class. Equivalently, \(L\in L_2^P\) if there is a polynomial-time relation \(R\) such that for every \(x\), \(R(x,\cdot,\cdot)\) defines a linear order on polynomially-long strings, and the minimum element begins with a 1 exactly when \(x\in L\). That last formulation makes clear that \(L_2^P\) is just \(S_2^P\) with a transitive referee, so \(L_2^P\subseteq S_2^P\).

Korten and Pitassi show \(\mathrm{P^{NP}}\subseteq L_2^P\subseteq S_2^P\) and \(\mathrm{MA}\subseteq L_2^P\). Edward Hirsch and Ilya Volkovich show  \(\mathrm{P^{prMA}}\subseteq L_2^P\), answering a 2011 question of Venkatesan Chakaravarthy and Sambuddha Roy on whether \(\mathrm{P^{prMA}}\subseteq S_2^P\). MA is the class of two-round interactive proofs where the prover goes first. Promise-MA (prMA) means you need to give the correct answer when the promise holds but can give an arbitrary response when it doesn't.

Since Jin-Yi Cai showed \(S_2^P\subseteq \mathrm{ZPP^{NP}}\), and under standard derandomization assumptions \(\mathrm{P^{NP}}=\mathrm{ZPP^{NP}}\), in the world most of us believe in, \(\mathrm{P^{NP}}= \mathrm{P^{prMA}}=L_2^P=S_2^P=\mathrm{ZPP^{NP}}.\)

Why define the class at all? It came out of the recent breakthroughs on circuit lower bounds. Lijie Chen, Shuichi Hirahara, Zeyong Li and Hanlin Ren showed that \(S_2^E\) requires circuits of near-maximum size \(2^n/n\), by giving a clever algorithm for the Range Avoidance problem: given a circuit mapping \(n\) bits to \(n+1\) bits, find a string outside its range. Korten and Pitassi sharpened their algorithm into the reduction from Range Avoidance to LOP and thus to \(L_2^P\). The payoff: \(L_2^E\) requires \(2^n/n\)-size circuits, and for every fixed \(k\) there is a language in \(L_2^P\) without \(n^k\)-size circuits. In my 2002 post I wrote that "\(S_2^P\) is the smallest class known to have these properties." That's where the quote from Rahul came from.

Karp–Lipton collapses have moved too. Korten and Pitassi asked whether NP in P/poly collapses PH to \(L_2^P\); Hirsch and Volkovich answered yes via \(\mathrm{PH}=\mathrm{P^{prMA}}\subseteq L_2^P\). 

Some of my old work on \(S_2^P\) now moves to \(L_2^P\). With Aduri Pavan and Samik Sengupta, we showed that if \(\mathrm{P}^{\mathrm{NP}[1]} = \mathrm{P}^{\mathrm{NP}[2]}\) then the polynomial-time hierarchy collapses to \(S_2^P\). Vyas Ram Selvam extended that collapse to \(\mathrm{P}_{||}^{\mathrm{NP}[1],\mathrm{MA}[1]}\subseteq \mathrm{P^{prMA}}\subseteq L_2^P\) under the same assumption.

Thirty years ago Yamakami and I constructed a language \(L(G)\in\Sigma_2^{P,G}\cap\Pi_2^{P,G}\) and used it to show generic oracles separate \(\Sigma_2^P\cap\Pi_2^P\) from \(\mathrm{P^{NP}}\). I later pushed \(L(G)\) into \(S_2^{P,G}\) and with a little effort can now show \(L(G)\in L_2^{P,G},\) showing that \(\mathrm{P^{NP}}\subsetneq L_2^P\) relative to generic oracles.

One thing that doesn't carry over: last fall I showed that the search version of \(S_2^P\) is equivalent to  \(\mathrm{TF}\Sigma_2\), a probably larger class, where the search version of \(L_2^P\) is just LOP, computationally equivalent to \(L_2^P\).

Whether  \(L_2^P=S_2^P\) or even \(L_2^P=\mathrm{ZPP^{NP}} \) remains open even in relativized worlds.

For more, read the well-written papers by Korten and Pitassi and Hirsch and Volkovich.

By Lance Fortnow

I’ve been obsessed with playing guitar and making music since I was thirteen. Obviously, as a giant nerd, I approach this in the nerdiest way possible. So much of my playing is thinking about the mathematical relationships in patterns of intervals and shapes. I love challenging abrasive music that involves odd counting or microtones. I geek out on music technology, be it software or hardware. But in the decades I’ve been doing this, I’ve never come across someone who thinks I’d be able to get better at music through science.

Why are there no science-based guitar lessons? There are countless books with varied methods on the fastest way to learn or the best way to get better. There’s beautiful math you can nerd out on. Just like in weightlifting, people sell their lessons online on Instagram. But none of the musicians I follow ever put up PubMed screenshots. Instead, you find a psychopathic Spaniard who learns to play impossibly hard drum parts with one arm tied behind his back.

Don’t the laws of adaptation apply to music? It’s certainly the case that the more you practice, the better you get. Much of music practice is just sensorimotor learning. You are adapting both neural pathways and strengthening muscles. There’s psychophysical adaptation in syncing your limbs up with a click track. There are fine motor skills involved in hyperefficient picking. It’s also clear that if you practice too much, you’ll make your hands bleed or develop tendonitis. Surely Selye’s General Adaptive Syndrome applies to woodshedding.

I mean, the concept of progressive overload clearly applies to practice. The way you learn a song is to set your metronome to half time and work your way through the notes. Once you have it down, you increase the beats per minute by one. Each time you come back, you play faster than last time. Next thing you know, you are shredding Chopin.

And it’s not like there’s one perfect way to learn how to be the best at your instrument. There are wide disagreements about the best auxiliary exercises to improve your chops. There is an infinite collection of tutorials and courses designed to improve your skills, telling you which rhythms to practice, which strings to skip, which positions to memorize. And yet, no one thinks you need to run RCTs on these books to crown the best one.

You might say music exists more for art than for competition, and I’d applaud your idealism. But the music industry is a rough one, and it gets pretty cutthroat when you try to make a career out of it.

I write all this to ask what it is about the gym that makes us think that we can science it. I don’t have a good answer to this yet. I have a few partial answers, but none are particularly satisfying to me.

First, there is a clear connection to medicine, and for a wide variety of reasons we’ve decided that medicine needs to be based in science. Physical therapy can only argue for legitimacy in the healthcare sphere if it can be proven a cost-efficient therapy. That means it must be based in our post-modern science of efficiency, and hence we are forced to run RCTs.

The medical reasoning breaks down when it comes to weight lifting. A lot of the biggest names in the science-based lifting community are obsessed with hypertrophy, the fancy scientific word for increased muscle size. While it’s true that to be a strength athlete you need to have big muscles, most of these guys are selling programs for aesthetics. Dudes want to grow their muscles because looking jacked builds their self-esteem. The sport of hypertrophy, bodybuilding, is competitive body dysmorphia. Bodybuilding is an astonishingly unhealthy sport. It involves taking ungodly doses of performance-enhancing drugs, alternating binge eating with starvation, and walking around at dangerously low body fat levels. The pro athletes in this sport die at rates far higher than football players. It’s a mess. There is no good health-related reason for you to look like a modern bodybuilder.

But perhaps the universal desire of perfect aesthetics is a core part of why science is so alluring. Not everyone wants to be able to play 10 over 11 polyrhythms, but everyone wants to look hot. And since it’s so universal, the nerds want a way to stick it to the jocks and claim a masculine domain that hadn’t originally been theirs. The authority of science gives the nerds an institutional leg up in a world where all men want to stake their claim. Science-based training is to the gym as the analytics department is to professional sports teams.

However, when it comes to the strength sports, the science takes you about as far as the analytics takes a football team. Strength sports are not as quantitative as they look. There’s no optimal answer for any person to follow to become a championship Olympic weightlifter, even though the goal of that sport is to get the sum of two numbers as high as possible. Working hard, resting, and eating get you 80% of the way there. Science can’t fill in the rest. If you want to do heavy clean and jerks and snatches, you have to show up and do them.

Subscribe now

By Ben Recht

Authors: Maximilian Limmer, Nils M. Kriege

The graph edit distance generalizes several well-known NP-hard problems and is therefore NP-hard itself. However, the relationship between the considered graph class, the edit cost function, and the resulting computational complexity is not well understood. We investigate this interplay by revisiting polynomial-time reductions from the literature, which reduce subgraph isomorphism and maximum common induced subgraph to the graph edit distance. For these classical problems, a sharp distinction between NP-hard and polynomial-time solvable cases is known, and we make the implications for the complexity of the graph edit distance explicit. We establish a graph-class-preserving correspondence between the maximum common edge subgraph and graph edit distance under a specific cost function, both in labeled and unlabeled graphs. In the unlabeled setting, the maximum common edge subgraph problem is polynomial-time solvable when one graph is a path and the other is a tree. In contrast, for labeled graphs, we prove that both the maximum common edge subgraph and the graph edit distance remain NP-hard, even when both graphs are paths.

Authors: Holger Spakowski

The domatic number dom(G) of a graph G is the maximum number of dominating sets in a partition of its vertex set. A graph is domatically critical if deleting any edge lowers its domatic number. We determine the complexity of recognizing domatically critical graphs both when the domatic number is prescribed and when it is unrestricted. The problems DomCrit_1 and DomCrit_2 are polynomial-time decidable; in particular, DomCrit_2 consists precisely of the nonempty disjoint unions of nontrivial stars. In contrast, for every fixed integer k >= 3, the problem DomCrit_k is DP-complete under polynomial-time many-one reductions. The hardness proof at target value three uses a switch construction that reduces from edge-minimal 3-uncolorability and controls the effect of deleting every edge of the constructed graph. Clique addition then lifts the target-three result to every larger fixed target value. For the unrestricted recognition problem, we prove DP-hardness and membership in Theta_2^p.

Authors: Armen Karakashian, Itay Hen

We challenge the notion that a stoquastic binary governs fundamental computational boundaries in quantum computing and classical simulation of quantum systems. We argue that vanishing geometric phase (VGP), a geometric condition on the Hamiltonian's transition graph, more adequately captures these boundaries. To distinguish VGP from stoquasticity, we construct VGP 3-local Hamiltonians that are formally hard to stoquastize, yet belong to a family admitting polynomial-time recognition of the VGP property. Without constructing a stoquastizing unitary, we prove that the local Hamiltonian problem is $\mathsf{StoqMA}$-complete under the promise that the input Hamiltonian has VGP, and that a frustration-free variant is in $\mathsf{MA}$ under the same promise. We use this result to argue that non-VGP is necessary for any claimed adiabatic advantage justified by escaping the $\mathsf{StoqMA}$ regime. Further, we identify natural settings where the VGP property can be recognized in polynomial time. In contrast, we show that recognition of VGP is $\mathsf{PSPACE}$-complete in general for geometrically local Hamiltonians. Our results show that the computational boundaries $\mathsf{MA} \subseteq \mathsf{StoqMA} \subseteq \mathsf{QMA}$ traditionally attributed to stoquasticity are better understood as boundaries between vanishing and non-vanishing geometric phase structure.

Authors: Julian Christoph Brinkmann, Anand Srivastav

In this paper, we present new polynomial-time algorithms for determining the winner of the unbiased triangle game played on the edge set of general graphs. To that end, we propose to view the game through the edge-triangle incidence graph instead of the standard hypergraph model. We identify a necessary and sufficient winning condition for Maker in terms of the edge-triangle incidence graph and show that winning strategies achieving this condition as fast as possible play monotonically in the sense that they only consider monotonically decreasing connected subgraphs of the edge-triangle incidence graph. We give three different algorithms for different classes of graphs. For general graphs $G$, the outcome of the unbiased triangle game can be decided in time $\mathcal{O}(n+m^{3.5})=\mathcal{O}(n^7)$. This significantly improves on the $\mathcal{O}(n^{16})$ algorithm implied by the work of Galliot, Gravier and Sivignon (arXiv 2022). For graphs $G$ which contain $K_4$, the complete graph on four vertices, as a subgraph and whose edge-triangle incidence graph is connected, the winner can be decided in time $\mathcal{O}(n+\min\{n^{ω+1},m^2\})=\mathcal{O}(n^{ω+1})$, where $ω<2.372$ is the exponent of matrix multiplication (Alman et. al., SODA 2025). For graphs $G$ whose edge-triangle incidence graph is a cactus graph, i.e. all its cycles are edge-disjoint, the winner can be decided in time $\mathcal{O}(n+m^{1.5})=\mathcal{O}(n^3)$. Such $G$ are $K_4$-free. The algorithms for the special cases are based on novel structural characterizations of Maker's win for each graph class. We also give a linear time reduction from triangle detection to deciding the unbiased triangle game.

Authors: Mikhail Babin

A finite closure system on a finite set $U$ is a family of subsets that contains $U$ and is closed under intersections. It can be specified in two elementary ways: an implicational specification lists rules $A \to b$ and consists of all $X \subseteq U$ satisfying every rule, while an intersection specification lists subsets $M_1, \ldots, M_t$ and consists of all intersections of subfamilies of that list. We ask whether one specification of each kind defines the same family. This question has remained open in several guises for about thirty years: Khardon (1995) showed that translating between Horn formulas and their characteristic models is equivalent to deciding completeness of a proposed list of characteristic models, leaving the exact complexity open; at ISAAC 2025, enumerating irreducible closed sets from implications was still described as "widely open," even for acyclic convex geometries; closely related questions concerned pseudo-intents and the Duquenne-Guigues basis in Formal Concept Analysis, and functional dependencies and Armstrong relations in databases. We prove that the equivalence test is coNP-complete. Hardness holds for acyclic implications with premises of size at most three, even when every listed subset is correct and none can be removed without changing the closure system generated by the list; the hard part is deciding whether a required set is missing. Unless $P = NP$, the complete canonical lists cannot be generated in time polynomial in the input plus the total output size, even for acyclic convex geometries. Through standard correspondences, the theorem makes Characteristic Models Identification and FD-Relation Equivalence coNP-complete and rules out output-polynomial algorithms for Horn characteristic models, all pseudo-intents of a given formal context (equivalently, its Duquenne-Guigues basis), and premises of minimum functional-dependency covers.

Authors: William Whistler

A quasi-tree of a connected ribbon graph is a spanning ribbon subgraph with exactly one boundary component; quasi-trees play the role of spanning trees in the topological graph theory of embedded graphs. We prove that counting them is #P-complete under polynomial-time Turing reductions, already for bouquets. The proof identifies every nonempty framed chord diagram, up to natural identifications, with a 4-regular map equipped with a distinguished A-trail, in such a way that quasi-trees correspond to A-trails, whose counting is #P-complete by a theorem of Ge and Štefankovič. Through the framed Cohn-Lempel equality the count is also an interlace-polynomial evaluation - $q(H;2,1)$, the number of full-rank induced subgraphs of the looped circle graph $H$ of the diagram - placing it on the line $y=1$ left open in the complexity classification of Bläser and Hoffmann; a cloning argument then makes every fixed rational point of that line, other than the trivial $(1,1)$, #P-hard on looped circle graphs, even when a framed chord representation is supplied. On the tractable side, the same GF(2) model yields short proofs of the known determinantal cases: for orientable ribbon graphs the count is a determinant, essentially the Matrix-Quasi-tree Theorem of Merino, Moffatt and Noble, proved here via Bouchet's principal unimodularity, and for bouquets with exactly one non-orientable loop it is a sum of two orientable determinants, equivalent by a rank-one determinant identity to the determinant formula of Deng, Jin and Yan.

Authors: Lance Kennedy, Hossein Amiri, Yueyang Liu, Riyang Bao, Hanqi Chen, Mohammad Hashemi, Ruochen Kong, Xiaotong Liu, Joon-Seok Kim, Shengpu Tang, Liang Zhao, Andreas Züfle

Detecting staypoints from raw trajectory data is fundamental to numerous spatial computing applications. This process transforms raw numeric sequences of geolocations into semantically meaningful locations, such as homes, workplaces, or restaurants. Despite its importance for semantic trajectory analysis, staypoint detection lacks standard benchmarks, and existing algorithms have never been systematically evaluated. This gap persists because no publicly available datasets provide both raw individual trajectories and ground-truth staypoint annotations. This benchmark paper addresses this limitation with two key contributions: (1) we introduce 16 large-scale simulated datasets capturing thousands of agents with annotated staypoints across varying trajectory noise levels, and (2) we evaluate nine staypoint detection algorithms-including both state-of-the-art and novel methods-to analyze their robustness to noise. Our evaluation reveals that existing state-of-the-art algorithms perform poorly under realistic noise conditions. Conversely, our proposed unsupervised methods yield substantial improvements, while supervised approaches drastically outperform existing baselines. While these results are very promising, these datasets and methods are only meant as starting points for future research in staypoint detection.

Authors: Robin Whitty

Given a simple polygon we aim to find the equation of the straight line which bisects the area of the polygon in a given direction. Additionally, we would like to vary this direction with minimal additional calculation. We provide a solution in the case where the polygon is `bisection-convex', meaning that any straight line bisecting the area of the polygon contains exactly two points on the boundary of the polygon.

Authors: Isaac M. Hair, George Z. Li, Jason Li, Junkai Zhang

We consider the single-source shortest paths problem on a directed graph with real-valued (possibly negative) edge weights and solve this problem in $m^{1+o(1)}$ time.

Authors: Isaac M. Hair, George Z. Li, Jason Li, Junkai Zhang

We revisit the single-source shortest paths (SSSP) problem on directed graphs with nonnegative real weights and give a deterministic parallel algorithm with $O(n^{1+o(1)}t^2 + m^{1+o(1)})$ work and $\tilde{O}(n/t)$ span, for any $t \in [1, n]$. This matches (up to subpolynomial factors) the tradeoff due to [Shi and Spencer '99] for undirected graphs with nonnegative real weights.