Theory of Computing Report

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.)

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.

Authors: Toranosuke Kokai, Rin Saito, Tatsuhiro Suga, Takahiro Suzuki, Yuma Tamura

In the \textsc{Odd Domination} problem, given a graph $G$ and a positive integer $k$, the task is to determine whether there exists a vertex subset $D$ of $G$ such that the closed neighborhood of each vertex in $G$ contains an odd number of vertices from $D$. In this paper, we investigate the computational complexity of the problem. When parameterized by the solution size $k$, we establish W[1]-hardness on some restricted graphs and a sharp boundary between fixed-parameter tractability and W[1]-hardness with respect to the girth of the input graph. Then, we address the problem when parameterized by several structural graph parameters. Furthermore, we investigate the parameterized complexity of \textsc{Parity Domination}, which is a generalization of \textsc{Odd Domination}.

Authors: Tom Janßen

We consider a continuous facility location problem called $δ$-Dispersion. For some fixed $δ> 0$, the goal is to place as many facilities on a graph as possible with pairwise distance at least $δ$. The facilities may be located on the vertices of the graph, or the interior of the edges. This problem can be interpreted as a continuous version of the well-known Independent Set problem. Its approximation behavior is very similar for large values of $δ$. Notably, Grigoriev et al. [Algorithmica 21] showed that $δ$-Dispersion is solvable in polynomial time when $δ= 1/x$ or $δ= 2/x$ for a natural number $x$ and NP-hard otherwise. We study the approximability of $δ$-Dispersion depending on the value of $δ$. For $δ> 2$, we show poly-APX-hardness, while for all $δ< 2$ that are not solvable in polynomial time we show APX-hardness. Thanks to a translation theorem for $δ$ due to Hartmann et al. [MFCS 22], we may focus our attention for approximation algorithms on the intervals $(2/3 , 1)$ and $(1, 2)$. We provide several approximation algorithms with an approximation factor approaching $1$ as $δ$ approaches one of the interval boundaries. Surprisingly, the behavior as $δ$ approaches $2/3$ from above is different: As our hardness reductions reveal, it is impossible (under standard complexity-theoretic assumptions) to construct an approximation algorithm with an approximation factor approaching $1$ as $δ$ approaches $2/3$ from above.

Authors: Chenglin Fan, Jingcheng Liu, Pan Peng, Hangyu Xu, Zongrui Zou

We study the problem of releasing a synthetic graph that approximates the sizes of all cuts of an input graph under edge-level differential privacy. If one insists on purely additive error, the optimal worst-case error is $\widetildeΘ(n^{3/2})$. If one allows a small multiplicative slack, an information-theoretic exponential-time mechanism achieves nearly linear additive error, but the best known polynomial-time algorithms have substantially larger error. We give a polynomial-time $(\varepsilon,δ)$-differentially private algorithm which, for every $n$-vertex unweighted graph $G$, outputs a non-negative weighted synthetic graph $\widetilde G$ such that, with high probability, every cut $S\subseteq V(G)$ satisfies \[ |w_G(S)-w_{\widetilde G}(S)| \le γw_G(S)+\widetilde O_{\varepsilon,δ,γ}(n^{13/12+o(1)}). \] This improves the previous polynomial-time worst-case bound $\widetilde O(n^{5/4+o(1)})$ of Aamand et al. (ICML 2025) for mixed multiplicative/additive private cut approximation. The main technical ingredient is a new set of private spectral primitives for bounded-degree graphs, one of them gives spectral error $\widetilde O_δ((nd)^{1/4}/\sqrt\varepsilon)$ in estimating the graph Laplacian for graphs of maximum degree $d$, being the first to beat the standard $\min\{2d,\widetilde O_δ(\sqrt{n}/\varepsilon)\}$ baseline in the high-degree regime. We further develop a primitive with a sharper error dependence on $n$ and $d$ for the downstream cut approximation. Combined with a new edge-sensitive terminal cut oracle with additive error $\widetilde O(n+(n^2M)^{1/3})$ on graphs with $M$ edges, this yields the final worst-case $\widetilde O(n^{13/12+o(1)})$ private cut-release error.

Authors: Seungbum Jo, Dominik Köppl

Given an array of $n$ real numbers, the maximum segment sum (MSS) problem is to find a contiguous subarray that has the largest sum. While the MSS problem can be solved optimally with Kadane's algorithm in $O(n)$ time, the study of its indexing version spawned new extensions such as (a) retrieving the MSS after subtracting a query offset parameter for all array entries or (b) retrieving the MSS for arbitrary query ranges. We here study the combination of both problems (a) and (b), which requires retrieving the MSS for arbitrary query ranges after subtracting a query offset parameter for all array entries. For that, we present an index whose query time is only slower than the best known for (a) by a factor of $O(\log n)$. In detail, our index uses $O(n \log n)$ space, supports queries in $O(\log^2 n)$ time, and can be constructed in $O(n \log^3 n)$ time. More generally, for every integer $d$ with $1\le d\le\lceil\log_2 n\rceil$, we give an $O(dn)$-space index with $O(dn^{1/d}\log n)$ query time; in particular, for every fixed $\varepsilon>0$, we obtain linear space and $O(n^\varepsilon\log n)$ query time. As side results, we obtain the same time-space trade-off in terms of the number of runs of a run-length encoded input, deduce a solution for (a) that works in run-length compressed space and time, and prove a tight $Θ(n^{2/3})$ bound on the number of non-compatible offsets for binary arrays. Finally, we give supportive lower bounds for our query problem, showing that there is only a polylogarithmic gap of improvement left.

Authors: Manoj Gupta, Mrigankashekhar Shandilya

Given an undirected, unweighted graph $G$, we aim to compute a 2-approximation of all-pairs shortest paths (APSP). This problem admits a natural lower bound of $Ω(n^2)$ since the output size is $Θ(n^2)$. A central goal in this area is to achieve a running time of $O(n^2)$. Dor, Halperin, and Zwick (FOCS 1996, SICOMP 2001) designed an algorithm with a running time of $\tilde{O}(n^2)$ that guarantees a 2-approximation only for pairs at a distance of at least $O(\log n)$. Recently, Gupta (FOCS 2025) improved this bound, handling all pairs at a distance of at least $O(\log \log n)$. We nearly resolve this problem. We design a randomized algorithm that runs in $\tilde{O}(n^2)$ time and, with high probability, guarantees a 2-approximation for all pairs at distance at least $c$, where $c \ge 0$ is a constant. Unlike the above two results, which were purely combinatorial, our algorithm combines combinatorial techniques with fast matrix multiplication (FMM).

Authors: Petr Chmel, Bernhard Haeupler, Richard Hladík, Michal Koucký, Antti Roeyskoe, Václav Rozhoň, Ondřej Sladký, Robert E. Tarjan

Sleator and Tarjan [JACM, 1985] conjectured that splay trees are dynamically optimal -- that on every access sequence, they perform within a constant factor of the optimal offline dynamic binary search tree. Despite four decades of work, no $o(\log n)$ competitive ratio was known. We prove that splay trees are $O(\log\log n \cdot \log^2\log\log n)=\tilde{O}(\log\log n)$-competitive.

We construct an $\varepsilon$-error PRG for permutation read-once branching programs of length $n$ and width $w$ with seed length $$ O\left((\log w+\log(1/\varepsilon))\cdot \log n\right). $$ This gives an exponential improvement in the dependence on $w$ compared with the constructions of De (CCC 2011) and Steinke (ECCC 2012). Compared with the work of Braverman, Rao, Raz, and Yehudayoff (FOCS 2010; SICOMP 2014), which applies more generally to regular branching programs and already achieves the optimal dependence on $w$, our result improves the dependence on the length $n$, attaining the optimal logarithmic dependence. The generator itself is the classical INW PRG of Impagliazzo, Nisan, and Wigderson (STOC 1994). We show that, for permutation branching programs, the INW generator can be instantiated with expanders whose degrees are polynomial in $w$ and $1/\varepsilon$ and, crucially, independent of $n$. To prove this, we analyze error propagation using program-dependent seminorms tailored to the branching program at hand. These seminorms build on the weight function introduced by Braverman et al. The key point is that, when measured in these adapted seminorms, the error does not accumulate throughout the recursion. Since our analysis relies only on the spectral expansion of the underlying expanders, our seed length tightly matches the recent lower bound for spectral analyses of the INW generator due to Hoza, Pyne, and Vadhan (Algorithmica 2024).

Authors: Yunbei Xu

A randomized algorithm may terminate almost surely even though exceptional random tapes make it run forever. This paper studies the survival tail, the Kolmogorov complexity of one such tape, and the Hausdorff dimension of all of them. For each $s>0$ at which the powered repair matrices commute, the main theorem bounds $\sum_wP[w]^s$ over surviving prefixes $w$, uniformly over deterministic nonanticipating selectors. The case $s=1$ controls termination; the full family gives weak-source and dimension bounds. The source powers contain information absent even from the ordinary repair kernel and the complete stopping-time law. Under one common finite tape source, two overlapping disagreement-repair rules on a four-vertex path have the same ordinary kernels and the same stopping-time law for every selector, yet their nontermination dimensions can be arbitrarily close to zero and one. At one common source-power level, the same dominated tape source makes one rule run forever but gives the other an exponential stopping tail. The separation is caused by action labels that produce the same state transition and are therefore invisible at power one. For bounded-dependence $k$-SAT, conditional block min-entropy above the trace-growth threshold gives exponential termination, and the effective dimension of an individual infinite run is bounded by the trace growth induced by the clauses repaired infinitely often. Tree formulas asymptotically attain the maximum-degree dimension and global source bounds, while clique formulas attain the graph-specific one-step threshold in the stated regime. An exact backward likelihood identity complements these setwise results with tail and coding bounds for each run.

Authors: Arman Adibi, Piotr Krysta

Estimating entropy from samples is fundamental in information theory and property testing. Shannon entropy measures average uncertainty and can be estimated to constant additive accuracy over a $k$-symbol alphabet using $Θ(k/\log k)$ samples. Min-entropy depends only on the most likely symbol. Both are special cases of order-$α$ R'{e}nyi entropy, $H_α$. We characterize the sample complexity of estimating min-entropy and R'{e}nyi entropy for $k$ and integer $α>1$; our lower bounds also hold for noninteger $α\ge1.001$. We prove that min-entropy estimation to constant additive accuracy has sample complexity $Θ(k\log k)$. The upper bound uses the largest empirical frequency and concentration via dyadic grouping. The matching lower bound hides a slightly heavier symbol at a uniformly random location. Thus, min-entropy requires $Θ(\log^2 k)$ more samples than Shannon entropy and corrects a previously stated $Θ(k/\log k)$ characterization. For every integer $2\leα\le c_0\log k$, we prove the matching fixed-accuracy bound $Θ_{c_0}(αk^{1-1/α})$. Previous results gave $Ω_α(k^{1-1/α})$ for fixed integer $α>1$ and $O_{c_0}(α^2k^{1-1/α})$ for all integer $α>1$. Our upper bound analyzes an unbiased falling-factorial estimator based on $α$-way collisions, while a hidden-heavy-coordinate construction gives the matching lower bound and shows that the factor $α$ is unavoidable. For every real $1.001\leα\le c_0\log k$, we prove the uniform lower bound $Ω_{c_0}(αk^{1-1/α})$. Finally, since $0\le H_α(p)-H_\infty(p)\le\log k/(α-1)$, min-entropy uniformly approximates $H_α$ when $α$ is a sufficiently large multiple of $\log k$. Combining this reduction with our min-entropy bounds gives $Θ_\varepsilon(k\log k)$ sample complexity in the high-order regime.

Authors: Zhou He, T. C. E. Cheng, Jichang Dong

We study continuous planar facility location in which a demand point's captured value decays with distance, with the per-point decay scale varying across points. This heterogeneity is ubiquitous yet underexploited, and one nearest-facility objective unifies decay, clustering, and median goals, containing k-means, the Weber/p-median problem, and maximum covering as special cases. We make four contributions. (i) A tractability classification: the discrete objective is always monotone submodular, so the (1-1/e) greedy guarantee holds regardless of decay shape or heterogeneity, and the continuous cooperative objective is concave if and only if the decay is concave in distance; the clip max(0,d) in common coverage specifications is what destroys concavity, and the classification is tight. (ii) An exact discrete method: the candidate-discretized maximum-cover MIP has an empirically tight LP relaxation (~0% gap) and is solved by branch-and-bound in seconds for n <= 500. (iii) A force-as-gradient / large-neighborhood-search heuristic, within 0.5% of the discrete optimum, that outperforms the (1-1/e) greedy, Cooper-style alternating location-allocation, particle swarm optimization, and weighted k-means (30/30 per-instance wins at K=30, p<10^-9) and is competitive with bespoke solvers on k-means, Weber/p-median, and shape-demand instances. (iv) A real-world study: on 592,667 urban-delivery orders, ignoring the calibrated decay variation loses up to 9.7% of captured demand and relocates facilities by up to 37% of the map; a retail dataset calibrates the decay as exponential with scale R ~ 1.4 km.

Authors: Gil Cohen, Dean Doron, Noam Goldgraber

We construct an $\varepsilon$-error PRG for permutation read-once branching programs of length $n$ and width $w$ with seed length \[ O\left((\log w+\log(1/\varepsilon))\cdot \log n\right). \] This gives an exponential improvement in the dependence on $w$ compared with the constructions of De (CCC 2011) and Steinke (ECCC 2012). Compared with the work of Braverman, Rao, Raz, and Yehudayoff (FOCS 2010; SICOMP 2014), which applies more generally to regular branching programs and already achieves the optimal dependence on $w$, our result improves the dependence on the length $n$, attaining the optimal logarithmic dependence. The generator itself is the classical INW PRG of Impagliazzo, Nisan, and Wigderson (STOC 1994). We show that, for permutation branching programs, the INW generator can be instantiated with expanders whose degrees are polynomial in $w$ and $1/\varepsilon$ and, crucially, independent of $n$. To prove this, we analyze error propagation using program-dependent seminorms tailored to the branching program at hand. These seminorms build on the weight function introduced by Braverman et al. The key point is that, when measured in these adapted seminorms, the error does not accumulate throughout the recursion. Since our analysis relies only on the spectral expansion of the underlying expanders, our seed length tightly matches the recent lower bound for spectral analyses of the INW generator due to Hoza, Pyne, and Vadhan (Algorithmica 2024).

Authors: Che Cheng, Daniel Mock, Peter Rossmanith

We extend the algorithmic framework of progressive exploration [Fabiański et al., STACS 2019], which yields simple, yet surprisingly general and efficient parameterized algorithms for Dominating Set, Independent Set, and some of their variants. While they identified stability and the Helly property as necessary for their approach, we show that -- with a simple change -- in the case of Dominating Set, one can get rid of the stability requirement. This yields a fixed-parameter tractable algorithm on exactly those graph classes which do not contain long co-matchings or double-ladders as semi-induced subgraphs. Lifting one of these two restrictions makes Dominating Set W[1]-hard on these classes. Our algorithm generalizes results on weakly $γ$-closed graphs, and results from Sparsity theory, e.g., nowhere dense and biclique-free classes. At the same time, we match the time complexity of the previously known algorithms on those classes. We demonstrate that this technique can easily be applied to the Distance-$r$ Dominating Set and the Set Cover problem.

Authors: Simon D. Fink, Matthias Pfretzschner, Ignaz Rutter, Marie Diana Sieper

We consider the combination of the two constrained planarity problems Level- and Clustered Planarity. Traditionally, level-planar drawings with convex clusters have been studied in this setting. Fink et al. (EuroCG 2024) recently introduced a different way of combining level- and clustered planarity by mimicking a classic characterization of clustered planarity in the level-planar setting: The problem (y-)monotone Clustered Level Planarity (mCLP) seeks a level-planar drawing in which it is possible to augment each cluster with edges that do not cross cluster boundaries so that it becomes connected while maintaining level-planarity. This is in line with previous research on clustered planarity that poses certain requirements on the augmentation edges that make each cluster connected, e.g., that they form a path. Fink et al. (EuroCG 2024) showed that mCLP is NP-complete even for biconnected single-source graphs and instances with a constant number of levels and clusters. We further classify the parameterized complexity of the mCLP problem by, on the one hand, showing hardness even for instances that consist of a forest with trees of bounded size, no isolated vertices, and a small constant number of either clusters or levels. This excludes fixed-parameter tractability for almost all graph-structural parameters, except for vertex cover, even in conjunction with the number of clusters. We complement this by showing fixed-parameter tractability when parameterizing by the vertex cover number and the number of clusters. A major obstacle is the fact that mCLP is non-hereditary, i.e., subinstances of yes-instances may be no-instances and vice versa, which makes it challenging to apply usual reduction techniques.

Authors: Harish Chandramouleeswaran, Prajakta Nimbhorkar

The existence of allocations of indivisible goods that are simultaneously fair (envy-free up to one item (EF1)) and efficient (Pareto optimal (PO)) when agents have monotone submodular valuations has been a longstanding open problem. We settle this question negatively by giving an example with two agents where no allocation is simultaneously EF1 and PO. We also show that determining the existence of such allocations is NP-hard for monotone submodular valuations. Our example uses (unweighted) coverage valuations, which is a strict subclass of monotone submodular valuations. Since EF1+PO allocations are known to always exist for additive valuations via the maximization of Nash Social Welfare (Caragiannis et al. (ACM TEAC 2019)), and for matroid-rank valuations (Benabbou et al. (ACM TEAC 2021)), nonexistence was known only for monotone subadditive valuations (Caragiannis et al. (ACM TEAC 2019)). Our work moves the nonexistence frontier to unweighted coverage valuations. We also show that the example we designed for goods also proves nonexistence of EF1+PO in general, for chores with unweighted coverage costs, by interpreting the valuations as disutilities.

Authors: Zhiyi Huang, Qinpei Lou, Tao Xiao

Mixture-of-Experts (MoE) models route each token to only a few expert networks, distributing the serving load across experts whose popularity shifts over time. A serving system must therefore dynamically decide how many GPUs to assign to each expert, trading off service latency against the cost of reconfiguring the assignment. We introduce a formal model of MoE Serving and initiate a principled study of online and offline algorithms for it. Our main result is a polynomial-time $O(\sqrt{\log k})$-competitive online algorithm, where $k$ is the number of GPUs beyond one per expert. We complement it with a matching $Ω(\sqrt{\log k})$ barrier for the online dual problem underlying our analysis. In the offline setting, we give a constant-factor approximation, show that MoE Serving is NP-hard, and rule out an FPTAS assuming ETH.

Authors: Romain Cosson, Jingwei Li, Alexander Lindermayr, Jens Schlöter

Nonclairvoyant scheduling is a fundamental online model in which processing times are initially unknown to the scheduler. Unfortunately, for important objectives such as total completion time and makespan, worst-case analysis yields pessimistic guarantees: every nonclairvoyant algorithm has a competitive ratio of at least $2$ for these objectives. Recent work introduced $\varepsilon$-clairvoyance, where a scheduler receives a signal once an $\varepsilon$-fraction of a job remains (FOCS'25, NeurIPS'25). This model avoids giving the algorithm a priori predictions as done in learning-augmented algorithms, a practice that is often hard to justify in practice. However, existing algorithms and analyses rely crucially on signal times being precise, an assumption hardly justifiable in applications such as task profiling. We introduce stochastic clairvoyance, a beyond-worst-case model in which each job emits a randomly timed signal during its execution, drawn from a distribution over its processing length. For this model, we design new online scheduling algorithms whose competitive ratios are strictly below $2$ for minimizing total completion time and makespan. On the technical side, we prove a new black-box theorem that converts bounds on expected pairwise job delays into competitive guarantees via a continuous amortized charging argument. Our results show that stochastic clairvoyance is not merely a curiosity: it yields robust improvements across different scheduling objectives and machine environments. More broadly, stochastic clairvoyance suggests a new direction in beyond-worst-case analysis for online algorithms, and builds a bridge between learning-augmented algorithms and stochastic information models.

Authors: Jiří Fink, Petr Hladík, Arturo Merino, Ondřej Mička, Torsten Mütze

Recently, Merino and Mütze (FOCS'23+SICOMP'24) presented an algorithm for computing a Hamilton path on the skeleton of any 0/1-polytope ${\rm conv}(X)$, where $X\subseteq\{0,1\}^n$. The algorithm uses as a black box an algorithm for solving the classical linear optimization problem $\min\{w\cdot x\mid x\in X\}$ for some weight vector $w\in\mathbb{R}^n$. The resulting delay per visited vertex on the Hamilton path is only by a $\log n$ factor larger than the time to solve one instance of the optimization algorithm. In this paper, we make the Hamilton path algorithm simpler and faster. Namely, we obtain an amortized delay that is only by a constant factor larger than the running time of the optimization algorithm, thus removing the $\log n$ factor. As concrete results, this yields improved algorithms for generating bases and independent sets in a matroid, spanning trees, forests, matchings and maximum matchings in a graph, vertex covers, minimum vertex covers, independent sets and maximum independent sets in a bipartite graph, and antichains, maximum antichains and ideals in a poset. All of these listings correspond to Hamilton paths on the corresponding polytopes. Furthermore, we obtain an $\mathcal{O}(t_{\rm LP})$ amortized delay algorithm for the vertex enumeration problem on 0/1-polytopes $\{x\in\mathbb{R}^n\mid Ax\leq b\}$, where $A\in \mathbb{R}^{m\times n}$ and $b\in\mathbb{R}^m$, and $t_{\rm LP}$ is the time needed to solve the linear program $\min\{w\cdot x\mid Ax\leq b\}$. This improves upon the $\mathcal{O}(t_{\rm LP} \log n)$ delay algorithm of Merino and Mütze, and the previous $\mathcal{O}(t_{\rm LP}\,n)$ delay algorithm of Bussieck and Lübbecke from 1998.

Authors: Andrew Krapivin, William Kuszmaul, Jolyne Wang

Linear probing hash tables classically use a \emph{greedy} insertion strategy, placing a key $u$ in the first available position out of $h(u), h(u) + 1, h(u) + 2, \ldots$. If the hash table is filled to $1 - 1/x$ full, this results in $Θ(x^{2})$ worst-case expected insertion time. In this note, we show that there is a simple \emph{non-greedy} insertion strategy that does better, and without requiring elements to be reordered within the table over time. Given $x$ in advance, the strategy is able to bring the worst-case expected insertion time down to $O(x \log x)$.

Authors: Vanessa Kosoy

In a previous paper, we began the study of sequence prediction algorithms adapted to stringological word complexity measures. One measure we considered was left-to-right (most-significant-digit-first) automaticity. Here, we show a statistically and computationally efficient algorithm adapted to the ``dual'' right-to-left (least-significant-digit-first) automaticity, which turns out to be substantially different for our purpose. We also demonstrate a prediction algorithm for a more expressive measure that we call ``arithmetic repetition complexity''. In particular, the latter can be used for predicting the so-called mix-automatic sequences.