Theory of Computing Report

Authors: Xiaoyu Li, Andi Han, Dai Shi, Jiaojiao Jiang, Junbin Gao

Generation in the limit guarantees eventual generation for every countable collection of infinite languages in the model of Kleinberg and Mullainathan [KM24], while closure dimension characterizes stronger information-theoretic guarantees [RLT25]. Neither restricts per-output computation. The cumulative-mistake objective in mistake-bounded generation makes finite failure prefixes quantitative [KPR26], and a per-output query budget exposes their computational source. Polynomial-time algorithms are known for parities, conjunctions, and monotone functions with polynomially many maxterms [JKO26]. We ask whether information-theoretic ease can coexist with bounded-access computational hardness. Relative to a random oracle $H$, we answer yes by constructing a countable collection $C^\star$ of infinite languages with closure dimension zero. Almost surely on the same $H$, an unbounded generator makes zero mistakes on every target and every complete distinct enumeration. Yet, writing $λ$ for the target-seed length, every fixed uniform generator $G$ with polynomially many oracle queries in $λ$ and the output index $i$ has a constant $c_G>0$ such that, for every sufficiently large $λ$, some target incurs more than $2^{c_Gλ}$ expected mistakes within its first $2(\lceil 2^{c_Gλ}\rceil+1)$ canonical outputs. Infinite accidental agreement enables exhaustive search; sparse queries hide fresh target values. Thus, in the random-oracle model, zero-mistake information-theoretic generation coexists with a generator-dependent exponential lower bound on worst-case expected mistakes under polynomial-query access.

Authors: Xiaoyu Li, Andi Han, Dai Shi, Jiaojiao Jiang, Junbin Gao

Generation in the limit guarantees eventual generation for every countable collection of infinite languages in the model of Kleinberg and Mullainathan [KM24], while closure dimension characterizes stronger information-theoretic guarantees [RLT25]. Neither restricts per-output computation. The cumulative-mistake objective in mistake-bounded generation makes finite failure prefixes quantitative [KPR26], and a per-output query budget exposes their computational source. Polynomial-time algorithms are known for parities, conjunctions, and monotone functions with polynomially many maxterms [JKO26]. We ask whether information-theoretic ease can coexist with bounded-access computational hardness. Relative to a random oracle $H$, we answer yes by constructing a countable collection $C^\star$ of infinite languages with closure dimension zero. Almost surely on the same $H$, an unbounded generator makes zero mistakes on every target and every complete distinct enumeration. Yet, writing $λ$ for the target-seed length, every fixed uniform generator $G$ with polynomially many oracle queries in $λ$ and the output index $i$ has a constant $c_G>0$ such that, for every sufficiently large $λ$, some target incurs more than $2^{c_Gλ}$ expected mistakes within its first $2(\lceil 2^{c_Gλ}\rceil+1)$ canonical outputs. Infinite accidental agreement enables exhaustive search; sparse queries hide fresh target values. Thus, in the random-oracle model, zero-mistake information-theoretic generation coexists with a generator-dependent exponential lower bound on worst-case expected mistakes under polynomial-query access.

Thursday, August 06 2026, 00:00

Step Recursion: A Three-Parameter Refinement of the Grzegorczyk Hierarchy

Authors: Kirill Osipov

We introduce bounded step recursion and a three-parameter hierarchy refining the Grzegorczyk hierarchy. For a strictly increasing function $\varphi:\mathbb N\to\mathbb N$ with $\varphi(x)\ge x+1$, its generalized inverse $$ρ_\varphi(y)=\min\{z:\varphi(z)\ge y\}$$ replaces the ordinary predecessor and generates the descent schedule $y,ρ_\varphi(y),ρ_\varphi^{[2]}(y),\ldots,0$. From a Grzegorczyk basis $B_m$, composition, and bounded step recursion with step $g_n^{[l]}$, we define classes $H^m_{n,l}$, where $m$ measures the initial-function strength, $n$ selects a growth scale, and $l$ fixes the stride through its canonical layers. For all $n,n'\ge2$, we obtain an exact criterion for $H^a_{n,l}\subseteq H^b_{n',l'}$. Below horizontal collapse, fixed strides are ordered by reverse divisibility: inclusion at equal row is governed by $l'\mid l$, not by the numerical order of $l$ and $l'$. All fixed strides collapse from initial basis $m=n$, and the common class equals the ordinary bounded-recursion class $E^m$ exactly from $m=n+1$. Positive inclusions use exact-depth simulations; separations use a direct piecewise-monotone trace theorem and a canonical-zone invariant for selected dependency chains. The doubling row $g_1(x)=2x+1$ is exceptional at low bases. We prove $H^m_{1,l}=E^m$ for all $m\ge3$, construct the first vertical bridge at basis $2$, and show that every fixed-arity function in $H^2_{1,l}$ is binary polynomial-time computable, with $H^2_{1,l}\subsetneq FP$. Equality $H^2_{1,l}=E^2$ would imply $P=NP$.

Authors: Kirill Osipov

We introduce bounded step recursion and a three-parameter hierarchy refining the Grzegorczyk hierarchy. For a strictly increasing function $\varphi:\mathbb N\to\mathbb N$ with $\varphi(x)\ge x+1$, its generalized inverse $$ρ_\varphi(y)=\min\{z:\varphi(z)\ge y\}$$ replaces the ordinary predecessor and generates the descent schedule $y,ρ_\varphi(y),ρ_\varphi^{[2]}(y),\ldots,0$. From a Grzegorczyk basis $B_m$, composition, and bounded step recursion with step $g_n^{[l]}$, we define classes $H^m_{n,l}$, where $m$ measures the initial-function strength, $n$ selects a growth scale, and $l$ fixes the stride through its canonical layers. For all $n,n'\ge2$, we obtain an exact criterion for $H^a_{n,l}\subseteq H^b_{n',l'}$. Below horizontal collapse, fixed strides are ordered by reverse divisibility: inclusion at equal row is governed by $l'\mid l$, not by the numerical order of $l$ and $l'$. All fixed strides collapse from initial basis $m=n$, and the common class equals the ordinary bounded-recursion class $E^m$ exactly from $m=n+1$. Positive inclusions use exact-depth simulations; separations use a direct piecewise-monotone trace theorem and a canonical-zone invariant for selected dependency chains. The doubling row $g_1(x)=2x+1$ is exceptional at low bases. We prove $H^m_{1,l}=E^m$ for all $m\ge3$, construct the first vertical bridge at basis $2$, and show that every fixed-arity function in $H^2_{1,l}$ is binary polynomial-time computable, with $H^2_{1,l}\subsetneq FP$. Equality $H^2_{1,l}=E^2$ would imply $P=NP$.

Thursday, August 06 2026, 00:00

Even more properties of parity based bit-counting complexity classes

Authors: Tayfun Pay

We study several additional properties of parity based bit-counting complexity classes ${\bf B_{|0| \oplus}P}$ and ${\bf B_{|1| \oplus}P}$. We first prove that ${\bf MNS}\subseteq{\bf P}^{{\bf B_{|1|\oplus}P}}={\bf P}^{{\bf B_{|0|\oplus}P}}$ and since ${\bf C_=P}={\bf ES}={\bf MNS}$ is already known, we establish that ${\bf C_=P}={\bf ES}={\bf MNS}\subseteq{\bf P}^{{\bf B_{|1|\oplus}P}}={\bf P}^{{\bf B_{|0|\oplus}P}}$. We then prove that ${\bf PP}\subseteq{\bf P}^{{\bf B_{|1|\oplus}P}}$ and ${\bf PP}\subseteq{\bf P}^{{\bf B_{|0|\oplus}P}}$, which consequently yields ${\bf P}^{\bf PP}={\bf P}^{\bf B_{|0|\oplus}P}={\bf P}^{\bf B_{|1|\oplus}P}$. We then demonstrate that the same method can be used to prove ${\bf \# P}\subseteq{\bf FP}^{{\bf B_{|1|\oplus}P}}$ and ${\bf \# P}\subseteq{\bf FP}^{{\bf B_{|0|\oplus}P}}$. We also show that the parity based bit-counting hierarchies contain ${\bf CH}$.

Authors: Tayfun Pay

We study several additional properties of parity based bit-counting complexity classes ${\bf B_{|0| \oplus}P}$ and ${\bf B_{|1| \oplus}P}$. We first prove that ${\bf MNS}\subseteq{\bf P}^{{\bf B_{|1|\oplus}P}}={\bf P}^{{\bf B_{|0|\oplus}P}}$ and since ${\bf C_=P}={\bf ES}={\bf MNS}$ is already known, we establish that ${\bf C_=P}={\bf ES}={\bf MNS}\subseteq{\bf P}^{{\bf B_{|1|\oplus}P}}={\bf P}^{{\bf B_{|0|\oplus}P}}$. We then prove that ${\bf PP}\subseteq{\bf P}^{{\bf B_{|1|\oplus}P}}$ and ${\bf PP}\subseteq{\bf P}^{{\bf B_{|0|\oplus}P}}$, which consequently yields ${\bf P}^{\bf PP}={\bf P}^{\bf B_{|0|\oplus}P}={\bf P}^{\bf B_{|1|\oplus}P}$. We then demonstrate that the same method can be used to prove ${\bf \# P}\subseteq{\bf FP}^{{\bf B_{|1|\oplus}P}}$ and ${\bf \# P}\subseteq{\bf FP}^{{\bf B_{|0|\oplus}P}}$. We also show that the parity based bit-counting hierarchies contain ${\bf CH}$.

Thursday, August 06 2026, 00:00

Zero-error expectation equals amortized query complexity

Authors: Daiki Suruga

This paper investigates the direct sum question for expected randomized and distributional query complexity. Our main result gives an exact characterization of the amortized expected randomized query complexity. For any total relation $f$ and any error tolerance $\varepsilon \in [0,1]$, we prove \[ \lim_{n \to \infty} \frac{\overline{R}_\varepsilon(f^n)}{n} = (1 - \varepsilon) \overline{R}_0(f). \] Thus the amortization converts bounded-error into zero error with the exact multiplicative factor $1-\varepsilon$. We also prove corresponding liminf/limsup bounds for worst-case randomized and distributional query complexity. These results improve prior direct-sum bounds that were known only up to constant factors or in restricted error regimes, and they resolve an open question posed by Blais and Brody (2019). Additionally for one-sided computation of the function $\operatorname{OR}_n \circ f$, we obtain analogous exact amortized identities for both expected and worst-case cost. As applications, we obtain separations between amortized and single-instance costs, including unbounded separations for distributional complexity and randomized relations, and a quadratic barrier for randomized total functions.

Authors: Daiki Suruga

This paper investigates the direct sum question for expected randomized and distributional query complexity. Our main result gives an exact characterization of the amortized expected randomized query complexity. For any total relation $f$ and any error tolerance $\varepsilon \in [0,1]$, we prove \[ \lim_{n \to \infty} \frac{\overline{R}_\varepsilon(f^n)}{n} = (1 - \varepsilon) \overline{R}_0(f). \] Thus the amortization converts bounded-error into zero error with the exact multiplicative factor $1-\varepsilon$. We also prove corresponding liminf/limsup bounds for worst-case randomized and distributional query complexity. These results improve prior direct-sum bounds that were known only up to constant factors or in restricted error regimes, and they resolve an open question posed by Blais and Brody (2019). Additionally for one-sided computation of the function $\operatorname{OR}_n \circ f$, we obtain analogous exact amortized identities for both expected and worst-case cost. As applications, we obtain separations between amortized and single-instance costs, including unbounded separations for distributional complexity and randomized relations, and a quadratic barrier for randomized total functions.

Thursday, August 06 2026, 00:00

Zero-error information equals amortized communication complexity

Authors: Daiki Suruga

The direct sum problem in computational complexity asks whether solving $n$ independent instances of a computational task inherently requires $n$ times the resources needed to solve a single instance. In this paper, we resolve a central form of the direct sum conjecture in randomized communication complexity. Specifically, we prove that the "amortized expected randomized communication complexity" of any function is exactly equal to its "zero-error information complexity"---a measure of the precise amount of information the communicating parties must reveal about their inputs to compute the function without error. This result also provides a tight characterization of the amortized "worst-case" randomized communication complexity up to a constant factor. To achieve our exact characterization, we introduce a new single-instance protocol embedding equipped with a prefix-verification mechanism to accurately localize global errors. Furthermore, we apply our new structural theorems to the fundamental Set-Disjointness problem. Our resulting exact asymptotic bounds for Set-Disjointness successfully refute a conjecture in DFHL18 regarding its scaling behavior.

Authors: Daiki Suruga

The direct sum problem in computational complexity asks whether solving $n$ independent instances of a computational task inherently requires $n$ times the resources needed to solve a single instance. In this paper, we resolve a central form of the direct sum conjecture in randomized communication complexity. Specifically, we prove that the "amortized expected randomized communication complexity" of any function is exactly equal to its "zero-error information complexity"---a measure of the precise amount of information the communicating parties must reveal about their inputs to compute the function without error. This result also provides a tight characterization of the amortized "worst-case" randomized communication complexity up to a constant factor. To achieve our exact characterization, we introduce a new single-instance protocol embedding equipped with a prefix-verification mechanism to accurately localize global errors. Furthermore, we apply our new structural theorems to the fundamental Set-Disjointness problem. Our resulting exact asymptotic bounds for Set-Disjointness successfully refute a conjecture in DFHL18 regarding its scaling behavior.

Thursday, August 06 2026, 00:00

Fast Thick-Thin Decomposition for Sparse Spanners on Hyperbolic Surfaces

Authors: Sándor Kisfaludi-Bak, Geert van Wordragen

We consider spanners for point sets lying in the hyperbolic plane or on a closed hyperbolic surface with the restriction that spanner edges are not allowed to cross. This is a natural generalization of non-crossing Euclidean spanners. Thus, the resulting spanner graphs are embedded in the hyperbolic plane or on the hyperbolic surface. As our main contribution, we show that there are sparse $(1+\varepsilon)$-spanners for these problems when we are allowed to use Steiner points: - on the hyperbolic plane we get a non-crossing Steiner $(1+\varepsilon)$-spanner with $\mathcal{O}(n / \varepsilon^2)$ edges, - on hyperbolic surfaces of genus $g$ we get a Steiner $(1+\varepsilon)$-spanner with $\mathcal{O}(n / \varepsilon^{3/2} + g/\varepsilon^2)$ non-crossing edges, or with $\mathcal{O}(n / \sqrt{\varepsilon} + g/\varepsilon)$ edges that are allowed to cross. In particular, our spanners on surfaces have sparsity with linear dependence on $g$, rather than the easier-to-attain exponential dependence, and the terms $n/\varepsilon^{3/2}$ and $n/\sqrt{\varepsilon}$ match the current best Euclidean results for plane and crossing Steiner spanners, respectively. As a corollary of our non-crossing spanner and techniques from the existing literature on light spanners and minor-free TSP, we get an EPTAS for TSP on hyperbolic surfaces. Our surface constructions rely on the thick-thin decomposition, a standard tool for studying hyperbolic surfaces. For convex hyperbolic polygons, we introduce an analogous neck decomposition. We give algorithms that compute the thick-thin decomposition of a genus-$g$ surface in $\mathcal{O}(g^4\log g)$ time and the neck decomposition of an $n$-vertex polygon in $\mathcal{O}(n)$ time.

Authors: Sándor Kisfaludi-Bak, Geert van Wordragen

We consider spanners for point sets lying in the hyperbolic plane or on a closed hyperbolic surface with the restriction that spanner edges are not allowed to cross. This is a natural generalization of non-crossing Euclidean spanners. Thus, the resulting spanner graphs are embedded in the hyperbolic plane or on the hyperbolic surface. As our main contribution, we show that there are sparse $(1+\varepsilon)$-spanners for these problems when we are allowed to use Steiner points: - on the hyperbolic plane we get a non-crossing Steiner $(1+\varepsilon)$-spanner with $\mathcal{O}(n / \varepsilon^2)$ edges, - on hyperbolic surfaces of genus $g$ we get a Steiner $(1+\varepsilon)$-spanner with $\mathcal{O}(n / \varepsilon^{3/2} + g/\varepsilon^2)$ non-crossing edges, or with $\mathcal{O}(n / \sqrt{\varepsilon} + g/\varepsilon)$ edges that are allowed to cross. In particular, our spanners on surfaces have sparsity with linear dependence on $g$, rather than the easier-to-attain exponential dependence, and the terms $n/\varepsilon^{3/2}$ and $n/\sqrt{\varepsilon}$ match the current best Euclidean results for plane and crossing Steiner spanners, respectively. As a corollary of our non-crossing spanner and techniques from the existing literature on light spanners and minor-free TSP, we get an EPTAS for TSP on hyperbolic surfaces. Our surface constructions rely on the thick-thin decomposition, a standard tool for studying hyperbolic surfaces. For convex hyperbolic polygons, we introduce an analogous neck decomposition. We give algorithms that compute the thick-thin decomposition of a genus-$g$ surface in $\mathcal{O}(g^4\log g)$ time and the neck decomposition of an $n$-vertex polygon in $\mathcal{O}(n)$ time.

Thursday, August 06 2026, 00:00

Tropical Algebraic Geometry for Neuronal Representations: An Arakelov-Green Measure Based Descriptor for Graph Learning

Authors: Yuyang Zhang, Weihan Xu, Xuehai Zhou, Shucheng Cao, Qihuang Zhang

The quantitative analysis of 3D neuronal morphologies requires capturing both graph topology and spatial geometry. Current message-passing Graph Neural Networks (GNNs) are bounded by the 1-Weisfeiler-Lehman (1-WL) test, limiting their ability to capture cycles induced by spatial proximities. To address this, we propose a training-free geometric prior based on tropical algebraic geometry. We apply the recently established tropical Abel-Jacobi transform and polarization distances to machine learning on tree-structured data. We introduce a structural transformation pipeline, comprising cycle space augmentation and quotient space construction, to convert spatial trees into cyclic metric graphs suitable for embedding into the Tropical Jacobian. Computing exact tropical polarization distances requires solving the NP-Hard Closest Vector Problem (CVP) on integer lattices. Instead of relying on explicit approximations with quantization errors (e.g., Babai's rounding), we adopt a continuous relaxation on the universal cover of the Albanese torus. We show that the discrete Arakelov-Green measure, computed in closed form via the graph Laplacian's generalized inverse, decomposes exactly into the intrinsic path metric minus the unquantized polarization distance on this cover, avoiding integer lattice searches. This metric yields two descriptors: eigenvectors provide node-level structural coordinates, and the permutation-invariant eigenvalue spectrum provides a graph-level signature. On the BREC benchmark, the eigenvector formulation demonstrates expressivity beyond the 1-WL limit. On 3D morphology datasets (ACT-4, JML-4, BIL-6), the spectrum seamlessly integrates into standard architectures (VAEs, GNNs, Tree-LSTMs) without additional trainable parameters, outperforming explicit lattice approximations and improving classification accuracy over existing spatial models.

Authors: Yuyang Zhang, Weihan Xu, Xuehai Zhou, Shucheng Cao, Qihuang Zhang

The quantitative analysis of 3D neuronal morphologies requires capturing both graph topology and spatial geometry. Current message-passing Graph Neural Networks (GNNs) are bounded by the 1-Weisfeiler-Lehman (1-WL) test, limiting their ability to capture cycles induced by spatial proximities. To address this, we propose a training-free geometric prior based on tropical algebraic geometry. We apply the recently established tropical Abel-Jacobi transform and polarization distances to machine learning on tree-structured data. We introduce a structural transformation pipeline, comprising cycle space augmentation and quotient space construction, to convert spatial trees into cyclic metric graphs suitable for embedding into the Tropical Jacobian. Computing exact tropical polarization distances requires solving the NP-Hard Closest Vector Problem (CVP) on integer lattices. Instead of relying on explicit approximations with quantization errors (e.g., Babai's rounding), we adopt a continuous relaxation on the universal cover of the Albanese torus. We show that the discrete Arakelov-Green measure, computed in closed form via the graph Laplacian's generalized inverse, decomposes exactly into the intrinsic path metric minus the unquantized polarization distance on this cover, avoiding integer lattice searches. This metric yields two descriptors: eigenvectors provide node-level structural coordinates, and the permutation-invariant eigenvalue spectrum provides a graph-level signature. On the BREC benchmark, the eigenvector formulation demonstrates expressivity beyond the 1-WL limit. On 3D morphology datasets (ACT-4, JML-4, BIL-6), the spectrum seamlessly integrates into standard architectures (VAEs, GNNs, Tree-LSTMs) without additional trainable parameters, outperforming explicit lattice approximations and improving classification accuracy over existing spatial models.

Thursday, August 06 2026, 00:00

Discrete homology computations by reduction to zero differentials

Authors: Sterling Ebel, Chris Kapulkin, Nathan Kershaw

We develop a new algorithm for computing (persistent) discrete homology of graphs using reduction to zero differentials and active enumeration. This allows us to compute the fourth homology group of the Greene sphere, along with several previously unknown groups. We also show that persistent discrete homology computes faster than simplicial homology of Vietoris-Rips complex in the high-noise non-metric settings, making it a better choice for noisy data sets.

Authors: Sterling Ebel, Chris Kapulkin, Nathan Kershaw

We develop a new algorithm for computing (persistent) discrete homology of graphs using reduction to zero differentials and active enumeration. This allows us to compute the fourth homology group of the Greene sphere, along with several previously unknown groups. We also show that persistent discrete homology computes faster than simplicial homology of Vietoris-Rips complex in the high-noise non-metric settings, making it a better choice for noisy data sets.

Thursday, August 06 2026, 00:00

Efficient Algorithms for the Bottleneck Path Problem in Geometric Graphs

Authors: Matthew J. Katz, Rachel Saban, Micha Sharir

We present efficient algorithms for the bottleneck path problem in two geometric settings that arise naturally in applications: directional-antenna graphs in the plane with antenna angles bounded from below by a constant, and visibility graphs whose vertices lie on or above a 1.5-dimensional terrain, both with Euclidean distances as edge weights. We provide near-linear algorithms for the corresponding decision problems, namely, determining whether the subgraph obtained by retaining all edges with weight at most some threshold ${\bf bn}$ contains a path from $s$ to $t$. We then use the decision procedures to obtain algorithms for the bottleneck path problem that run in $O^*(n^{8/7})$ randomized expected time, where $n$ is the input size and the $O^*(\cdot)$ notation hides subpolynomial factors. Within the same performance bounds, we can also solve the bounded-hop version, in which we only consider $s$-$t$ paths with at most $k$ edges, for a given integer $k < n$.

Authors: Matthew J. Katz, Rachel Saban, Micha Sharir

We present efficient algorithms for the bottleneck path problem in two geometric settings that arise naturally in applications: directional-antenna graphs in the plane with antenna angles bounded from below by a constant, and visibility graphs whose vertices lie on or above a 1.5-dimensional terrain, both with Euclidean distances as edge weights. We provide near-linear algorithms for the corresponding decision problems, namely, determining whether the subgraph obtained by retaining all edges with weight at most some threshold ${\bf bn}$ contains a path from $s$ to $t$. We then use the decision procedures to obtain algorithms for the bottleneck path problem that run in $O^*(n^{8/7})$ randomized expected time, where $n$ is the input size and the $O^*(\cdot)$ notation hides subpolynomial factors. Within the same performance bounds, we can also solve the bounded-hop version, in which we only consider $s$-$t$ paths with at most $k$ edges, for a given integer $k < n$.

Thursday, August 06 2026, 00:00

Cluster Deletion is as Hard to Approximate as Vertex Cover

Authors: Yixin Cao, Ying Xu

Recent breakthroughs in Cluster Editing have motivated attempts to adapt these approaches to obtain better-than-$2$ approximations for Cluster Deletion. We rule out this possibility under the Unique Games Conjecture: Cluster Deletion is NP-hard to approximate within a factor of $2-ε$ for every fixed $ε>0$, matching the known $2$-approximation [Veldt et al., WWW 2018]. Our approximation-preserving reduction from Vertex Cover also implies NP-hardness of approximation within $\sqrt2-ε$. We also show that better-than-$2$ approximations are possible in restricted settings. We close the paper with a brief discussion of the relationship between Cluster Editing and Bad Triangle Transversal. In particular, we give a $31$-vertex graph~$G$ for which the two optimal values differ, answering an open question of Adriaens and Tatti [ICML 2026].

Authors: Yixin Cao, Ying Xu

Recent breakthroughs in Cluster Editing have motivated attempts to adapt these approaches to obtain better-than-$2$ approximations for Cluster Deletion. We rule out this possibility under the Unique Games Conjecture: Cluster Deletion is NP-hard to approximate within a factor of $2-ε$ for every fixed $ε>0$, matching the known $2$-approximation [Veldt et al., WWW 2018]. Our approximation-preserving reduction from Vertex Cover also implies NP-hardness of approximation within $\sqrt2-ε$. We also show that better-than-$2$ approximations are possible in restricted settings. We close the paper with a brief discussion of the relationship between Cluster Editing and Bad Triangle Transversal. In particular, we give a $31$-vertex graph~$G$ for which the two optimal values differ, answering an open question of Adriaens and Tatti [ICML 2026].

Thursday, August 06 2026, 00:00

If it is Good Then Drop it -- a Spiteful Poisson Process for Submodular Maximization

Authors: Ariel Kulik, Thiago Oliveira, Roy Schwartz, Mohit Singh

We study the problem of maximizing a general and not necessarily monotone submodular function subject to a matroid independence constraint. This problem has a rich history, with multiple algorithms using both discrete and continuous methods. Recently, [Ganz-Rozenman, Kulik, Schwartz and Singh STOC `26] presented a novel hybrid approach based on a Poisson process that aims to combine the strengths of both discrete and continuous methods for the special case of the problem where the submodular function is monotone. Our main result is a new Poisson process based hybrid algorithm that works for both non-monotone and monotone submodular functions, achieving an approximation of $ \frac{1}{e}$ for the former and $1-\frac{1}{e}$ for the latter. The algorithm always maintains a feasible set and at random times governed by the Poisson process it performs a single element swap based on a best response set. The new idea is that our algorithm is spiteful as it can purposefully discard an element that is in both the current set and the best response set. Surprisingly, this spiteful step does not harm the approximation our algorithm achieves for monotone submodular functions but is necessary for the non-monotone case. As applications, we obtain fast approximation algorithms for maximizing non-monotone submodular function subject to a general matroid independence constraint as well as faster algorithms for a partition matroid.

Authors: Ariel Kulik, Thiago Oliveira, Roy Schwartz, Mohit Singh

We study the problem of maximizing a general and not necessarily monotone submodular function subject to a matroid independence constraint. This problem has a rich history, with multiple algorithms using both discrete and continuous methods. Recently, [Ganz-Rozenman, Kulik, Schwartz and Singh STOC `26] presented a novel hybrid approach based on a Poisson process that aims to combine the strengths of both discrete and continuous methods for the special case of the problem where the submodular function is monotone. Our main result is a new Poisson process based hybrid algorithm that works for both non-monotone and monotone submodular functions, achieving an approximation of $ \frac{1}{e}$ for the former and $1-\frac{1}{e}$ for the latter. The algorithm always maintains a feasible set and at random times governed by the Poisson process it performs a single element swap based on a best response set. The new idea is that our algorithm is spiteful as it can purposefully discard an element that is in both the current set and the best response set. Surprisingly, this spiteful step does not harm the approximation our algorithm achieves for monotone submodular functions but is necessary for the non-monotone case. As applications, we obtain fast approximation algorithms for maximizing non-monotone submodular function subject to a general matroid independence constraint as well as faster algorithms for a partition matroid.

Thursday, August 06 2026, 00:00

Exact simulation of diffusions and improved algorithms for log-concave sampling

Authors: Fan Chen, Sinho Chewi, Alexander Rakhlin, Matthew S. Zhang

We study exact simulation of diffusions via rejection sampling on path space using unbiased estimators of the density ratio obtained from Girsanov's theorem. When applied to the underdamped Langevin diffusion, it yields an algorithm for sampling from a strongly log-concave and log-smooth distribution with condition number $κ$, in dimension $d$, to accuracy $\varepsilon$ in Rényi divergence, in $\widetilde O(κ^{2/3} d^{1/3}\,\mathrm{polylog}(1/\varepsilon))$ queries. Under a third derivative bound, the dimension dependence improves to $d^{1/5}$. This improves substantially over the prior state-of-the-art complexity of $\widetilde O(κd^{1/2}\,\mathrm{polylog}(1/\varepsilon))$ for the Metropolis-adjusted Langevin algorithm, and over the $d^{1/4}$ dimension dependence of Metropolized Hamiltonian Monte Carlo under the same third derivative bound. We also present applications to the mirror Langevin diffusion, and for obtaining Fisher information bounds in the non-log-concave case.

Authors: Fan Chen, Sinho Chewi, Alexander Rakhlin, Matthew S. Zhang

We study exact simulation of diffusions via rejection sampling on path space using unbiased estimators of the density ratio obtained from Girsanov's theorem. When applied to the underdamped Langevin diffusion, it yields an algorithm for sampling from a strongly log-concave and log-smooth distribution with condition number $κ$, in dimension $d$, to accuracy $\varepsilon$ in Rényi divergence, in $\widetilde O(κ^{2/3} d^{1/3}\,\mathrm{polylog}(1/\varepsilon))$ queries. Under a third derivative bound, the dimension dependence improves to $d^{1/5}$. This improves substantially over the prior state-of-the-art complexity of $\widetilde O(κd^{1/2}\,\mathrm{polylog}(1/\varepsilon))$ for the Metropolis-adjusted Langevin algorithm, and over the $d^{1/4}$ dimension dependence of Metropolized Hamiltonian Monte Carlo under the same third derivative bound. We also present applications to the mirror Langevin diffusion, and for obtaining Fisher information bounds in the non-log-concave case.

Thursday, August 06 2026, 00:00

A Tight Bound on Online Vertex Cover under Edge Arrivals

Authors: Zhihao Gavin Tang, Yuhao Zhang

We prove a tight impossibility result for online vertex cover under edge arrivals. No randomized integral or fractional algorithm achieves a competitive ratio strictly below $2$ against an oblivious adversary, even on bipartite graphs. Since the standard algorithm that takes both endpoints of every uncovered edge is $2$-competitive, this settles the optimal ratio. Our proof is a direct reduction from the recent breakthrough blueprint framework of Assadi, Jiang, and Xiang.

Authors: Zhihao Gavin Tang, Yuhao Zhang

We prove a tight impossibility result for online vertex cover under edge arrivals. No randomized integral or fractional algorithm achieves a competitive ratio strictly below $2$ against an oblivious adversary, even on bipartite graphs. Since the standard algorithm that takes both endpoints of every uncovered edge is $2$-competitive, this settles the optimal ratio. Our proof is a direct reduction from the recent breakthrough blueprint framework of Assadi, Jiang, and Xiang.

Thursday, August 06 2026, 00:00

A Separator-based Algorithm for the Graph Edit Distance Problem

Authors: Laura Bülte, Philip Mayer, Lars Müller, Petra Mutzel

The Graph Edit Distance (GED) is a widely used graph similarity measure asking for the minimum cost of a sequence of edits transforming one (labeled) graph into another. The considered edit operations are deletion, insertion, and relabeling of nodes and edges. Special cases include the Graph Isomorphism problem, as well as many other graph problems that ask for the existence or minimum cost of a certain substructure, like the Traveling Salesman or Maximum Clique problem. We present a novel exponential time algorithm to compute the exact GED and a corresponding edit sequence in $O^*(4 + \varepsilon)^n$ time and polynomial space, provided one of the two graphs admits strictly sublinear balanced separators. In particular, the claimed runtime holds if one of the graphs is $K_h$-minor free (e.g., planar), or has bounded treewidth, which is the case for many real-world applications (e.g., all instances in GEDLIB). This substantially improves the best known worst-case running time bounds of $O^*(n!)$ for these graph classes.

Authors: Laura Bülte, Philip Mayer, Lars Müller, Petra Mutzel

The Graph Edit Distance (GED) is a widely used graph similarity measure asking for the minimum cost of a sequence of edits transforming one (labeled) graph into another. The considered edit operations are deletion, insertion, and relabeling of nodes and edges. Special cases include the Graph Isomorphism problem, as well as many other graph problems that ask for the existence or minimum cost of a certain substructure, like the Traveling Salesman or Maximum Clique problem. We present a novel exponential time algorithm to compute the exact GED and a corresponding edit sequence in $O^*(4 + \varepsilon)^n$ time and polynomial space, provided one of the two graphs admits strictly sublinear balanced separators. In particular, the claimed runtime holds if one of the graphs is $K_h$-minor free (e.g., planar), or has bounded treewidth, which is the case for many real-world applications (e.g., all instances in GEDLIB). This substantially improves the best known worst-case running time bounds of $O^*(n!)$ for these graph classes.

Thursday, August 06 2026, 00:00

Taming Treewidth DP with Modulators: A General Booster for Graph Heuristics

Authors: Jialiang Li, Aneta Neumann, Frank Neumann, Hung Nguyen, Mingyu Guo

Treewidth is a fundamental graph invariant that quantifies how tree-like a given graph is. It is extensively used with dynamic programming to design fixed-parameter tractable algorithms for many NP-hard graph combinatorial optimization problems. However, despite broad theoretical applicability, treewidth dynamic programming (TDP) does not scale in practice beyond graphs with very small treewidth. Rather than applying TDP as a standalone technique, in this paper, we demonstrate that TDP can serve as a broadly applicable enhancer for a wide range of graph combinatorial optimization algorithms. Our framework leverages the concept of treewidth modulators, which refer to vertex sets whose removal significantly reduces the treewidth. We further propose an empirically efficient procedure for generating such treewidth modulators. To enhance an algorithm $\textit{A}$, we use $\textit{A}$ to heuristically make decisions on the modulators vertices, after which the remaining decisions outside the treewidth modulators become scalable for TDP. To demonstrate the general applicability of our proposed framework. We experimented with three classic graph combinatorial optimization models: Maximum Independent Set, Minimum Vertex Cover, and Max Cut. We apply TDP to enhance algorithms across diverse paradigms, including evolutionary search, greedy heuristics, and graph-neural-network-based heuristics. For all combinations of optimization models and base algorithms, TDP significantly improves performance over the original methods. In many settings, TDP-enhanced greedy heuristics are competitive with, and sometimes clearly outperform, state-of-the-art commercial solvers.

Authors: Jialiang Li, Aneta Neumann, Frank Neumann, Hung Nguyen, Mingyu Guo

Treewidth is a fundamental graph invariant that quantifies how tree-like a given graph is. It is extensively used with dynamic programming to design fixed-parameter tractable algorithms for many NP-hard graph combinatorial optimization problems. However, despite broad theoretical applicability, treewidth dynamic programming (TDP) does not scale in practice beyond graphs with very small treewidth. Rather than applying TDP as a standalone technique, in this paper, we demonstrate that TDP can serve as a broadly applicable enhancer for a wide range of graph combinatorial optimization algorithms. Our framework leverages the concept of treewidth modulators, which refer to vertex sets whose removal significantly reduces the treewidth. We further propose an empirically efficient procedure for generating such treewidth modulators. To enhance an algorithm $\textit{A}$, we use $\textit{A}$ to heuristically make decisions on the modulators vertices, after which the remaining decisions outside the treewidth modulators become scalable for TDP. To demonstrate the general applicability of our proposed framework. We experimented with three classic graph combinatorial optimization models: Maximum Independent Set, Minimum Vertex Cover, and Max Cut. We apply TDP to enhance algorithms across diverse paradigms, including evolutionary search, greedy heuristics, and graph-neural-network-based heuristics. For all combinations of optimization models and base algorithms, TDP significantly improves performance over the original methods. In many settings, TDP-enhanced greedy heuristics are competitive with, and sometimes clearly outperform, state-of-the-art commercial solvers.

Thursday, August 06 2026, 00:00

The Greedy Binary Search Tree is Non-trivially Competitive

Authors: Yuhao Guo, Seth Pettie, Daniel Skora, Chengzhang Wan

We prove that the $\textsf{Greedy}$ binary search tree is $2^{O(\sqrt{\log\log n})}$-competitive. It is widely conjectured that $\textsf{Greedy}$ is $O(1)$-competitive, but before this work it was not known to be $f$-competitive, for any non-trivial $f(n)=o(\log n)$. Our analysis differs from prior analyses of binary search trees. It takes what might be called a "scaling" approach, where the cost at a refined scale is related to the cost at a coarser scale, and Wilber's interleave lower bound.

Authors: Yuhao Guo, Seth Pettie, Daniel Skora, Chengzhang Wan

We prove that the $\textsf{Greedy}$ binary search tree is $2^{O(\sqrt{\log\log n})}$-competitive. It is widely conjectured that $\textsf{Greedy}$ is $O(1)$-competitive, but before this work it was not known to be $f$-competitive, for any non-trivial $f(n)=o(\log n)$. Our analysis differs from prior analyses of binary search trees. It takes what might be called a "scaling" approach, where the cost at a refined scale is related to the cost at a coarser scale, and Wilber's interleave lower bound.

Thursday, August 06 2026, 00:00

From Compensation Design to Budget-Feasible Mechanisms: A Constant Approximation for Subadditive Valuations

Authors: Ioannis Anagnostides, Kshipra Bhawalkar, Christopher Liaw, Aranyak Mehta, Grigoris Velegkas, Weiqiang Zheng

Budget-feasible mechanism design is a classic framework introduced by Singer, but there is still a wide gap between existing upper and lower bounds. In this paper, we significantly advance the state of the art. First, without computational constraints, we show that there exists a budget-feasible universally truthful mechanism with the following approximation ratios: - $3$ for monotone submodular valuations and $e+1$ for nonmonotone submodular valuations, improving over $3.798$ and $9.742$, respectively. - $e+1$ for XOS valuations, improving over $28$. In large markets, our approximation can be improved deterministically to $e$. - $2e+1$ for subadditive valuations, improving over $33$. In large markets, our approximation can be improved deterministically to $2e$. Moreover, for subadditive valuations, we obtain a constant-approximation mechanism that runs in polynomial time using demand queries. This improves over the previous best approximation of $O(\log \log n)$, resolving a long-standing open problem going back to Dobzinski, Papadimitriou, and Singer, who conjectured that a constant approximation requires exponentially many demand queries. We obtain these results through a simple and unifying framework based on non-truthful indirect mechanisms, recently coined compensation design. In particular, through a potential argument, we establish constant price-of-stability bounds for compensation design based on marginal-contribution payment rules, which we then translate into truthful direct mechanisms. For subadditive valuations, the core of the argument is a new smoothing lemma showing that every subadditive function can be approximated within a factor of $2$ by a self-bounding function. This is also of independent interest, readily addressing an open question in multiwinner elections by showing the existence of a $2e$-approximate core even under subadditive valuations.

Authors: Ioannis Anagnostides, Kshipra Bhawalkar, Christopher Liaw, Aranyak Mehta, Grigoris Velegkas, Weiqiang Zheng

Budget-feasible mechanism design is a classic framework introduced by Singer, but there is still a wide gap between existing upper and lower bounds. In this paper, we significantly advance the state of the art. First, without computational constraints, we show that there exists a budget-feasible universally truthful mechanism with the following approximation ratios: - $3$ for monotone submodular valuations and $e+1$ for nonmonotone submodular valuations, improving over $3.798$ and $9.742$, respectively. - $e+1$ for XOS valuations, improving over $28$. In large markets, our approximation can be improved deterministically to $e$. - $2e+1$ for subadditive valuations, improving over $33$. In large markets, our approximation can be improved deterministically to $2e$. Moreover, for subadditive valuations, we obtain a constant-approximation mechanism that runs in polynomial time using demand queries. This improves over the previous best approximation of $O(\log \log n)$, resolving a long-standing open problem going back to Dobzinski, Papadimitriou, and Singer, who conjectured that a constant approximation requires exponentially many demand queries. We obtain these results through a simple and unifying framework based on non-truthful indirect mechanisms, recently coined compensation design. In particular, through a potential argument, we establish constant price-of-stability bounds for compensation design based on marginal-contribution payment rules, which we then translate into truthful direct mechanisms. For subadditive valuations, the core of the argument is a new smoothing lemma showing that every subadditive function can be approximated within a factor of $2$ by a self-bounding function. This is also of independent interest, readily addressing an open question in multiwinner elections by showing the existence of a $2e$-approximate core even under subadditive valuations.

Thursday, August 06 2026, 00:00

Bottleneck Paths Reduce to Deterministic Graphical Games: A Correction to a Claimed Linear-Time Algorithm

Authors: Egor Gorbachev

Chechik, Kaplan, Thorup, Zamir, and Zwick (STACS 2016) claimed a simple deterministic linear-time comparison-based algorithm for solving deterministic two-player, turn-based, zero-sum terminal-payoff games, also known as deterministic graphical games (DGGs). We give a counterexample to their algorithm. We also give a deterministic linear-time reduction from the directed $s$-$t$ bottleneck path (BP) problem to the DGG problem. Consequently, a linear-time comparison-based algorithm for computing the value of a designated start vertex in a DGG would yield a linear-time comparison-based algorithm for directed $s$-$t$ BP. Whether directed $s$-$t$ BP admits such an algorithm has remained open since Gabow and Tarjan gave their $\mathcal{O}(m\log^* n)$-time algorithm. Thus, a positive resolution of the open question for DGGs would also resolve the corresponding open question for directed $s$-$t$ BP.

Authors: Egor Gorbachev

Chechik, Kaplan, Thorup, Zamir, and Zwick (STACS 2016) claimed a simple deterministic linear-time comparison-based algorithm for solving deterministic two-player, turn-based, zero-sum terminal-payoff games, also known as deterministic graphical games (DGGs). We give a counterexample to their algorithm. We also give a deterministic linear-time reduction from the directed $s$-$t$ bottleneck path (BP) problem to the DGG problem. Consequently, a linear-time comparison-based algorithm for computing the value of a designated start vertex in a DGG would yield a linear-time comparison-based algorithm for directed $s$-$t$ BP. Whether directed $s$-$t$ BP admits such an algorithm has remained open since Gabow and Tarjan gave their $\mathcal{O}(m\log^* n)$-time algorithm. Thus, a positive resolution of the open question for DGGs would also resolve the corresponding open question for directed $s$-$t$ BP.

Thursday, August 06 2026, 00:00

Multi-Level Aggregation via Dual Fitting: An $O(D)$-Competitive Algorithm

Authors: Sara Ahmadian, Shuchi Chawla, Ravi Kumar, Manish Purohit, Shirley Zhang

We present a new online algorithm for the well-known Multi-Level Aggregation Problem (MLAP) with arbitrary delay functions, achieving a $2D$-competitive ratio, where $D$ is the depth of the underlying tree. This result improves the current best-known competitive ratio of $O(D^2)$ and asymptotically matches the $D$-competitive bound previously known only for the deadline variant, thereby closing the asymptotic gap between the two settings. Our key technical contribution is a novel dual fitting framework that provides a unified analysis for both settings; in particular, it also establishes a $D$-competitive ratio for MLAP with deadlines. Our analysis is built upon two new ideas: a hindsight dual construction, which resolves the infeasibility issues in traditional online primal-dual methods, and a time-dependent dual packing that maintains feasibility over dynamic request sets.

Authors: Sara Ahmadian, Shuchi Chawla, Ravi Kumar, Manish Purohit, Shirley Zhang

We present a new online algorithm for the well-known Multi-Level Aggregation Problem (MLAP) with arbitrary delay functions, achieving a $2D$-competitive ratio, where $D$ is the depth of the underlying tree. This result improves the current best-known competitive ratio of $O(D^2)$ and asymptotically matches the $D$-competitive bound previously known only for the deadline variant, thereby closing the asymptotic gap between the two settings. Our key technical contribution is a novel dual fitting framework that provides a unified analysis for both settings; in particular, it also establishes a $D$-competitive ratio for MLAP with deadlines. Our analysis is built upon two new ideas: a hindsight dual construction, which resolves the infeasibility issues in traditional online primal-dual methods, and a time-dependent dual packing that maintains feasibility over dynamic request sets.

Thursday, August 06 2026, 00:00

Bicriteria Approximation Algorithms for Demand Matching

Authors: Yuchong Pan, Michel X. Goemans

The demand matching problem generalizes both the knapsack problem and the $b$-matching problem. In this problem, each edge of a graph has a demand and a weight, each vertex has a capacity, and the goal is to find a maximum weight subset of edges whose total incident demand at every vertex does not exceed its capacity. We study $(α, β)$-bicriteria approximation algorithms, which return a solution of weight at least $1/α$ times the optimum while allowing an additive capacity violation of at most $β$ times the maximum edge demand. We give an iterative relaxation algorithm for the demand matching problem that exploits a structural characterization of strictly fractional extreme points of the natural LP relaxation, which reduces the residual rounding problem to odd-cycle instances. Combined with a better-of-two rounding strategy, this yields $(7/6, 1)$- and $(1, 1)$-bicriteria approximation algorithms for general and bipartite graphs, respectively. We further generalize this approach to obtain a parametric family of algorithms, including a $(1, 4/3)$-bicriteria approximation. Separately, for the more general $k$-hypergraph demand matching problem, we give a greedy, combinatorial $(k, 1)$-bicriteria approximation algorithm. We complement these algorithmic results with matching lower bounds relative to the natural LP relaxation for $β= 0$ and all $β\geq 1$, completely characterizing the trade-off between weight approximation and additive capacity violation in this range.

Authors: Yuchong Pan, Michel X. Goemans

The demand matching problem generalizes both the knapsack problem and the $b$-matching problem. In this problem, each edge of a graph has a demand and a weight, each vertex has a capacity, and the goal is to find a maximum weight subset of edges whose total incident demand at every vertex does not exceed its capacity. We study $(α, β)$-bicriteria approximation algorithms, which return a solution of weight at least $1/α$ times the optimum while allowing an additive capacity violation of at most $β$ times the maximum edge demand. We give an iterative relaxation algorithm for the demand matching problem that exploits a structural characterization of strictly fractional extreme points of the natural LP relaxation, which reduces the residual rounding problem to odd-cycle instances. Combined with a better-of-two rounding strategy, this yields $(7/6, 1)$- and $(1, 1)$-bicriteria approximation algorithms for general and bipartite graphs, respectively. We further generalize this approach to obtain a parametric family of algorithms, including a $(1, 4/3)$-bicriteria approximation. Separately, for the more general $k$-hypergraph demand matching problem, we give a greedy, combinatorial $(k, 1)$-bicriteria approximation algorithm. We complement these algorithmic results with matching lower bounds relative to the natural LP relaxation for $β= 0$ and all $β\geq 1$, completely characterizing the trade-off between weight approximation and additive capacity violation in this range.

Thursday, August 06 2026, 00:00

Concentration from Product Moments via an Additional Element of Randomness

Authors: Michael Saks, Aravind Srinivasan, Renata Valieva

The standard method of exponential moments for proving concentration bounds can often be replaced by an argument based on elementary symmetric polynomials. We introduce an additional element of randomness into this framework, which reduces the problem to bounding product moments over a uniformly sampled set of indices. We show that this approach gives useful bounds in three settings. For read-$Δ$ families under limited independence, we obtain bounds governed by the degrees of randomly induced dependency subgraphs, improving the dependence on worst-case degrees. For random binary linear hashing with (semi-)random inputs, we derive fixed-bin and maximum-load bounds by controlling the rank defect of random tuples of input keys. Finally, for stochastic processes, we show how decay of product moments yields concentration bounds, recovering the spectral and mixing-time scales for finite-state Markov chains.

Authors: Michael Saks, Aravind Srinivasan, Renata Valieva

The standard method of exponential moments for proving concentration bounds can often be replaced by an argument based on elementary symmetric polynomials. We introduce an additional element of randomness into this framework, which reduces the problem to bounding product moments over a uniformly sampled set of indices. We show that this approach gives useful bounds in three settings. For read-$Δ$ families under limited independence, we obtain bounds governed by the degrees of randomly induced dependency subgraphs, improving the dependence on worst-case degrees. For random binary linear hashing with (semi-)random inputs, we derive fixed-bin and maximum-load bounds by controlling the rank defect of random tuples of input keys. Finally, for stochastic processes, we show how decay of product moments yields concentration bounds, recovering the spectral and mixing-time scales for finite-state Markov chains.

Thursday, August 06 2026, 00:00

Separating quantum circuits from classical LLMs

Authors: Srinivasan Arunachalam, Arkopal Dutt, Hari Krovi, Rik Sengupta

Modern large language models - transformers and diffusion language models - are built around two canonical algorithmic tasks: prediction and generation. We prove unconditional separations between low-depth quantum computation and the corresponding bounded-resource classical language-model architectures in both regimes. Concretely, we exhibit the following: 1. Distributional separation. We give a distribution that is sampleable by $\textsf{QNC}^0$ circuits (i.e., a family of constant-depth quantum circuits consisting of bounded fan-in gates) that no constant-round diffusion language model ($\textsf{DLM}$) with shallow scheduling and denoising can sample within constant distance, even when allowed sublinear chain-of-thought and output-token revision/remasking events, the very features modern $\textsf{DLM}$s rely on. 2. Functional separation. We exhibit a function computable in $\land \circ \textsf{QNC}^0[\log\log n]$ (i.e., a family of O$(\log\log n)$-depth $\textsf{QNC}^0$ circuits, where $n$ is the input length, followed by a single classical $\mathsf{AND}$ gate) such that any constant-depth decoder-only transformer computing the function must be large: it would have to have width $n^{Ω(1)}$. Together, our work initiates the study of quantum advantage in the era of large language models.

Authors: Srinivasan Arunachalam, Arkopal Dutt, Hari Krovi, Rik Sengupta

Modern large language models - transformers and diffusion language models - are built around two canonical algorithmic tasks: prediction and generation. We prove unconditional separations between low-depth quantum computation and the corresponding bounded-resource classical language-model architectures in both regimes. Concretely, we exhibit the following: 1. Distributional separation. We give a distribution that is sampleable by $\textsf{QNC}^0$ circuits (i.e., a family of constant-depth quantum circuits consisting of bounded fan-in gates) that no constant-round diffusion language model ($\textsf{DLM}$) with shallow scheduling and denoising can sample within constant distance, even when allowed sublinear chain-of-thought and output-token revision/remasking events, the very features modern $\textsf{DLM}$s rely on. 2. Functional separation. We exhibit a function computable in $\land \circ \textsf{QNC}^0[\log\log n]$ (i.e., a family of O$(\log\log n)$-depth $\textsf{QNC}^0$ circuits, where $n$ is the input length, followed by a single classical $\mathsf{AND}$ gate) such that any constant-depth decoder-only transformer computing the function must be large: it would have to have width $n^{Ω(1)}$. Together, our work initiates the study of quantum advantage in the era of large language models.

Wednesday, August 05 2026, 00:00

CNOT-Distance is NP-complete under all-to-all connectivity

Authors: Antonio Acuaviva, Arturo Acuaviva, Pablo Acuaviva

Given $A\in\operatorname{GL}(N,2)$ and an integer $K$, we ask whether $A$ can be implemented by at most $K$ CNOT gates on fixed labelled wires with all-to-all connectivity. We prove that this problem is NP-complete. From a finite simple graph $G=(V,E)$, we construct an upper-unitriangular matrix $A_G\in\operatorname{GL}(2|V|+|E|+1,2)$ satisfying $\ell_{\mathrm{CNOT}}(A_G)=2|V|+2|E|+τ(G)$, where $τ(G)$ is the minimum vertex-cover size. Each target matrix has $O(N)$ nonzero entries and row Hamming weight at most four. The lower bound unfolds an arbitrary CNOT circuit into an XOR directed acyclic graph and applies projection--contraction operations, allowing cancellation and unrestricted reuse of intermediate parities. For this family, the optimum is unchanged by any finite number of clean or borrowed ancillary wires that must be restored. A polynomial-time decoder further yields NP-hardness of approximation within every fixed additive constant and, through an L-reduction from Minimum Vertex Cover on cubic graphs, APX-hardness of the associated CNOT-circuit optimisation problem.

Authors: Antonio Acuaviva, Arturo Acuaviva, Pablo Acuaviva

Given $A\in\operatorname{GL}(N,2)$ and an integer $K$, we ask whether $A$ can be implemented by at most $K$ CNOT gates on fixed labelled wires with all-to-all connectivity. We prove that this problem is NP-complete. From a finite simple graph $G=(V,E)$, we construct an upper-unitriangular matrix $A_G\in\operatorname{GL}(2|V|+|E|+1,2)$ satisfying $\ell_{\mathrm{CNOT}}(A_G)=2|V|+2|E|+τ(G)$, where $τ(G)$ is the minimum vertex-cover size. Each target matrix has $O(N)$ nonzero entries and row Hamming weight at most four. The lower bound unfolds an arbitrary CNOT circuit into an XOR directed acyclic graph and applies projection--contraction operations, allowing cancellation and unrestricted reuse of intermediate parities. For this family, the optimum is unchanged by any finite number of clean or borrowed ancillary wires that must be restored. A polynomial-time decoder further yields NP-hardness of approximation within every fixed additive constant and, through an L-reduction from Minimum Vertex Cover on cubic graphs, APX-hardness of the associated CNOT-circuit optimisation problem.

Wednesday, August 05 2026, 00:00

Reducing CMSO to Unbreakable Graphs Cannot be Computable

Authors: Colin Geniet, Roohani Sharma

Lokshtanov, Ramanujan, Saurabh, and Zehavi [ICALP 2018] proved that for any CMSO formula $φ$, testing $φ$ on arbitrary graphs can be reduced to testing it on $(q,k)$-unbreakable graphs for appropriate parameters. Their proof is non-constructive, and they ask whether it can be made constructive. We prove that this is impossible: specifically, the parameter $q$ cannot be a computable function of $φ$.

Authors: Colin Geniet, Roohani Sharma

Lokshtanov, Ramanujan, Saurabh, and Zehavi [ICALP 2018] proved that for any CMSO formula $φ$, testing $φ$ on arbitrary graphs can be reduced to testing it on $(q,k)$-unbreakable graphs for appropriate parameters. Their proof is non-constructive, and they ask whether it can be made constructive. We prove that this is impossible: specifically, the parameter $q$ cannot be a computable function of $φ$.

Wednesday, August 05 2026, 00:00

The complexity of minimum-density locating-dominating set in infinite periodic graphs

Authors: Arthur C. Gomes, Yoshiko Wakabayashi

A dominating set $S$ of a graph $G$ is a locating-dominating set (LDS) if, for each pair of distinct vertices not in~$S$, their neighbourhoods in $S$ are distinct. Finding a minimum-cardinality LDS in finite graphs is a well-known NP-hard problem. On infinite graphs, this problem naturally generalises to finding an LDS of minimum density. While density bounds have been widely studied for specific infinite regular grids, no computational complexity results exist for infinite graphs. We prove that the minimum-density LDS problem in infinite $\mathbb{Z}$-periodic graphs with a finite period is NP-hard. This result bridges the gap between cardinality minimization on finite graphs and density minimization on infinite graphs via a rigorous periodic reduction. Furthermore, our approach can be adapted to establish NP-hardness for related structural problems on infinite periodic graphs.

Authors: Arthur C. Gomes, Yoshiko Wakabayashi

A dominating set $S$ of a graph $G$ is a locating-dominating set (LDS) if, for each pair of distinct vertices not in~$S$, their neighbourhoods in $S$ are distinct. Finding a minimum-cardinality LDS in finite graphs is a well-known NP-hard problem. On infinite graphs, this problem naturally generalises to finding an LDS of minimum density. While density bounds have been widely studied for specific infinite regular grids, no computational complexity results exist for infinite graphs. We prove that the minimum-density LDS problem in infinite $\mathbb{Z}$-periodic graphs with a finite period is NP-hard. This result bridges the gap between cardinality minimization on finite graphs and density minimization on infinite graphs via a rigorous periodic reduction. Furthermore, our approach can be adapted to establish NP-hardness for related structural problems on infinite periodic graphs.

Wednesday, August 05 2026, 00:00

Decidability of Parameterised Dolev-Yao Secrecy

Authors: Ioana Boureanu, R. Ramanujam, Srinibas Swain

We study the verification of parameterised secrecy for cryptographic protocols in the Dolev-Yao model, where the number of protocol sessions is unbounded and treated as a parameter. This differs fundamentally from classical Dolev-Yao secrecy, which asks whether a protocol leaks a secret irrespective of the number of executions; our question is whether secrecy holds uniformly across all system sizes, where such a size is a parameter. This parameterised perspective captures how attacks scale with the number of participants and provides a formal basis for the empirical effectiveness of small-instance analysis. Secrecy (parameterised or not) is undecidable in general, even under bounded freshness or bounded message size. We identify two structural restrictions that make parameterised secrecy decidable: (i) global bounded freshness per role, and (ii) a Dolev-Yao intruder restricted to well-typed substitutions. Under these assumptions, protocol executions admit a finite representation up to a collapsing map on agents and terms. Our main result is that parameterised secrecy is decidable in this setting. We obtain a cut-off theorem: secrecy violations in systems with arbitrarily many sessions are always witnessed in systems of bounded size. The cut-off is self-contained; more strongly, the induced transition system forms a well-structured transition system (WSTS) under a bound-based ordering, so secrecy also reduces to a coverability problem in WSTS. This provides a structural explanation for the existence of finite witnesses in symbolic protocol analysis and connects Dolev-Yao verification with parameterised verification techniques.

Authors: Ioana Boureanu, R. Ramanujam, Srinibas Swain

We study the verification of parameterised secrecy for cryptographic protocols in the Dolev-Yao model, where the number of protocol sessions is unbounded and treated as a parameter. This differs fundamentally from classical Dolev-Yao secrecy, which asks whether a protocol leaks a secret irrespective of the number of executions; our question is whether secrecy holds uniformly across all system sizes, where such a size is a parameter. This parameterised perspective captures how attacks scale with the number of participants and provides a formal basis for the empirical effectiveness of small-instance analysis. Secrecy (parameterised or not) is undecidable in general, even under bounded freshness or bounded message size. We identify two structural restrictions that make parameterised secrecy decidable: (i) global bounded freshness per role, and (ii) a Dolev-Yao intruder restricted to well-typed substitutions. Under these assumptions, protocol executions admit a finite representation up to a collapsing map on agents and terms. Our main result is that parameterised secrecy is decidable in this setting. We obtain a cut-off theorem: secrecy violations in systems with arbitrarily many sessions are always witnessed in systems of bounded size. The cut-off is self-contained; more strongly, the induced transition system forms a well-structured transition system (WSTS) under a bound-based ordering, so secrecy also reduces to a coverability problem in WSTS. This provides a structural explanation for the existence of finite witnesses in symbolic protocol analysis and connects Dolev-Yao verification with parameterised verification techniques.

Wednesday, August 05 2026, 00:00

Tight Information Complexity of the Coin Problem in the Broadcast Model

Authors: Hadi Kazemi, Varun Jog

We study distributed testing of $\mathrm{Ber}(α)$ versus $\mathrm{Ber}(β)$ in the broadcast, or shared-blackboard, model. For protocols with constant advantage, we characterise up to universal constant factors the information complexity under either hypothesis for every pair $β<α$. The characterisation shows that the two information costs can be quite different and identifies three parameter regimes, with optimal protocols based respectively on clean samples, a noisy binary symmetric channel, and an asymmetric $Z$-channel. The lower bounds rely on a novel mixed Hellinger--Jensen--Shannon inequality that may be of independent interest. We also characterise the constant-advantage information complexity of testing arbitrary discrete distributions via an optimisation problem over channels, and show that binary-output channels suffice. We obtain bounds for bounded likelihood-ratio distributions, and give general upper bounds in terms of $χ^2$ divergence. As applications, we recover the broadcast-model set-disjointness lower bound, and derive stronger lower bounds in the multi-pass streaming setting for some problems considered in prior work.

Authors: Hadi Kazemi, Varun Jog

We study distributed testing of $\mathrm{Ber}(α)$ versus $\mathrm{Ber}(β)$ in the broadcast, or shared-blackboard, model. For protocols with constant advantage, we characterise up to universal constant factors the information complexity under either hypothesis for every pair $β<α$. The characterisation shows that the two information costs can be quite different and identifies three parameter regimes, with optimal protocols based respectively on clean samples, a noisy binary symmetric channel, and an asymmetric $Z$-channel. The lower bounds rely on a novel mixed Hellinger--Jensen--Shannon inequality that may be of independent interest. We also characterise the constant-advantage information complexity of testing arbitrary discrete distributions via an optimisation problem over channels, and show that binary-output channels suffice. We obtain bounds for bounded likelihood-ratio distributions, and give general upper bounds in terms of $χ^2$ divergence. As applications, we recover the broadcast-model set-disjointness lower bound, and derive stronger lower bounds in the multi-pass streaming setting for some problems considered in prior work.

Wednesday, August 05 2026, 00:00

Linked Barcode for Persistence Induced by Filtrations

Authors: Tamal K. Dey, Gilberto Gonzalez-Arroyo, Tao Hou

The well-known persistence algorithm summarizes the evolution of homological cycles into what is called a \emph{barcode} while scanning an input simplicial filtration. We show that this summarization process can be enriched by monitoring other algebraic structures that weave through different dimensions. In particular, we propose an algorithm to monitor the $(p+1)$-chains that make $p$-cycles to be $p$-boundaries and then morph into $(p+1)$-cycles. In effect, we get extra bars called \emph{links} connecting the bars in dimension $p$ with the bars in dimension $p+1$ in the persistence barcode. The links produce extra barcodes, which we call \emph{link barcodes} in addition to the usual ones obtained by standard persistence. The link barcodes, as such, are not stable. However, we can make them stable using a fixed ``reference'' filtration. We apply the link barcodes to the graph isomorphism problem and to the link prediction problem in temporal networks exhibiting its discriminating power through these experiments.

Authors: Tamal K. Dey, Gilberto Gonzalez-Arroyo, Tao Hou

The well-known persistence algorithm summarizes the evolution of homological cycles into what is called a \emph{barcode} while scanning an input simplicial filtration. We show that this summarization process can be enriched by monitoring other algebraic structures that weave through different dimensions. In particular, we propose an algorithm to monitor the $(p+1)$-chains that make $p$-cycles to be $p$-boundaries and then morph into $(p+1)$-cycles. In effect, we get extra bars called \emph{links} connecting the bars in dimension $p$ with the bars in dimension $p+1$ in the persistence barcode. The links produce extra barcodes, which we call \emph{link barcodes} in addition to the usual ones obtained by standard persistence. The link barcodes, as such, are not stable. However, we can make them stable using a fixed ``reference'' filtration. We apply the link barcodes to the graph isomorphism problem and to the link prediction problem in temporal networks exhibiting its discriminating power through these experiments.

Wednesday, August 05 2026, 00:00

Ranked spreadness and sample-based testing

Authors: Gaia Carenini

In this note, we introduce the notion of ranked spreadness, a strengthening of the usual spread condition in which the elements of each member can be ordered so that their one-coordinate marginals decay geometrically with their rank. This additional structure removes the dependence on the maximum set size in random-containment estimates. We prove width-free hitting and weighted-concentration theorems for ranked-spread set systems, together with an elementary kernel-extraction theorem showing that ranked spreadness arises naturally in arbitrary distributions on small sets. Our main application is to the simulation of nonadaptive property testers by sample-based testers. If a one-sided tester has average query complexity $d$ and rejects every far input with probability at least $δ$, then, for every integer $c>d/δ$, it admits a one-sided sample-based simulation with expected sample complexity $O_{d,δ,|Σ|}\bigl(n^{1-1/c}\bigr)$. More generally, if positive inputs are rejected with probability at most $γ$ and far inputs with probability at least $δ>γ$, the same conclusion holds for every $c>d/(δ-γ)$. In particular, for constant-query nonadaptive testers we obtain an exponent $1-Θ(1/q)$, matching, up to the dependence on the rejection gap, the exponent conjectured by Fischer, Lachish, and Vasudev.

Authors: Gaia Carenini

In this note, we introduce the notion of ranked spreadness, a strengthening of the usual spread condition in which the elements of each member can be ordered so that their one-coordinate marginals decay geometrically with their rank. This additional structure removes the dependence on the maximum set size in random-containment estimates. We prove width-free hitting and weighted-concentration theorems for ranked-spread set systems, together with an elementary kernel-extraction theorem showing that ranked spreadness arises naturally in arbitrary distributions on small sets. Our main application is to the simulation of nonadaptive property testers by sample-based testers. If a one-sided tester has average query complexity $d$ and rejects every far input with probability at least $δ$, then, for every integer $c>d/δ$, it admits a one-sided sample-based simulation with expected sample complexity $O_{d,δ,|Σ|}\bigl(n^{1-1/c}\bigr)$. More generally, if positive inputs are rejected with probability at most $γ$ and far inputs with probability at least $δ>γ$, the same conclusion holds for every $c>d/(δ-γ)$. In particular, for constant-query nonadaptive testers we obtain an exponent $1-Θ(1/q)$, matching, up to the dependence on the rejection gap, the exponent conjectured by Fischer, Lachish, and Vasudev.

Wednesday, August 05 2026, 00:00

Improved Euclidean Shallow Light Trees

Authors: Hung Le, Shay Solomon, Cuong Than, Csaba D. Tóth, Tianyi Zhang

For parameters $α,β\geq 1$, a spanning tree $T$ of a weighted graph $G$ rooted at a designated vertex $r$ is called an $(α,β)$-shallow-light tree (SLT) if (i) for every vertex $v$, $d_T(r,v) \leq α\cdot d_G(r,v)$ (root-stretch $α$), and (ii) $w(T) \leq β\cdot w(\mathsf{MST})$ (lightness $β$). The pioneering work of Khuller, Raghavachari, and Young (SODA 1993) constructed $\left(1+ε, \tfrac{2}ε+1\right)$-SLTs for general weighted graphs, and proved that this tradeoff between root-stretch and lightness is tight even for series-parallel graphs. They further asked whether even a slight improvement, namely reducing the lightness to $\tfrac{2-c}ε$ for any constant $c>0$, is possible in the Euclidean plane. We resolve this longstanding question in the affirmative. Specifically, we show that every Euclidean instance admits an SLT with root-stretch $1+ε$ and lightness at most $\left(\frac{5}{3} + o_ε(1)\right) \cdot \frac{1}ε$, thereby significantly improving upon the longstanding $2/ε$ barrier. As our second main result, we provide a construction of SLTs in the Euclidean plane, with root stretch $1+ε$ and lightness at most $\left(\frac{2π}{\sqrt{4π^2+1}}+o_ε(1)\right)\frac{1}ε \approx (0.987+o_ε(1))\frac{1}ε$. Notably, this reduces the leading $2/ε$ term in the lightness bound by more than a factor of two, and comes quite close to the lower bound of $\left(\frac{2π}{2π+1} +o_ε(1))\right) \cdot \frac{1}ε \approx (0.862 +o_ε(1))\frac{1}ε$ by Elkin and Solomon (FOCS 2011).

Authors: Hung Le, Shay Solomon, Cuong Than, Csaba D. Tóth, Tianyi Zhang

For parameters $α,β\geq 1$, a spanning tree $T$ of a weighted graph $G$ rooted at a designated vertex $r$ is called an $(α,β)$-shallow-light tree (SLT) if (i) for every vertex $v$, $d_T(r,v) \leq α\cdot d_G(r,v)$ (root-stretch $α$), and (ii) $w(T) \leq β\cdot w(\mathsf{MST})$ (lightness $β$). The pioneering work of Khuller, Raghavachari, and Young (SODA 1993) constructed $\left(1+ε, \tfrac{2}ε+1\right)$-SLTs for general weighted graphs, and proved that this tradeoff between root-stretch and lightness is tight even for series-parallel graphs. They further asked whether even a slight improvement, namely reducing the lightness to $\tfrac{2-c}ε$ for any constant $c>0$, is possible in the Euclidean plane. We resolve this longstanding question in the affirmative. Specifically, we show that every Euclidean instance admits an SLT with root-stretch $1+ε$ and lightness at most $\left(\frac{5}{3} + o_ε(1)\right) \cdot \frac{1}ε$, thereby significantly improving upon the longstanding $2/ε$ barrier. As our second main result, we provide a construction of SLTs in the Euclidean plane, with root stretch $1+ε$ and lightness at most $\left(\frac{2π}{\sqrt{4π^2+1}}+o_ε(1)\right)\frac{1}ε \approx (0.987+o_ε(1))\frac{1}ε$. Notably, this reduces the leading $2/ε$ term in the lightness bound by more than a factor of two, and comes quite close to the lower bound of $\left(\frac{2π}{2π+1} +o_ε(1))\right) \cdot \frac{1}ε \approx (0.862 +o_ε(1))\frac{1}ε$ by Elkin and Solomon (FOCS 2011).

Wednesday, August 05 2026, 00:00

The Hard-Core Model on Bipartite Spectral Expanders: Counting and Sampling at All Fugacities

Authors: Ijay Narang, Will Perkins

We study approximate counting and sampling algorithms for the hard-core model on $Δ$-regular bipartite graphs under a spectral expansion condition. Let $M_G$ be the biadjacency matrix of $G$. For every fixed $ξ\in(0,1)$, we give an FPRAS for the hard-core partition function and an efficient approximate sampler whenever \[ λ\leq \frac{1-ξ}{σ_2(M_G)}. \] The main idea is to introduce a family of quadratic tilts in the left-right occupation imbalance and show that each tilted measure can be sampled efficiently using Glauber dynamics. A discrete Gaussian identity expresses the original hard-core model as an exact positive mixture of these tilted measures; truncation and simulated annealing then yield efficient counting and sampling algorithms. For the complementary high-fugacity regime, we refine the polymer-model approach and show that the required phase-dominance and cluster expansion conditions follow from the singular-spectrum bound alone. Combining the two regimes, we obtain efficient approximate counting and sampling at every fugacity $λ>0$ whenever \[ σ_2(M_G)\leq c\left(\frac{Δ^2}{\log(\mathrm eΔ)}\right)^{1/3} \] for an absolute constant $c>0$. In particular, this recovers all-fugacity algorithms for random $Δ$-regular bipartite graphs for all sufficiently large $Δ$, while providing an efficiently verifiable certificate of their success on a given instance.

Authors: Ijay Narang, Will Perkins

We study approximate counting and sampling algorithms for the hard-core model on $Δ$-regular bipartite graphs under a spectral expansion condition. Let $M_G$ be the biadjacency matrix of $G$. For every fixed $ξ\in(0,1)$, we give an FPRAS for the hard-core partition function and an efficient approximate sampler whenever \[ λ\leq \frac{1-ξ}{σ_2(M_G)}. \] The main idea is to introduce a family of quadratic tilts in the left-right occupation imbalance and show that each tilted measure can be sampled efficiently using Glauber dynamics. A discrete Gaussian identity expresses the original hard-core model as an exact positive mixture of these tilted measures; truncation and simulated annealing then yield efficient counting and sampling algorithms. For the complementary high-fugacity regime, we refine the polymer-model approach and show that the required phase-dominance and cluster expansion conditions follow from the singular-spectrum bound alone. Combining the two regimes, we obtain efficient approximate counting and sampling at every fugacity $λ>0$ whenever \[ σ_2(M_G)\leq c\left(\frac{Δ^2}{\log(\mathrm eΔ)}\right)^{1/3} \] for an absolute constant $c>0$. In particular, this recovers all-fugacity algorithms for random $Δ$-regular bipartite graphs for all sufficiently large $Δ$, while providing an efficiently verifiable certificate of their success on a given instance.

Wednesday, August 05 2026, 00:00

Complexity of induced subgraph isomorphism and maximum common induced subgraph parameterized by cluster vertex deletion number

Authors: Tomohiro Koana, Soh Kumabe, Yota Otachi

We study the parameterized complexity of Induced Subgraph Isomorphism (ISI) and Maximum Common Induced Subgraph (MCIS) with respect to the cluster vertex deletion number $k$. For ISI, we give a randomized $O^*(k^{O(k)})$-time algorithm, showing that ISI is fixed-parameter tractable under this parameter and resolving an open question of Hanaka et al. [WALCOM 2026]. Our algorithm is optimal under the Exponential Time Hypothesis (ETH), and is based on a reduction to Exact Multicolored Matching solvable via algebraic techniques. For MCIS, we present a randomized $O^*(2^{O(k^2)})$-time algorithm via a reduction to a weighted variant of Exact Multicolored Matching, and we prove a matching ETH-based lower bound by showing that a $k$-by-$k$ binary matrix feasibility problem with list-constrained rows and columns admits no $O^*(2^{o(k^2)})$-time algorithm, which may be of independent interest. These results reveal that, in this setting, MCIS is strictly harder than ISI. Finally, for the three-graph variant 3-MCIS, we show that it becomes NP-hard already when each input graph has cluster vertex deletion number 2.

Authors: Tomohiro Koana, Soh Kumabe, Yota Otachi

We study the parameterized complexity of Induced Subgraph Isomorphism (ISI) and Maximum Common Induced Subgraph (MCIS) with respect to the cluster vertex deletion number $k$. For ISI, we give a randomized $O^*(k^{O(k)})$-time algorithm, showing that ISI is fixed-parameter tractable under this parameter and resolving an open question of Hanaka et al. [WALCOM 2026]. Our algorithm is optimal under the Exponential Time Hypothesis (ETH), and is based on a reduction to Exact Multicolored Matching solvable via algebraic techniques. For MCIS, we present a randomized $O^*(2^{O(k^2)})$-time algorithm via a reduction to a weighted variant of Exact Multicolored Matching, and we prove a matching ETH-based lower bound by showing that a $k$-by-$k$ binary matrix feasibility problem with list-constrained rows and columns admits no $O^*(2^{o(k^2)})$-time algorithm, which may be of independent interest. These results reveal that, in this setting, MCIS is strictly harder than ISI. Finally, for the three-graph variant 3-MCIS, we show that it becomes NP-hard already when each input graph has cluster vertex deletion number 2.

Wednesday, August 05 2026, 00:00

Uplifting the Superpowers of Worst-Case-Optimal Join Algorithms

Authors: Adrián Gómez-Brandón, Aidan Hogan, Gonzalo Navarro

Worst-case-optimal (wco) join algorithms have demonstrated their power -- in both theory and practice -- to efficiently solve complex Basic Graph Patterns (BGPs). Modern graph query languages, such as SPARQL and GQL, have BGPs at their core, but also have a wide range of other features, including filters (aka.\ selections). Such conditions are typically handled via pre- or post-filtering, before or after processing the BGPs. In this paper we show how to uplift wco join algorithms so as to incorporate such filtering natively, improving efficiency. We demonstrate the superiority of this approach by extending the \textit{Ring} -- a compact index that provides wco resolution of BGPs within almost no extra space on top of the graph -- so as to handle property graphs using our new techniques while retaining compactness. We implement this extension and experimentally show that it outperforms various baseline systems.

Authors: Adrián Gómez-Brandón, Aidan Hogan, Gonzalo Navarro

Worst-case-optimal (wco) join algorithms have demonstrated their power -- in both theory and practice -- to efficiently solve complex Basic Graph Patterns (BGPs). Modern graph query languages, such as SPARQL and GQL, have BGPs at their core, but also have a wide range of other features, including filters (aka.\ selections). Such conditions are typically handled via pre- or post-filtering, before or after processing the BGPs. In this paper we show how to uplift wco join algorithms so as to incorporate such filtering natively, improving efficiency. We demonstrate the superiority of this approach by extending the \textit{Ring} -- a compact index that provides wco resolution of BGPs within almost no extra space on top of the graph -- so as to handle property graphs using our new techniques while retaining compactness. We implement this extension and experimentally show that it outperforms various baseline systems.

Wednesday, August 05 2026, 00:00

A Single-Exponential FPT Algorithm for 2-Vertex-Connectivity Augmentation

Authors: Tomohiro Koana, Soh Kumabe

We study restricted-link augmentation to $2$-vertex-connectivity. An instance consists of a graph $G$, possibly disconnected, a set $L$ of admissible links on its vertices, integer link costs in $\{1,\dots,W\}$, and an integer $k$; the task is to add at most $k$ links of minimum total cost so that the resulting multigraph is $2$-vertex-connected. Recent work gives $O^*(k^{O(k)})$-time algorithms for unweighted $λ$-vertex-connectivity augmentation for every $λ\leq 4$ [Carmesin and Ramanujan, SODA 2026], and an $O^*((k+λ)^{O(k)})$-time algorithm for arbitrary $λ$ [Korhonen and Thorup, arXiv 2026]. We give a deterministic algorithm with running time $O^*(36^kW)$. Thus, for $λ=2$, the unweighted running time improves from $O^*(k^{O(k)})$ to $O^*(36^k)$, and the algorithm also handles link costs with pseudo-polynomial dependence on $W$. We reduce the problem to a boundary-pair variant of $2$-vertex-connected spanning subgraph, where each vertex is assigned a pair of incident edges with an associated pair cost. We solve this variant using a cancellation identity, inspired by Cut&Count [Cygan et al., TALG 2022], obtained by applying Möbius inversion to decompositions along cut vertices: the identity cancels every connected spanning graph with more than one block and keeps exactly the $2$-vertex-connected spanning graphs.

Authors: Tomohiro Koana, Soh Kumabe

We study restricted-link augmentation to $2$-vertex-connectivity. An instance consists of a graph $G$, possibly disconnected, a set $L$ of admissible links on its vertices, integer link costs in $\{1,\dots,W\}$, and an integer $k$; the task is to add at most $k$ links of minimum total cost so that the resulting multigraph is $2$-vertex-connected. Recent work gives $O^*(k^{O(k)})$-time algorithms for unweighted $λ$-vertex-connectivity augmentation for every $λ\leq 4$ [Carmesin and Ramanujan, SODA 2026], and an $O^*((k+λ)^{O(k)})$-time algorithm for arbitrary $λ$ [Korhonen and Thorup, arXiv 2026]. We give a deterministic algorithm with running time $O^*(36^kW)$. Thus, for $λ=2$, the unweighted running time improves from $O^*(k^{O(k)})$ to $O^*(36^k)$, and the algorithm also handles link costs with pseudo-polynomial dependence on $W$. We reduce the problem to a boundary-pair variant of $2$-vertex-connected spanning subgraph, where each vertex is assigned a pair of incident edges with an associated pair cost. We solve this variant using a cancellation identity, inspired by Cut&Count [Cygan et al., TALG 2022], obtained by applying Möbius inversion to decompositions along cut vertices: the identity cancels every connected spanning graph with more than one block and keeps exactly the $2$-vertex-connected spanning graphs.

Wednesday, August 05 2026, 00:00

From b-Coloring to $b^*$-Coloring: Large Girth and Parameterized Complexity

Authors: Jakub Balabán, Oliver Bukor

A b-coloring is a proper vertex coloring such that every color class contains a vertex, a so-called b-vertex, which sees all colors in its closed neighborhood. This type of coloring has been intensively studied from both structural and algorithmic point of view. Recently, Zaker [DAM 2025] introduced the notion of a b*-coloring, which is a b-coloring in which there is a vertex that sees a b-vertex of every color in its closed neighborhood. The b*-chromatic number is the maximum integer k such that there is a b*-coloring with k colors. We partially answer a question posed by Zaker and prove that graphs of girth at least 7 are b*-monotonic, which means that the b*-chromatic number does not increase by taking an induced subgraph. In addition, we discover a class of d-regular graphs of girth at least 5 with b*-chromatic number d+1, which strengthens a result about b-colorings by Dettlaff, Furmańczyk, Peterin, Roux, and Ziemann [AMC 2024]. We also study the parameterized complexity of finding b*-colorings, and show that for many structural parameters, the complexity coincides with that of finding b-colorings. In particular, the b*-chromatic number can be computed in polynomial time on any class of bounded clique-width. For most parameters, the translation from b-colorings is straightforward but for the feedback edge number, the FPT algorithm for b*-colorings is actually much simpler than that for b-colorings by Balabán [MFCS 2026].

Authors: Jakub Balabán, Oliver Bukor

A b-coloring is a proper vertex coloring such that every color class contains a vertex, a so-called b-vertex, which sees all colors in its closed neighborhood. This type of coloring has been intensively studied from both structural and algorithmic point of view. Recently, Zaker [DAM 2025] introduced the notion of a b*-coloring, which is a b-coloring in which there is a vertex that sees a b-vertex of every color in its closed neighborhood. The b*-chromatic number is the maximum integer k such that there is a b*-coloring with k colors. We partially answer a question posed by Zaker and prove that graphs of girth at least 7 are b*-monotonic, which means that the b*-chromatic number does not increase by taking an induced subgraph. In addition, we discover a class of d-regular graphs of girth at least 5 with b*-chromatic number d+1, which strengthens a result about b-colorings by Dettlaff, Furmańczyk, Peterin, Roux, and Ziemann [AMC 2024]. We also study the parameterized complexity of finding b*-colorings, and show that for many structural parameters, the complexity coincides with that of finding b-colorings. In particular, the b*-chromatic number can be computed in polynomial time on any class of bounded clique-width. For most parameters, the translation from b-colorings is straightforward but for the feedback edge number, the FPT algorithm for b*-colorings is actually much simpler than that for b-colorings by Balabán [MFCS 2026].

Wednesday, August 05 2026, 00:00

Fixed Budget vs. Covering Target: The Partial Set Cover Boundary for Bounded VC-Dimension

Authors: Madhumita Kundu, Souvik Saha, Saket Saurabh, Anannya Upasana

Maximum Coverage and Partial Set Cover are fundamental parameterized covering problems. The former fixes a budget $k$ and maximizes coverage; the latter meets a target with as few sets as possible. Badanidiyuru, Kleinberg, and Lee (SoCG 2012) give an EPAS for the former on bounded-VC set systems, while Jain et al. (SODA 2023) show that on $K_{d,d}$-free incidence graphs, $k+1$ sets suffice whenever $k$ sets meet the target. We ask whether this guarantee extends to all bounded-VC set systems. Our first result is negative. Unless FPT = W[1], Partial Set Cover admits no parameterized $(2-δ)$-approximation even at VC-dimension seven. Under ETH, it has no parameterized approximation scheme there and no $2^{o(d)}$-approximation at VC-dimension $d$. On the positive side, bounded semi-ladder index restores this guarantee. It is stronger than bounded VC-dimension but strictly generalizes the $K_{d,d}$-free setting. For Weighted Partial Set Cover, if $k$ sets cover weight $W$, we find $k+1$ sets covering weight $W$ in $2^{O(Γk\log k)}N$ time, where $Γ$ is the downward intersection complexity and $N$ is the input size. The framework supports per-class targets and matroid independence, with applications to partial dominating set and geometric and bounded-size covering. Finally, we give a deterministic FPT reduction from Weighted CC-MaxSAT to a bounded family of Weighted Maximum Coverage instances, preserving incidence structure and approximation schemes with constant-factor accuracy loss. This gives an EPAS at bounded semi-ladder index. We improve the deterministic BKL bounded-VC implementation; combined with our reduction, it yields a $2^{\widetilde{O}(kd/\varepsilon)}N^{O(1)}$-time EPAS for bounded-VC Weighted CC-MaxSAT.

Authors: Madhumita Kundu, Souvik Saha, Saket Saurabh, Anannya Upasana

Maximum Coverage and Partial Set Cover are fundamental parameterized covering problems. The former fixes a budget $k$ and maximizes coverage; the latter meets a target with as few sets as possible. Badanidiyuru, Kleinberg, and Lee (SoCG 2012) give an EPAS for the former on bounded-VC set systems, while Jain et al. (SODA 2023) show that on $K_{d,d}$-free incidence graphs, $k+1$ sets suffice whenever $k$ sets meet the target. We ask whether this guarantee extends to all bounded-VC set systems. Our first result is negative. Unless FPT = W[1], Partial Set Cover admits no parameterized $(2-δ)$-approximation even at VC-dimension seven. Under ETH, it has no parameterized approximation scheme there and no $2^{o(d)}$-approximation at VC-dimension $d$. On the positive side, bounded semi-ladder index restores this guarantee. It is stronger than bounded VC-dimension but strictly generalizes the $K_{d,d}$-free setting. For Weighted Partial Set Cover, if $k$ sets cover weight $W$, we find $k+1$ sets covering weight $W$ in $2^{O(Γk\log k)}N$ time, where $Γ$ is the downward intersection complexity and $N$ is the input size. The framework supports per-class targets and matroid independence, with applications to partial dominating set and geometric and bounded-size covering. Finally, we give a deterministic FPT reduction from Weighted CC-MaxSAT to a bounded family of Weighted Maximum Coverage instances, preserving incidence structure and approximation schemes with constant-factor accuracy loss. This gives an EPAS at bounded semi-ladder index. We improve the deterministic BKL bounded-VC implementation; combined with our reduction, it yields a $2^{\widetilde{O}(kd/\varepsilon)}N^{O(1)}$-time EPAS for bounded-VC Weighted CC-MaxSAT.

Wednesday, August 05 2026, 00:00

Expected cost in Combinatorial Optimization under color constraints

Authors: Patrick Bennett, Alan Frieze, Wesley Pegden

We present an average case model of classical problems in combinatorial optimization where there are color constraints. In all cases we seek some (spanning) sub-structure of a complete graph of minimum cost. The edges are randomly colored either red or blue. We bias against the red edges by placing a bound on the number of them that are allowed in our structure. This bound will be lower w.h.p. than what would occur without discrimination. We examine the effect of this bias on the minimum cost of a desired structure. We consider minimum cost spanning trees, shortest paths, minimum cost perfect matchings and the asymmetric traveling salesperson problem.

Authors: Patrick Bennett, Alan Frieze, Wesley Pegden

We present an average case model of classical problems in combinatorial optimization where there are color constraints. In all cases we seek some (spanning) sub-structure of a complete graph of minimum cost. The edges are randomly colored either red or blue. We bias against the red edges by placing a bound on the number of them that are allowed in our structure. This bound will be lower w.h.p. than what would occur without discrimination. We examine the effect of this bias on the minimum cost of a desired structure. We consider minimum cost spanning trees, shortest paths, minimum cost perfect matchings and the asymmetric traveling salesperson problem.

Wednesday, August 05 2026, 00:00

Quality Control Algorithms for Pattern Counting

Authors: Cassandra Marcussen, Ronitt Rubinfeld, Madhu Sudan

In recent work, Marcussen, Rubinfeld, and Sudan introduced the notion of quality control problems, which aim to capture the task of determining if a given input is truly random. Formally, their goal is to accept typical inputs from the specified distribution while rejecting every input whose value of a specified statistic is far from the distributional baseline. This captures the empirical practice of using specified statistics as a proxy for the quality of randomness. Empirical algorithms, however, have not exploited the asymmetry in the definition of quality control problems, which require soundness guarantees in the worst-case while only seeking average-case completeness. Their work abstracted a problem definition emphasizing this asymmetry and used it to give efficient quality control algorithms for assessing the randomness of graphs. In this work, we introduce and study quality control problems over sequences, where the goal is to distinguish a sequence of i.i.d. characters from sequences where some specified pattern appears too often (or too infrequently) as a subsequence. We consider this problem in both the finite-alphabet setting and for real-valued sequences. We refer to the former setting as the pattern counting problem. In the latter case, the natural notion of a pattern is to consider the relative ordering of the characters in the subsequence, and we refer to this as the permutation pattern counting problem. Algorithms to approximately count (permutation) patterns of length $k$ in a worst-case sequence of length $n$ can provably require exponential in $k$ queries into the sequence. In contrast, we show that by taking advantage of the asymmetry in the definition of quality control, we give algorithms that run in poly$(k)$ time to solve these problems. We also prove that any quality control algorithm (over some natural distributions) requires superlinear queries in $k$.

Authors: Cassandra Marcussen, Ronitt Rubinfeld, Madhu Sudan

In recent work, Marcussen, Rubinfeld, and Sudan introduced the notion of quality control problems, which aim to capture the task of determining if a given input is truly random. Formally, their goal is to accept typical inputs from the specified distribution while rejecting every input whose value of a specified statistic is far from the distributional baseline. This captures the empirical practice of using specified statistics as a proxy for the quality of randomness. Empirical algorithms, however, have not exploited the asymmetry in the definition of quality control problems, which require soundness guarantees in the worst-case while only seeking average-case completeness. Their work abstracted a problem definition emphasizing this asymmetry and used it to give efficient quality control algorithms for assessing the randomness of graphs. In this work, we introduce and study quality control problems over sequences, where the goal is to distinguish a sequence of i.i.d. characters from sequences where some specified pattern appears too often (or too infrequently) as a subsequence. We consider this problem in both the finite-alphabet setting and for real-valued sequences. We refer to the former setting as the pattern counting problem. In the latter case, the natural notion of a pattern is to consider the relative ordering of the characters in the subsequence, and we refer to this as the permutation pattern counting problem. Algorithms to approximately count (permutation) patterns of length $k$ in a worst-case sequence of length $n$ can provably require exponential in $k$ queries into the sequence. In contrast, we show that by taking advantage of the asymmetry in the definition of quality control, we give algorithms that run in poly$(k)$ time to solve these problems. We also prove that any quality control algorithm (over some natural distributions) requires superlinear queries in $k$.

Wednesday, August 05 2026, 00:00

Sensitivity and Size Relationships of the Lempel-Ziv Factorization

Authors: Hiroki Shibata, Yuto Fujie

The Lempel-Ziv (LZ) factorization is one of the most fundamental methods for compressing highly repetitive strings, and the number of phrases in its factorization is considered a repetitiveness measure. Sensitivity to an edit operation measures the maximum increase in a repetitiveness measure when the operation is applied to a string. While asymptotically tight bounds are known for the sensitivity of the LZ factorization to single-character edits, whether its multiplicative sensitivity is bounded by a constant has remained open for operations that change a large part of the structure of a string, such as prefix deletion, substring deletion, cyclic rotation, and string reversal. We resolve this question. For each of these four operations, we construct a family of strings in which a string of length $n$ has sensitivity $Ω(\log n)$ to that operation. We also determine the size relationships among the LZ factorization, collage systems and the lex-parse. We construct a family of strings whose LZ factorizations are $Ω(\log n)$ times larger than their minimum collage systems, and a family of strings whose lex-parses are $Ω(\log n)$ times larger than their LZ factorizations. All of these lower bounds are asymptotically tight, matching $O(\log n)$ upper bounds.

Authors: Hiroki Shibata, Yuto Fujie

The Lempel-Ziv (LZ) factorization is one of the most fundamental methods for compressing highly repetitive strings, and the number of phrases in its factorization is considered a repetitiveness measure. Sensitivity to an edit operation measures the maximum increase in a repetitiveness measure when the operation is applied to a string. While asymptotically tight bounds are known for the sensitivity of the LZ factorization to single-character edits, whether its multiplicative sensitivity is bounded by a constant has remained open for operations that change a large part of the structure of a string, such as prefix deletion, substring deletion, cyclic rotation, and string reversal. We resolve this question. For each of these four operations, we construct a family of strings in which a string of length $n$ has sensitivity $Ω(\log n)$ to that operation. We also determine the size relationships among the LZ factorization, collage systems and the lex-parse. We construct a family of strings whose LZ factorizations are $Ω(\log n)$ times larger than their minimum collage systems, and a family of strings whose lex-parses are $Ω(\log n)$ times larger than their LZ factorizations. All of these lower bounds are asymptotically tight, matching $O(\log n)$ upper bounds.

Wednesday, August 05 2026, 00:00

One Discrete Gaussian Sample in $2^{n/2+o(n)}$ Time

Authors: Jiseung Kim

Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS; STOC 2015) sample $2^{n/2}$ discrete Gaussians at an arbitrary parameter in $2^{n+o(n)}$ time, and above smoothing in $2^{n/2+o(n)}$ time. They ask whether the latter bound suffices for one sample at an arbitrary parameter. We answer this question affirmatively: for every rank-$n$ lattice $L\subseteq\R^n$ specified by a rational basis and every rational $s^2>0$, we produce one sample from $D_{L,s}$ within statistical distance $\exp(-Ω(n^3))$ in expected $2^{n/2+o(n)}$ time and $2^{n/2+o(n)}$ space on every execution. The algorithm samples from random superlattices that are smooth at the required scale with constant probability and outputs the first point in $L$; a Gaussian-mass comparison shows that the $2^{n/2}$ samples produced by one ADRS call contain a point of $L$ with inverse-polynomial probability. The factor $2^{n/2}$ is tight in this Gaussian-mass comparison. For every fixed rational $α<1.4697$, the same comparison gives a sub-$2^n$ algorithm for exact CVP on targets satisfying $\dist(y,L)\leαλ_1(L)$, without a uniqueness assumption, and an exact-SVP algorithm in $2^{0.7315n+o(n)}$ time.

Authors: Jiseung Kim

Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS; STOC 2015) sample $2^{n/2}$ discrete Gaussians at an arbitrary parameter in $2^{n+o(n)}$ time, and above smoothing in $2^{n/2+o(n)}$ time. They ask whether the latter bound suffices for one sample at an arbitrary parameter. We answer this question affirmatively: for every rank-$n$ lattice $L\subseteq\R^n$ specified by a rational basis and every rational $s^2>0$, we produce one sample from $D_{L,s}$ within statistical distance $\exp(-Ω(n^3))$ in expected $2^{n/2+o(n)}$ time and $2^{n/2+o(n)}$ space on every execution. The algorithm samples from random superlattices that are smooth at the required scale with constant probability and outputs the first point in $L$; a Gaussian-mass comparison shows that the $2^{n/2}$ samples produced by one ADRS call contain a point of $L$ with inverse-polynomial probability. The factor $2^{n/2}$ is tight in this Gaussian-mass comparison. For every fixed rational $α<1.4697$, the same comparison gives a sub-$2^n$ algorithm for exact CVP on targets satisfying $\dist(y,L)\leαλ_1(L)$, without a uniqueness assumption, and an exact-SVP algorithm in $2^{0.7315n+o(n)}$ time.

Wednesday, August 05 2026, 00:00

Diameter-Free Distributed Frequency Control for Graph Coloring in the CONGEST Model

Authors: Amit Nir, David Peleg

This paper presents two randomized proper-coloring algorithms that control color frequencies in the synchronous CONGEST model without paying a diameter-dependent coordination cost. Let $λ\geq 1$ denote the desired failure exponent. For every fixed $δ> 0$, the first algorithm uses $χ= \lceil (2+δ)Δ\rceil$ colors and, with probability at least $1 - n^{-λ}$, outputs a proper coloring that bounds the deviation of every color frequency from $n/χ$ by $O_δ(\sqrt{(λ+1)(n/χ)\lg n} + (λ+1)\lg n)$. Under an explicit load condition, this additive guarantee yields two-sided relative balance. The second algorithm works with every $χ> Δ$ and gives a one-sided frequency cap controlled by the palette slack $χ- Δ$. In particular, it uses $Δ+ \lceil (Δ+1)/\lceil \ln n \rceil \rceil$ colors and caps every used color class by $O((λ+1)(σ\lg^2 n + \lg n))$, where $σ= n/(Δ+1)$. Both algorithms run in $O((λ+1)\lg n)$ rounds, with no dependence on the network diameter; for the first algorithm, the multiplicative constant in the time bound depends on $δ$.

Authors: Amit Nir, David Peleg

This paper presents two randomized proper-coloring algorithms that control color frequencies in the synchronous CONGEST model without paying a diameter-dependent coordination cost. Let $λ\geq 1$ denote the desired failure exponent. For every fixed $δ> 0$, the first algorithm uses $χ= \lceil (2+δ)Δ\rceil$ colors and, with probability at least $1 - n^{-λ}$, outputs a proper coloring that bounds the deviation of every color frequency from $n/χ$ by $O_δ(\sqrt{(λ+1)(n/χ)\lg n} + (λ+1)\lg n)$. Under an explicit load condition, this additive guarantee yields two-sided relative balance. The second algorithm works with every $χ> Δ$ and gives a one-sided frequency cap controlled by the palette slack $χ- Δ$. In particular, it uses $Δ+ \lceil (Δ+1)/\lceil \ln n \rceil \rceil$ colors and caps every used color class by $O((λ+1)(σ\lg^2 n + \lg n))$, where $σ= n/(Δ+1)$. Both algorithms run in $O((λ+1)\lg n)$ rounds, with no dependence on the network diameter; for the first algorithm, the multiplicative constant in the time bound depends on $δ$.

Wednesday, August 05 2026, 00:00

Distributed Algorithms for Near-Equitable Coloring

Authors: Amit Nir, David Peleg

For an $n$-vertex graph of maximum degree $Δ$ and diameter $D$, an equitable $(Δ+1)$-coloring is a vertex coloring where the frequency of each color (namely, the number of vertices it colors) are all equal to $σ=n/(Δ+1)$ (up to rounding). The Hajnal-Szemerédi Theorem guarantees the existence of such a coloring for every graph, and an $O(n^2Δ)$ time sequential algorithm is known for computing such a coloring. Here, we study near-equitable graph coloring in distributed networks. The main question of interest is how close one can remain to the desired palette size of $Δ+1$ while computing, in few distributed rounds, a coloring whose frequencies are close to $σ$. It appears that these two conflicting parameters exhibit a tradeoff, which we attempt to explore. We present a suite of fast randomized distributed algorithms representing varying points on this tradeoff, analyze their properties, and study their time complexity in the sequential, CONGEST and Congested Clique (CC) models.

Authors: Amit Nir, David Peleg

For an $n$-vertex graph of maximum degree $Δ$ and diameter $D$, an equitable $(Δ+1)$-coloring is a vertex coloring where the frequency of each color (namely, the number of vertices it colors) are all equal to $σ=n/(Δ+1)$ (up to rounding). The Hajnal-Szemerédi Theorem guarantees the existence of such a coloring for every graph, and an $O(n^2Δ)$ time sequential algorithm is known for computing such a coloring. Here, we study near-equitable graph coloring in distributed networks. The main question of interest is how close one can remain to the desired palette size of $Δ+1$ while computing, in few distributed rounds, a coloring whose frequencies are close to $σ$. It appears that these two conflicting parameters exhibit a tradeoff, which we attempt to explore. We present a suite of fast randomized distributed algorithms representing varying points on this tradeoff, analyze their properties, and study their time complexity in the sequential, CONGEST and Congested Clique (CC) models.

Wednesday, August 05 2026, 00:00

TR26-132 | Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms | Arpon Basu, Joshua Brakensiek, Yeyuan Chen, Aaron (Louie) Putterman, Victor Reis, Zihan Zhang

from ECCC Papers

We extend the recent work of Reis and Rothvoss on sparsifying sums of $\ell_1$ norms to the more general task of sparsifying (Minkowski) sums of centrally symmetric, convex sets. As our main result, we prove that for any $\varepsilon > 0$ and centrally symmetric, convex sets $C_1, \ldots, C_m\subseteq\mathbb R^n$ there is a choice of weights $\lambda_1, \dots , \lambda_m \in \mathbb R_{\geq 0}$ such that at most $O(n / \varepsilon^2)$ of the weights are non-zero, and \[(1 - \varepsilon)\cdot C\subseteq\sum_{i = 1}^m\lambda_i\cdot C_i\subseteq(1 + \varepsilon)\cdot C,\] where $C:= C_1 + \cdots + C_m$ refers to the Minkowski sums of the sets $C_1, \ldots, C_m$, and $\lambda\cdot C$ refers to the dilation of the set $C$. As immediate applications of this result, we obtain sparsifiers of size $O(n / \varepsilon^2)$ for sparsifying sums of seminorms in $n$-dimensional space, improving on the $O\left ( \frac{n \log(n/\varepsilon) \cdot \log^{2.5}(n)}{\varepsilon^2} \right )$ size sparsifiers from the work of Jambulapati, Lee, Liu, and Sidford (FOCS 2023). This further yields optimal size hypergraph cut sparsifiers with $O(n / \varepsilon^2)$ hyperedges, improving on the $O(n \log(n) / \varepsilon^2)$ size sparsifiers from the work of Chen, Khanna, and Nagda (FOCS 2020). More generally, this also gives optimal size sparsifiers for sums of symmetric submodular functions.

Tuesday, August 04 2026, 17:08

Nearly tight lower bounds for estimating quantum functionals: Uhlmann fidelity, trace distance, and von Neumann entropy

Authors: Qisheng Wang

In this paper, we present a unified framework for proving lower bounds for estimating functionals of quantum states. We therefore resolve several open problems by establishing lower bounds that match known upper bounds: we show that it requires $\widetildeΩ(N^2)$ samples to estimate the Uhlmann fidelity, trace distance, and von Neumann entropy. Moreover, they immediately imply matching query lower bounds of $\widetildeΩ(N)$ by quantum sample-to-query lifting. These lower bounds imply the near-optimality of a dozen quantum algorithms since 2016.

Authors: Qisheng Wang

In this paper, we present a unified framework for proving lower bounds for estimating functionals of quantum states. We therefore resolve several open problems by establishing lower bounds that match known upper bounds: we show that it requires $\widetildeΩ(N^2)$ samples to estimate the Uhlmann fidelity, trace distance, and von Neumann entropy. Moreover, they immediately imply matching query lower bounds of $\widetildeΩ(N)$ by quantum sample-to-query lifting. These lower bounds imply the near-optimality of a dozen quantum algorithms since 2016.

Tuesday, August 04 2026, 00:00

An Argmax Principle for Sum-of-Squares Relaxations on the Sphere

Authors: Fernando Jeronimo Granha, Pei Wu, Haochen Xu

We develop an argmax principle for analyzing sum-of-squares relaxations of optimization problems over the unit sphere. Given a feasible pseudo-expectation, we form a polynomial of high-order pseudo-moments, such as $Φ_k(u)=\widetilde{\mathbb E}\langle x,u\rangle^{2k}$. Our guiding principle is that its maximizers are rounding candidates: their local and global optimality conditions reveal the reweighed pseudo-expectation inequalities governing SoS convergence. This viewpoint unifies several problems previously analyzed by rather different techniques. We obtain three results. First, for Best Separable State, we give a degree-$O(\sqrt{n/ε})$ SoS analysis for approximating $h_{\mathrm{sep}}(P)$ in the perfect-completeness regime, improving and simplifying Barak, Kothari and Steurer (STOC'17). The dependence is essentially tight for inverse-linear gap under the Exponential-Time Hypothesis, matching hardness from $\mathrm{QMA}(2)$ protocols. Second, for the matrix $2\to4$ norm, degree-$O(\sqrt n/ε)$ SoS gives a multiplicative $(1+ε)$ approximation. Barak et al. (STOC'12) previously gave a comparable-time constant-gap decision algorithm; our result gives a multiplicative guarantee and extends to a family of $p\to q$ norms with even $q$. Finally, for degree-$d$ polynomial optimization, we recover the convergence theorem of Bhattiprolu et al. (FOCS'17) with a shorter, more direct proof: degree-$k$ SoS gives approximation ratio $O_d((n/k)^{d/2-1})$. The paper introduces no new relaxation. Instead, the high-moment argmax gives a common way to read an SoS solution, unifying previously separate convergence analyses and yielding sharper bounds or simpler proofs.

Authors: Fernando Jeronimo Granha, Pei Wu, Haochen Xu

We develop an argmax principle for analyzing sum-of-squares relaxations of optimization problems over the unit sphere. Given a feasible pseudo-expectation, we form a polynomial of high-order pseudo-moments, such as $Φ_k(u)=\widetilde{\mathbb E}\langle x,u\rangle^{2k}$. Our guiding principle is that its maximizers are rounding candidates: their local and global optimality conditions reveal the reweighed pseudo-expectation inequalities governing SoS convergence. This viewpoint unifies several problems previously analyzed by rather different techniques. We obtain three results. First, for Best Separable State, we give a degree-$O(\sqrt{n/ε})$ SoS analysis for approximating $h_{\mathrm{sep}}(P)$ in the perfect-completeness regime, improving and simplifying Barak, Kothari and Steurer (STOC'17). The dependence is essentially tight for inverse-linear gap under the Exponential-Time Hypothesis, matching hardness from $\mathrm{QMA}(2)$ protocols. Second, for the matrix $2\to4$ norm, degree-$O(\sqrt n/ε)$ SoS gives a multiplicative $(1+ε)$ approximation. Barak et al. (STOC'12) previously gave a comparable-time constant-gap decision algorithm; our result gives a multiplicative guarantee and extends to a family of $p\to q$ norms with even $q$. Finally, for degree-$d$ polynomial optimization, we recover the convergence theorem of Bhattiprolu et al. (FOCS'17) with a shorter, more direct proof: degree-$k$ SoS gives approximation ratio $O_d((n/k)^{d/2-1})$. The paper introduces no new relaxation. Instead, the high-moment argmax gives a common way to read an SoS solution, unifying previously separate convergence analyses and yielding sharper bounds or simpler proofs.

Tuesday, August 04 2026, 00:00

Optimal Quantum de Finetti Theorems via Argmax Rounding

Authors: Fernando Granha Jeronimo, Pei Wu, Haochen Xu

We prove optimal finite quantum de Finetti upper bounds. Given a bosonic state $ρ_N\in D(\mathrm{Sym}^N(\mathbb C^d))$, there is a probability measure $ν$ on the unit sphere such that \[ \left\| ρ_N^{(2)}-\int |u\rangle\langle u|^{\otimes 2}\,dν(u) \right\|_1 \le \frac{\sqrt{d-1}}{N-1}. \] By purification, the bosonic theorem also gives the optimal $O(d/N)$ upper bound for arbitrary exchangeable states. These results settle the dimension dependence left open by Christandl, König, Mitchison, and Renner (CMP 2007). The proof casts de Finetti approximation as sum-of-squares rounding and applies the argmax method of Jeronimo, Wu, and Xu (manuscript 2026). More generally, $t$-site marginals satisfy $O(t\sqrt d/N)$ bosonic and $O(td/N)$ permutation-invariant bounds. Our proof formulates de Finetti approximation as the integrality gap of a symmetric-extension semidefinite program and rounds an optimum by the argmax principle. The sharp bounds have several consequences. For every fixed $\varepsilon\in(0,1)$, we construct a channel with input dimension $D=\exp(O_\varepsilon(\sqrt d\log d))=\exp(o(d))$ whose outputs are $\varepsilon$-close to separable states of local dimension $d$ and whose image contains every such separable state, thereby refuting Watrous's disentangler conjecture. We also obtain deterministic $\exp(\widetilde O(\sqrt d/\varepsilon))$-time algorithms for explicit Best Separable State without perfect completeness and for trace-distance separability testing. Finally, spectral truncation gives the first dimension-free bosonic de Finetti theorem in Hilbert--Schmidt distance, with the optimal rate $Θ(N^{-1/2})$ when the dimension may grow.

Authors: Fernando Granha Jeronimo, Pei Wu, Haochen Xu

We prove optimal finite quantum de Finetti upper bounds. Given a bosonic state $ρ_N\in D(\mathrm{Sym}^N(\mathbb C^d))$, there is a probability measure $ν$ on the unit sphere such that \[ \left\| ρ_N^{(2)}-\int |u\rangle\langle u|^{\otimes 2}\,dν(u) \right\|_1 \le \frac{\sqrt{d-1}}{N-1}. \] By purification, the bosonic theorem also gives the optimal $O(d/N)$ upper bound for arbitrary exchangeable states. These results settle the dimension dependence left open by Christandl, König, Mitchison, and Renner (CMP 2007). The proof casts de Finetti approximation as sum-of-squares rounding and applies the argmax method of Jeronimo, Wu, and Xu (manuscript 2026). More generally, $t$-site marginals satisfy $O(t\sqrt d/N)$ bosonic and $O(td/N)$ permutation-invariant bounds. Our proof formulates de Finetti approximation as the integrality gap of a symmetric-extension semidefinite program and rounds an optimum by the argmax principle. The sharp bounds have several consequences. For every fixed $\varepsilon\in(0,1)$, we construct a channel with input dimension $D=\exp(O_\varepsilon(\sqrt d\log d))=\exp(o(d))$ whose outputs are $\varepsilon$-close to separable states of local dimension $d$ and whose image contains every such separable state, thereby refuting Watrous's disentangler conjecture. We also obtain deterministic $\exp(\widetilde O(\sqrt d/\varepsilon))$-time algorithms for explicit Best Separable State without perfect completeness and for trace-distance separability testing. Finally, spectral truncation gives the first dimension-free bosonic de Finetti theorem in Hilbert--Schmidt distance, with the optimal rate $Θ(N^{-1/2})$ when the dimension may grow.

Tuesday, August 04 2026, 00:00

Optimal Unambiguous DNFs and Alon-Saks-Seymour

Authors: Chirag Pabbaraju

We construct unambiguous DNFs having width $O(n)$ but $0$-certificate complexity $Ω(n^2)$. By utilizing the special structure of these DNFs, we prove a lifting theorem with a constant-sized gadget that lifts the DNF to a communication problem, while losslessly translating the separation in certificate complexity to a separation in communication complexity. This leads to an optimal refutation of the Alon-Saks-Seymour conjecture, as well as an optimal communication lower bound for the Clique versus Independent Set problem, improving the previous results of Balodis, Ben-David, Göös, Jain and Kothari (FOCS 2021, SICOMP 2023) by several doubly logarithmic factors. As further applications of our construction to query complexity and learning theory, we exhibit: (a) a family of Boolean functions that has an optimal quartic separation between certificate complexity and approximate degree, and (b) a sample compression lower bound of $Ω(\sqrt{\log c})$ for multiclass concept classes over $c$ labels.

Authors: Chirag Pabbaraju

We construct unambiguous DNFs having width $O(n)$ but $0$-certificate complexity $Ω(n^2)$. By utilizing the special structure of these DNFs, we prove a lifting theorem with a constant-sized gadget that lifts the DNF to a communication problem, while losslessly translating the separation in certificate complexity to a separation in communication complexity. This leads to an optimal refutation of the Alon-Saks-Seymour conjecture, as well as an optimal communication lower bound for the Clique versus Independent Set problem, improving the previous results of Balodis, Ben-David, Göös, Jain and Kothari (FOCS 2021, SICOMP 2023) by several doubly logarithmic factors. As further applications of our construction to query complexity and learning theory, we exhibit: (a) a family of Boolean functions that has an optimal quartic separation between certificate complexity and approximate degree, and (b) a sample compression lower bound of $Ω(\sqrt{\log c})$ for multiclass concept classes over $c$ labels.

Tuesday, August 04 2026, 00:00

The Complete Extended Euclidean Scheme Is Not in Piecewise Arithmetic $\mathrm{AC}^0$

Authors: Amiel Ferman

We prove that the complete extended Euclidean scheme for pairs of monic univariate polynomials over a field of characteristic zero cannot be computed by polynomial-size, constant-depth piecewise arithmetic circuits in the select-gate model of Andrews and Wigderson. In fact, the lower bound already holds for the simpler task of outputting the complete padded list of nonzero Euclidean remainders. We show that a suitable Hankel determinant can be recovered from fixed coordinates of the complete Euclidean remainder sequence on a nonempty Zariski-open set. The connection is provided by a middle principal subresultant coefficient. A generic removal of select gates, followed by constant-depth division elimination, would therefore turn any piecewise constant-depth algorithm for the complete remainder sequence into an ordinary constant-depth circuit for Hankel determinants, contradicting the lower bound above. We also show that the same obstruction applies to several related outputs. It yields lower bounds for the complete polynomial continued-fraction expansion and for the complete profile of fixed-bound principal subresultant coefficients, since each of these outputs directly exposes the Hankel determinant used in the Euclidean reduction. In addition, we obtain a lower bound for normalized subdiagonal Pad'e approximation: even the normalized denominator alone suffices, through polynomially many parallel Pad'e computations and a telescoping product of determinantal ratios, to recover the same consecutive Hankel determinant. Consequently, none of these problems can be computed by polynomial-size, constant-depth piecewise arithmetic circuits.

Authors: Amiel Ferman

We prove that the complete extended Euclidean scheme for pairs of monic univariate polynomials over a field of characteristic zero cannot be computed by polynomial-size, constant-depth piecewise arithmetic circuits in the select-gate model of Andrews and Wigderson. In fact, the lower bound already holds for the simpler task of outputting the complete padded list of nonzero Euclidean remainders. We show that a suitable Hankel determinant can be recovered from fixed coordinates of the complete Euclidean remainder sequence on a nonempty Zariski-open set. The connection is provided by a middle principal subresultant coefficient. A generic removal of select gates, followed by constant-depth division elimination, would therefore turn any piecewise constant-depth algorithm for the complete remainder sequence into an ordinary constant-depth circuit for Hankel determinants, contradicting the lower bound above. We also show that the same obstruction applies to several related outputs. It yields lower bounds for the complete polynomial continued-fraction expansion and for the complete profile of fixed-bound principal subresultant coefficients, since each of these outputs directly exposes the Hankel determinant used in the Euclidean reduction. In addition, we obtain a lower bound for normalized subdiagonal Pad'e approximation: even the normalized denominator alone suffices, through polynomially many parallel Pad'e computations and a telescoping product of determinantal ratios, to recover the same consecutive Hankel determinant. Consequently, none of these problems can be computed by polynomial-size, constant-depth piecewise arithmetic circuits.

Tuesday, August 04 2026, 00:00

Alphabet-Preserving Lifting for the Log-Rank Conjecture