Theory of Computing Report

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

Authors: John N. Bray, Henrik Bäärnhielm

We present a black box algorithm that constructs standard generators for the Suzuki groups $Sz(q)$, where $q = 2^{2m+1}$ for some $m > 0$. The algorithm is one-sided Monte Carlo, with no false positives. We also present a black box algorithm that performs constructive membership testing in $Sz(q)$, and writes an element as a straight line program in the standard generators. Finally, we give a presentation for $Sz(q)$ that is efficient to verify. The algorithms have been implemented in the computer algebra system Magma.

Authors: Charalampos Platanos, Thanos Tolias

In Online Sorting, we are given an array $A$ of $n$ initially empty cells. At each time step $t\in[n]$, an element $x_t\in[0,1]$ arrives and must be placed irrevocably into an empty cell, without knowledge of future arrivals. The objective is to minimize the sum of absolute differences between elements assigned to adjacent cells. The problem has been studied under both adversarial and stochastic input models. For adversarial sequences, Aamand, Abrahamsen, Beretta, and Kleist (SODA'23) gave a tight $O\sqrt n)$-competitive algorithm, fully resolving the worst-case setting. For stochastic sequences, in which the elements are drawn i.i.d.\ from $U[0,1]$, Hu (SODA'26) gave an $\log n\cdot 2^{O(\log^* n)}$-competitive algorithm in expectation and proved an $Ω(\log n)$ lower bound, while Kalavas, Platanos, and Tolias (STACS'26) gave an $O(\log^2 n)$-competitive algorithm with high probability. Very recently, Hermansen (ESA'26) closed the remaining gap by designing an $O(\log n)$-competitive algorithm in expectation. In this work, we study Random-Order Online Sorting, a model interpolating between the adversarial and stochastic settings, that was posed as a challenging open question by Hermansen (ESA'26). Here, the input is a multiset chosen adversarially, but its elements arrive in uniformly random order. We take a different point of view by solving the problem in rank space, and prove an $O(\log^2 n)$-competitive algorithm with high probability, matching the state-of-the-art high probability guarantee for the stochastic setting in this more general model. We also study a multidimensional generalization, which we call Random-Order Online TSP, and obtain an $O(\log^3 n)$-competitive algorithm with high probability.

Authors: Sharma V. Thankachan

The suffix array ($\SA$) and inverse suffix array ($\ISA$) are fundamental data structures in string algorithms. Given a text of length $n$ over an integer alphabet of size $σ$, explicitly storing these structures requires $Θ(n\log n)$ bits, motivating compressed representations that approach the information-theoretic minimum of $n\logσ$ bits. Two landmark solutions are the FM-index, which achieves succinct space and supports $\SA$ and $\ISA$ queries in roughly logarithmic time, and the Compressed Suffix Array (CSA), which uses $O(n\logσ)$ bits and answers both queries in $O(\log_σ^εn)$ time. Nearly all subsequent compressed indexes, including entropy-compressed and repetitiveness-aware variants, support $\SA$ and $\ISA$ using essentially the same techniques, leading to similar space--time trade-offs. This raises a fundamental question: under the same asymptotic space bound, do $\SA$ and $\ISA$ have the same inherent query complexity? We provide evidence that this symmetry is not intrinsic. Under an $O(n\logσ)$-bit space bound, we show that $\SA$ queries are unlikely to admit $\log^{o(1)} n$ query time, suggesting that improving the classical CSA bound would require a major breakthrough. In contrast, we present a new encoding supporting $\ISA$ queries in $O(τ+\log\log n/\log\logσ)$ time using $(1+1/τ+o(1))n\logσ$ bits, for any $τ\ge1$. Our main insight is that the $\LF$-mapping, traditionally implemented using the Burrows--Wheeler Transform, can be adapted to support $\ISA$ queries directly from the packed text, eliminating the need to store the BWT while achieving substantially faster query times.

Authors: Ron Zadicario, Tova Milo

Result diversification is crucial for generating informative, non-redundant data summaries and query outputs. Although its various formulations have been extensively studied across an array of data-driven disciplines, existing methods fail to address the privacy concerns that arise when the underlying data is sensitive. In this work, we initiate the study of result diversification under differential privacy, focusing on the max-sum diversification (MSD) problem, a widely adopted model with the objective of maximizing a linear combination of a submodular function, quantifying relevance, and the sum of pairwise distances between selected items, quantifying diversity. We propose differentially private algorithms for MSD under both cardinality and matroid constraints, achieving nearly optimal utility guarantees. At the same time, we design more efficient algorithms that maintain strong guarantees. Notably, the proposed algorithms are faster than existing non-private methods, making them appealing even in non-private settings. Experimental evaluations on real-world datasets demonstrate that the proposed approach achieves utility comparable to that of non-private baselines even under strong privacy guarantees, and significantly improves execution times for cardinality constraints.

Authors: Toluwanimi O. Odemuyiwa, Serban D. Porumbescu, Muhammad Osama, Joel S. Emer, John D. Owens

We propose a principled approach to reasoning about various graph algorithm implementations. We leverage the extended general Einsum notation (EDGE) which allows us to factor complexity along four axes: algebraic manipulation, mapping, format, and low-level implementations. Using breadth-first search (BFS) as a driving example and case study, we apply our methodology to explore over 90 variations across 26 categories of optimization choices for our GPU-based implementations. In addition to showing that our approach is general enough to represent previously discovered algorithmic techniques such as the pull variant of BFS, we discover novel variants that lead to geomean performance benefits ranging from 1.2x to 1.7x over the best Gunrock baseline variation for graphs with mid- to high- normalized degree variance.

Authors: Rong Fu, Yongtai Liu, Xiaowen Ma, Wangyu Wu, Long Zhang, Hongbo Zhang, Yangchen Zeng, Hoi Leong Lee, Hao Zhang

We study degeneracy guided list compression for greedy graph coloring when graph structure is available before colors are sampled. Our exposure calibrated ordering framework assigns each vertex an independent uniform list according to its backward neighborhood in a color independent order. Its certified instantiation, Profiled Structure Aware Asymmetric Palette Sparsification, or P-SAPST, reverses a minimum degree removal sequence and obtains every backward exposure from the removal profile. For each fixed profile, we characterize the exact local budget required by independent uniform lists under history robust greedy recovery. The profile yields linear list volume on high degree forests and on a core fringe family where reciprocal rank allocation requires Theta(n log^2 n) sampled colors. Exact conflict expectation, concentration, and a dense exposure barrier complete the theoretical description. The evaluation contains 40,320 runs over SAPBench and two SNAP networks. At the theorem scale, P-SAPST reduces mean list size by 47.6 percent relative to calibrated APST while attaining 99.8 percent observed greedy success. P-SAPST Lite replaces peeling with a degree order and provides a lower latency order choice within the same framework. On stress graphs with 250,000 vertices and up to 1,251,868 edges, Lite obtains a payload ratio of 0.865, while calibrated APST obtains 7.886. On email Enron, the corresponding ratios are 0.193 and 5.814. Compression is strongest on hub dominated and power law graphs and disappears near the dense exposure barrier. The method complements edge oblivious streaming APST by addressing an offline regime in which structural plans can be reused.

Authors: Keren Zhu

Large language models may make precise but dormant algorithmic problems practical to revisit, and may expose new paths toward fundamental ones. We demonstrate this possibility through Prim-Dijkstra routing, a classic VLSI problem whose terminal-only Manhattan complexity remained open despite decades of practical work. We prove weak NP-completeness, derive a continuous cost-radius tradeoff with a balanced (2,2) guarantee, and build HP-RCRST, a height-partition-based multi-mode solver. On 28 development instances, its stronger modes Pareto-dominate the published-method union on 23 and tie on five. The case shows how conflicting conjectures, counterexamples, formal checks, and implementation can reopen neglected questions. Code and reproducibility materials are available at https://github.com/CODA-Team/hp-rcrst.

Authors: Niu Yannian, Han Song, Wang Minmei

Multi-set membership queries are ubiquitous in networking and database systems. Current solutions force a difficult compromise: hash tables guarantee correctness but suffer from high memory footprints, while filter-based approaches optimize space at the cost of probabilistic errors. In this paper, we propose STEM2, a fast and space-efficient data structure that achieves 100% query accuracy and can support dynamic key updates for multi-set membership queries. STEM2 utilizes a balanced binary tree architecture where each non-leaf node incorporates a novel Exact Binary Set Separator (XBSS) to partition keys into two disjoint groups. A key innovation of our design is a minimized hashing scheme that requires only two hash computations per key lookup, significantly reducing computational overhead. Additionally, STEM2 separates the control plane and the data plane: the control plane handles construction and dynamic updates, while the data plane is dedicated to serving efficient membership queries. Extensive experiments show that STEM2 achieves over 120 million operations per second (Mops) in lookup throughput, outperforming the state-of-the-art Coloring Embedder by 20% and the Ludo hashing by up to 21.6X, while maintaining compact memory cost and exact correctness.

Authors: Rémy Belmonte, Juan Pablo Bravo, Noleen Köhler, Haiko Müller

We study variants of graph colouring with parity constraints. More specifically, we consider $q$-colourings $c\colon V(G)\rightarrow \{1,\dots,q\}$ of a graph $G$ where, for every vertex $v\in V(G)$, the number of neighbours $w$ of $v$ with $c(w)=c(v)$ is restricted to be odd, even, positive, zero or a combination thereof. For every colour $i\neq c(v)$ the number of neighbours $w$ of $v$ with $c(w)=i$ is restricted by a constraint of similar type. Many known colouring problems such as proper colouring, defective colouring, exact defective colouring, odd colouring, and strong odd colouring can be described within this framework of constraining graph colourings, and therefore considering variants constitutes a natural generalisation of known colouring problems. We provide a comprehensive study of the computational complexity of different combinations of constraints involving parity.

Smoothed Analysis is Bullshit*

Last week we organized a workshop at Schloss Dagstuhl on analysis of algorithms beyond the worst case. Here, beyond worst-case^[1] refers to a pressing tension in the scientific study of algorithms: theory is often useless shit.^[2] I mean this with love.

Theoretical computer science has given us many great pieces of theory, predominantly following the classic modeling paradigm called 'worst-case analysis'. Under this paradigm, we specify a single algorithm (or class of algorithms) with mathematical precision and rigor, along with the set of valid inputs. A worst-case analysis then attempts to find the worst-possible performance of the algorithm (in time, memory, or output solution quality). We describe that worst-case performance as a function of the size of the input, often counted as the number of bits or number of numbers. In some parts of computation, whether modern or undergrad curriculum, worst-case analysis is a useful paradigm for understanding your algorithm's performance.

Other parts of computation spit in the face of theory. Paging, SAT, graph coloring, linear programming, mixed-integer linear programming, clustering, traveling salesperson. Each of these works better, is solveable faster, or returns better quality solutions than what worst-case analysis would predict. SAT and MILP are NP-hard in theory. In practice they are easy.^[3] The simplex method for linear programming runs in exponential time under worst-case analysis. In practice its blazingly fast.^[4]

We need different approaches, new modeling strategies. And the problem is, mathematicians like us are poorly equipped to think critically about what we do. Nobody believes in average-case analysis. But also smoothed analysis is kinda bullshit,^[5] even if people still believe in it.^[6]

So let me describe you how I got radicalized against smoothed analysis, so that you too can stop falling for its cursed allure. These arguments mostly come from discussions with my PhD student Eleon Bach. They were published in this paper but here on the blog I can write with more zest.

Hypersparsity

Real-world linear program constraint matrices have a property called hypersparsity. For one, that means that the matrix is very sparse: 99.99% of matrix entries are zero (and thus not even stored in memory). Only 0.01% is non-zero. This is important for real-world codes: the simplex method is memory-bound, so if you destroy all zeroes then your running time blows up. The instances we study in smoothed analysis have no sparsity: with probability 1, all entries of the matrix are non-zero. This is bad.

The second part of hypersparsity is the structure of the non-zeroes: most non-zero matrix entries share a handful of values. Most entries are probably equal to 1, but even among the remaining entries there are only a limited number of unique values. This is a problem for smoothed analysis: almost surely, all entries have distinct values. This is bad.

Worst-case instances are sparse and stable

So smoothed instances do not look like real-world instances for sparsity reasons. This is unlike worst-case instances: the Klee-Minty cubes are hypersparse. Looking purely at the patterns in the constraint matrix, one would assume that KM-cubes are more like real-world instances than smoothed analysis instances are.

You may think "could we do smoothed analysis in a sparse way? We could only perturb the non-zero entries in the input data". This thought puts you in good company: Spielman and Teng propose the same thing. Too bad its a dead end. If you choose the parameters right, then the behavior of the KM-cube is stable under constant-magnitude zero-preserving perturbations. That is, the zero-preserving smoothed complexity of the simplex method (with the most-negative reduced cost pivot rule) is exponential.

Even imprecise numbers are precise

Next issue. Some linear programs do contain numbers that 'look inaccurate': numbers like 15.79081 or 43.15593. Maybe those numbers contain some type of independent Gaussian noise to make them look like that? I don't think so. If you allow yourself to change such 'ugly' numbers by as little as 0.01% then the previously-optimal solution will violate some constraints by as much as 50%. This holds for 13 out of 90 NETLIB instances, quite a large amount.^[7] Feel free to disagree with my interpretation, but I personally think that means that the 'ugly random-looking numbers' have important non-trivial relations between eachother. Hence they cannot be changed in isolation. This would violate a key assumption of smoothed analysis: that all random noise entries are independently distributed.

Singular matrices should stay singular

In a typical LP, not every maximal square submatrix is a basis. Some submatrices are singular. Singular submatrices are good: the simplex method will never pivot to them, so they don't cost any extra time. If you add small random Gaussian noise to your constraint matrix, then every submatrix will be basic. This is a disaster: what used to be a singular submatrix (good) is now a basic submatrix with high condition number (very bad).

If you read your favorite solver's user manual or talk to their helpdesk, you will learn this: please write your input data in maximum precision. Use integer numbers if you can, or 64-bit floats if you must. Do not use 32-bit floats, for they are too imprecise and that imprecision hurts solver performance. One reason that is given for this advice is what I say above: low precision may cause nominally singular submatrices to pass the threshold and become basic. A basis with high condition number will ruin your numerical stability and your simplex method performance along with it.

So: smoothed analysis says 'more noise (less precision) is good'. The user manual says 'more precision is good'. Smoothed analysis is wrong, the user manual is correct.

Philosophical incoherence

Final issue. In smoothed analysis, we assume that there is an idealized piece of input data which gets perturbed by random noise added after its formulation. What is this noise? Where does it come from? What does it model?

Some people suggest the noise as modeling floating-point inaccuracy, implicitly advocating for a value of \(\sigma = 2^{-53} \approx 10^{-16}\) as per IEEE 754. Other people speak of the noise as modeling measurement error, which would endorse a value of \(\sigma \approx 10^{-2}\). This disagreement is ridiculous. Imagine admitting this to a real scientist, like a physicist: "yeah we have a theoretical understanding, except we don't agree what our model models and our opinions about the central parameter's value differ by 14 order of magnitude." Not a good look.

Smoothed analysis is trash

So that's the deal, those are the arguments that radicalized me against smoothed analysis for LP. Its instances don't pass the most basic sanity checks, its conclusions seem to contradict the user manual ground truth, and the whole theory lacks a coherent philosophical grounding.

This all leaves a crucial question: how should one analyze an algorithm when worst-case analysis fails? At the workshop we had talks from different subfields, and people had different partial answers to this question. Some people went deeper into the theory, other people proposed to engage more with computational experiments in one form or another. Some people thought that a good analysis method would be broadly applicable, others were happy to exploit more problem-specific features. This is an exciting set of questions and a lively research field.

For the simplex method, by far the best current analysis framework is by-the-book analysis, our new baby (STOC '26). It is not perfect but it is a big step up from all that came before.

I am curious to see where all the workshop's topics and participants will go next. Although none of us has all the answers, we are all making progress.

[1]	For an overview of items falling under this umbrella, take a look at this book edited by Tim Roughgarden and use password 'BWCA_CUP' to open it.

[2]

I am not pulling any punches today. The literature doesn't capture people's feelings, and normally you can only observe those by attending an IRL event. However, events like this workshop, broadly scoped on BWCA in its entirety, happen only once every 12 years and only permit 25 attendees. As such, you probably don't often hear the spicier takes. This blog post collects a few more critical notes, some mine and some taken from others. Don't get discouraged by any of this criticism: it applies to everyone's work, including my own. I built my career on doing smoothed analysis of the simplex method, so mostly I am throwing in my own windows here. The point is to reflect critically, and sometimes that is easier when we don't mince our words. Anyway, see for yourself what you can get out of this blog post: use it to help develop your own sense of critical evaluation. Nobody trains us mathematicians how to do this, and we gotta learn somehow.

[3]

Crafting hard instances is not difficult. But somehow, we have reams and reams of practical real-world instances which are easy to solve. Electronics designs get verified bug-free by showing that huge boolean formulas are UNSAT. Swathes of global shipping and manufacturing get planned by solving MIPs. 10k variables is tiny for these solvers, but should be huge for any true believer in NP-hardness.

[4]

For the simplex method, crafting hard instances is difficult. What I mean by that is, crafting numerically unstable instances is easy and your solver will struggle with those. But instances without numerical problems, but which do exhibit super-polynomial running times on real physical IEEE 754 compliant computer hardware? Constructing those is an open research problem.

[5]

At least it is trash for the context of studying linear programming, as I will lay out in this blog post. For other algorithms and applications areas, these arguments may not apply. Maybe for your problem, smoothed analysis is fine. I invite you to consider this matter critically in the context of the algorithm you study.

[6]

People really did believe in this theory. Spielman and Teng's Gödel Prize citation claims that smoothed analysis "provides a new rigorous framework for explaining the practical success of algorithms". Those are big claims: not only is it rigorous (mathematically? scientifically? who knows), but it provides actual explanation!

[7]	These facts are taken from this book, although the authors give a very different interpretation of what these same facts mean.

Last week in Zócalo Public Square, I wrote a piece on optimizing diets, adapted from the second chapter of The Irrational Decision.1 It’s one of my favorite stories in the book. Though it predates computers by several years, it’s a microcosm of the computer age and fits in seamlessly with today’s oddly dominant online culture of wellness optimizers. In a spat with USDA nutritionist Hazel Stiebeling about what sorts of recommendations are acceptable for the government to publish, the prickly economist George Stigler solved a complicated tableau by hand to find a rather unpalatable “minimum cost subsistence diet” of wheat flour and navy beans. Go read the essay, and then come back here and read a few fun addenda.

I tell the story of the diet problem in most of my book talks, and I always receive fun feedback. Jeff Linderoth sent me a hilarious reflection by George Dantzig, the inventor of linear programming, on his apparently futile attempt to find his own optimal diet to lose weight. Though Dantzig knew Stigler’s optimization problem had nothing but absurd and disgusting solutions, he figured he was adept enough at building linear programming models to patch Stigler’s simplistic assumptions with appropriate shaping of objectives and constraints. He used spare cycles of the IBM 701 at the RAND Corporation to churn out ever more innovative meal plans. But he kept getting bizarre recommendations, like drinking gallons of vinegar or consuming mass quantities of bouillon. He diligently refined the diet over the course of a week before his wife, Anne, got fed up:

Speaking firmly so that I would know who was boss, she said, “I have been studying the various menus the computer has been generating. There are some good ideas there that I can use. I’ll put you on MY diet. She did and I lost 22 pounds.

Steve Stigler—not only an amazing statistician and historian but also George’s son—attended my talk at the University of Chicago. Steve told me how this paper made its way out of academia and into national newspapers, ruffling feathers from coast to coast. George would receive angry letters scolding him about how “this is no way to feed growing boys.” I thought it was pretty clear from reading the original paper that George didn’t think anyone should try to eat his diet. He was trying to prove a point about the impossibility of optimal diets and the paternalistic nature of government recommendations. But people ended up taking him literally. Papers that start as sardonic jokes can surprisingly take on a life of their own.

Stigler’s paper is part of a broader conversation about the scope of government policy. The idea of a computable government was central to economic discussions during the Great Depression and throughout the Second World War. Experts and government officials argued about what is optimal, what can be planned centrally, what individuals should be allowed to navigate for themselves, and what sort of information is beneficial and which is coercive. These debates strongly influenced von Neumann, as you can see in his and Morgenstern’s engagement with contemporary economic debate in the introduction to their revolutionary book on game theory. For another fun example of the people building computers closely interacting with the people designing policy, here’s a 1958 photograph of a sharply dressed Claude Shannon at the Center for Advanced Study in the Behavioral Sciences at Stanford, taken by George Stigler on Steve Stigler’s camera.2

The diet debate also raises the uncomfortable central theme in Elizabeth Popp Berman’s book, Thinking Like an Economist. Everyone across the political spectrum is arguing about efficiency, as if that’s the only thing the government should think about. Left-wing technocrats (aka the Democrats) apply this sort of economic thinking to the utility of the population. Right-wing policymakers (aka Republicans) apply economic thinking to the utility of the individuals in that population. No matter their politics, everyone is thinking like an economist. The valence of the arguments and the parties making those arguments remain uncannily similar today.

Given the grand scale and ambition of the federal government, USDA dietary guidelines should be a fourth-order concern. But there’s something about worrying about what we should eat that galvanizes the popular imagination. It’s fun to walk through the original arguments about what should be in the food pyramid, especially given the weird steak-centric geometry being pushed by RFK’s cuckoo version of HHS. A steak every day sure sounds more appealing than a bean pie.

Subscribe now

By Ben Recht

The Department of Computer Science at RPTU at campus Kaiserslautern invites applications for a professorship in Algorithms and Complexity. The position is a tenured professorship at the salary level W2 equivalent to an associate professorship, and is to be filled as soon as possible.

Website: https://www.cs.rptu.de/en/forschung/stellen/w2-ak/
Email: lin@cs.uni-kl.de

By shacharlovett

Authors: Álvaro Gutiérrez, Christian Ikenmeyer, Greta Panova

We study the class $\#\mathsf{L}$ of functions counting accepting paths of non-deterministic log-space Turing machines and construct methods to prove containment in $\#\mathsf{L}$. We prove that a large number of classical combinatorial and number theoretic functions belong to this class: classical functions from enumerative combinatorics (multinomial coefficients, Catalan numbers, linear extensions of trees, Stirling numbers, etc), algebraic combinatorics (number of standard Young tableaux, etc), discrete geometry, number theoretic functions, representation theoretic multiplicities in a large class of cases. We show that $\mathrm{GL}_2$-plethysm coefficients of bounded length outer partition can be counted by log$^2$-space polytime verifiers. We pose numerous questions and conjectures on $\#\mathsf{L}$ containment and its generalizations, that suggest venues for conditionally disproving $\#\mathsf{P}$-completeness. While studying which combinatorial functions are in $\#\mathsf{P}$ provides a formal way of (dis)proving the existence of combinatorial interpretations, the lower class $\#\mathsf{L}$ serves as an analogue for functions computable in polynomial time.

Authors: Anand Kumar Narayanan

Raz proposed a program to prove arithmetic circuit lower bounds through the explicit construction of elusive functions. These are polynomial maps from a low dimensional space to a high dimensional ambient space whose image is contained in no subvariety of low complexity. Here, complexity is prescribed in terms of the dimension and degree of parametric maps into the ambient space defining the subvariety. Elusive functions are abundant: finding explicit ones with parameters typical of generic polynomial maps implies Valiant's hypothesis that VP$\neq$VNP. But no such construction is known. Raz devised elusive functions with weaker parameters to derive explicit degree d polynomials in n variables requiring superlinear circuit size at depth $d=o(\log n)$. We present a new method to analyse and construct elusive functions, with coordinate maps restricted to monomials. To prove elusiveness, we identify a hitting set of points, each a tuple of roots of unity coupled based on the exponents of the monomial maps. Using Chebotarev's theorem on roots of unity, we show that for every low complexity subvariety, the function evaluated at some point in the hitting set eludes it. For this strategy to work, it suffices that the iterated sumset of a certain set of numbers (derived from the exponents) expands exponentially. We thus reduce open explicit construction problems in elusive functions to purely additive combinatorial ones, whose resolutions imply as yet unknown lower bounds. Informed by iterated sumset expansion, we devise new elusive functions. We construct explicit elusive curves of exponential degree, resolving an open problem posed by Garg, Makam, Oliveira, and Wigderson as a testament to the difficulty of elusiveness proofs. We improve Raz's superlinear bound quadratically (with circuit size to input size ratio as the metric) below $o(\log n/\log\log n)$ depths.

Authors: Gal Yehuda

We construct quantitative almost laws for $SO(3)$. More precisely, there exist a constant $c>0$ and non-trivial words $W_n\in F_2$ such that, for every $A,B\in SO(3)$, \[ \|W_n(A,B)-I\| \le \exp\!\left(-c |W_n|^δ\right), \] where $δ=\log_2(x_0)=0.879146\ldots$ and $x_0>1$ is the real root of $x^3=x^2+x+1$. This improves the exponent $\log_2\varphi$ obtained from Elkasapy's lower-central-series construction. As an application, we show how this result improves the word-length threshold in Kuperberg's Solovay--Kitaev algorithm for single-qubit gates.

Authors: Tamal K. Dey, Tao Hou, Dmitriy Morozov

Computation of zigzag persistence has progressed in recent years, with results showing that complexities of many problems closely align with those in the non-zigzag setting. The major efficiency gap now lies in the updating of zigzag representatives. In this paper, we propose efficient algorithms for updating zigzag representatives based on a recent algorithm for extracting zigzag representatives from a $R=DV$ decomposition of a constructed non-zigzag. The main difficulty for designing our update algorithms lies in the adjacency change occurring in two operations that elongate or shorten a filtration. Despite the adjacency change, we find that the update can still be done efficiently in quadratic time.

Authors: Mark de Berg, Ulrike Schmidt-Kraepelin, Andree-Ovidiu Stef

Computing a minimum-weight perfect matching for a point set $P$ in Euclidean space is a classic geometric optimization problem. We consider the problem in a dynamic setting, where pairs of points may be added to or removed from the set $P$. Our focus is on maintaining an approximately optimal solution without making too many changes to the solution. More precisely, we are interested in $k$-stable algorithms, which change at most $k$ edges in the matching after each update to the set $P$. In other words, we consider an online setting (with insertions and deletions) with bounded recourse. We study trade-offs between the stability of the algorithm and the approximation ratio of the maintained solution for point sets in $\mathbb{R}^1$. First, we present an $O(\sqrt{n})$-stable algorithm that maintains a $2$-approximation, which we show to be optimal among all algorithms with sublinear stability. Second, we prove that any $o(\log n)$-stable algorithm has unbounded approximation ratio. Our lower bounds hold even in the insertion-only case, while our algorithm works in the fully dynamic case. Moreover, our lower bounds also hold for the bipartite variant of the problem.

Authors: Žiga Sajovic, Dejan Knez

Mesh CSG output is consumed in floating point: however exact the computation, every emitted coordinate is materialised -- rounded to a representable position -- and the next stage can observe crossings and orderings the exact result never had. Only index-based topology survives materialisation. We keep it exact: within the build, the arrangement's radial structure is ordered by exact predicates on the original input planes -- exact without exact constructions -- and where a decision spans faces, the intended answer is recovered by topological aggregation: a majority vote over the disagreeing geometric observations within their topological unit. We compute the arrangement locally with integer-exact predicates, every stage a graph problem on graphs it never explicitly constructs. Pairwise intersections are classified into five canonical types (VV, VE, VF, EE, EF), each cut face is arranged in its own plane, and a two-level identity keeps the result consistent across faces with no global structure. The arrangement and its domain partition are built once and queried arbitrarily often: a boolean of any arity is a per-domain bit test, volumetric regions read straight off the partition, and open surfaces -- declared as oriented sheets -- cut volumes through the same algebra. The method is implemented in the header-only trueform library, in C++ with Python and TypeScript bindings. Compared to prior art, it produces valid, watertight output while running up to two orders of magnitude faster, and stays interactive in the browser.

Authors: Ronald Katende

For an explicitly represented finite empirical model, deciding whether the contextual fraction is strictly below one is NP-complete, while the standard exact linear program has one column for every global assignment. We identify a permutation-transport class in which this global problem collapses to a fixed-point calculation. Let a connected permutation gain graph act on a finite state set $O$, let $H \leq{ \rm Sym}(O)$ be its holonomy subgroup, let $F = {\rm Fix}(H)$, and let $p$ be an $H$-invariant root distribution. For the induced empirical model, \[ {\rm NCF}(e)=p(F),\qquad {\rm CF}(e)=1-p(F). \] Consequently, compatibility, $F$, and ${\rm CF}(e)$ are computable in $O(|O|(|V|+|E|))$ arithmetic and table operations. For every finite simple $2$-edge-connected graph, any deterministic exact algorithm in the explicit permutation-table query model requires at least $(|O|-1)|E|$ probes in the worst case, making the dependence on the input tables optimal up to constant factors. With a fixed spanning tree, chord insertions and deletions require $O(|O|)$ worst-case time, or time proportional to the moved-set representation, while compatibility and contextual-fraction queries take $O(1)$ time. Finally, for common-marginal realizable binary constraint languages, the support threshold ${\rm CF} < 1$ is polynomial-time equivalent to the associated finite-domain constraint-satisfaction problem and therefore inherits the Bulatov--Zhuk dichotomy. The results identify a query-optimal and dynamically maintainable tractability island inside the general contextual-fraction problem.

Authors: Naoki Kitamura, Seitaro Kawaguchi, Yuya Terashima, Taisuke Izumi

We study the Connected Components Reconfiguration problem (CCR), in which connected components on a graph are transformed according to a specified reconfiguration rule. CCR generalizes Independent Set Reconfiguration by treating tokens not as individual vertices but as connected components of prescribed sizes. Among the variants of CCR, we focus on the component-jumping model, denoted by \CCRCJ. Nakahata.\ introduced this problem and showed that the decision problem for \CCRCJ~can be solved in $O(n^2)$ time on path graphs for arbitrary component sizes, and in polynomial time on chordal graphs when all connected components have the same size. However, the complexity on chordal graphs under a multiset size constraint remained open. In this paper, we study this multiset version of \CCRCJ~from both complexity-theoretic and algorithmic viewpoints. First, we prove that \CCRCJ~is NP-hard even on caterpillar graphs, which is a very restricted subclass of trees and chordal graphs minimally above path graphs. This result immediately implies NP-hardness for chordal graphs under a multiset size constraint, thereby resolving Nakahata's open problem on chordal graphs under multiset size constraints. Second, we revisit \CCRCJ~on path graphs. We improve the previous $O(n^2)$-time algorithm for the decision problem by giving an $O(n\log n)$-time decision algorithm. Moreover, when the instance has sufficiently large empty space, we show that there exists a reconfiguration sequence of length $O(n\log n)$, and such a sequence can be output efficiently.