Theory of Computing Report

Authors: Huanyi Zhou

The $(\min,+)$ convolution is a central problem in fine-grained complexity, and whether it admits a truly subquadratic algorithm remains open. We study it through tropical polynomials, where $(\min,+)$ convolution is exactly polynomial multiplication. We introduce tropical decomposition width, a parameter measuring how finely a tropical polynomial can be decomposed into low-degree factors. We prove modular convexity theorems showing that bounded tropical decomposition width forces strong convexity on arithmetic subpolynomials. This yields deterministic algorithms for computing $a\otimes b$ in $O(n\max(\operatorname{tdw}(a),\operatorname{tdw}(b))^2)$ time when the width is given, and in $O(ne^{\min(\operatorname{tdw}(a),\operatorname{tdw}(b))(1+o(1))})$ time otherwise, without requiring a decomposition. For Multiple-Sequence $(\min,+)$ Convolution, we give a randomized algorithm running in $O(kn^2\sqrt{\min(k,n)}\log^{1.5}(kn))$ time for $k$ sequences of length at most $n$, improving the natural $O(k^2n^2)$ bound. We also obtain conditional lower bounds, a faster single-entry algorithm, and new upper bounds for Multiple-Choice Knapsack. Finally, bounded-decomposition-width classes admit interpolation algebras of finite generating rank, whereas distinguishing all tropical polynomials of degree at most $n$ requires rank exactly $\lfloor n/2\rfloor+1$. We further show that tropical decomposition width cannot decrease under any flat $\mathbb T$-algebra extension. These results connect efficient tropical multiplication with structural rigidity.

Authors: Huanyi Zhou

The $(\min,+)$ convolution is a central problem in fine-grained complexity, and whether it admits a truly subquadratic algorithm remains open. We study it through tropical polynomials, where $(\min,+)$ convolution is exactly polynomial multiplication. We introduce tropical decomposition width, a parameter measuring how finely a tropical polynomial can be decomposed into low-degree factors. We prove modular convexity theorems showing that bounded tropical decomposition width forces strong convexity on arithmetic subpolynomials. This yields deterministic algorithms for computing $a\otimes b$ in $O(n\max(\operatorname{tdw}(a),\operatorname{tdw}(b))^2)$ time when the width is given, and in $O(ne^{\min(\operatorname{tdw}(a),\operatorname{tdw}(b))(1+o(1))})$ time otherwise, without requiring a decomposition. For Multiple-Sequence $(\min,+)$ Convolution, we give a randomized algorithm running in $O(kn^2\sqrt{\min(k,n)}\log^{1.5}(kn))$ time for $k$ sequences of length at most $n$, improving the natural $O(k^2n^2)$ bound. We also obtain conditional lower bounds, a faster single-entry algorithm, and new upper bounds for Multiple-Choice Knapsack. Finally, bounded-decomposition-width classes admit interpolation algebras of finite generating rank, whereas distinguishing all tropical polynomials of degree at most $n$ requires rank exactly $\lfloor n/2\rfloor+1$. We further show that tropical decomposition width cannot decrease under any flat $\mathbb T$-algebra extension. These results connect efficient tropical multiplication with structural rigidity.

Friday, August 14 2026, 00:00

Fortune's Bounty: Taming Complexity by Trimming Trees --- A Hands-On Problem-Solving Experience in Advanced Complexity Suitable for Introductory Students

Authors: Kimberly Fluet, Lane A. Hemaspaandra, Christopher M. Homan

This article provides an assignment designed to let undergraduate students who have completed an undergraduate CS1/CS2 sequence try to themselves, in groups, prove Fortune's Theorem. (Fortune's Theorem states that if the complement of the Boolean satisfiability problem polynomial-time reduces to a sparse set, then the Boolean satisfiability problem is polynomial-time computable. The assignment does not assume that students have previously seen the Boolean satisfiability problem, polynomial-time reductions, or sparse sets. Rather, it teaches those within the assignment. Note: Reworded into the technical vocabulary of complexity theory, Fortune's Theorem states that no sparse set is coNP-hard unless P=NP. Fortune's Theorem was a major advance in the understanding of the relationship between hardness and density.) We provide both the assignment handout (as the main body of this report plus Appendix A) and a solution to the assignment (as Appendix B, which would of course not be made available to the students until after they had handed in the assignment). The assignment handout, though the instructor can change this, is framed as having the students starting the assignment in teams in class for a whole class session, and then finishing it in those same teams as a take-home assignment, and handing it in before the next class session. We have found that student groups often succeed, partially or completely, in this challenge. This can mean a lot to the students: they see that they were able to make an advance that, when it was first obtained, appeared in what was arguably at the time the top journal venue for complexity theory research. This can give them confidence that they have substantial problem-solving skills (which basically means research skills) when they truly apply themselves to a given challenge.

Authors: Kimberly Fluet, Lane A. Hemaspaandra, Christopher M. Homan

This article provides an assignment designed to let undergraduate students who have completed an undergraduate CS1/CS2 sequence try to themselves, in groups, prove Fortune's Theorem. (Fortune's Theorem states that if the complement of the Boolean satisfiability problem polynomial-time reduces to a sparse set, then the Boolean satisfiability problem is polynomial-time computable. The assignment does not assume that students have previously seen the Boolean satisfiability problem, polynomial-time reductions, or sparse sets. Rather, it teaches those within the assignment. Note: Reworded into the technical vocabulary of complexity theory, Fortune's Theorem states that no sparse set is coNP-hard unless P=NP. Fortune's Theorem was a major advance in the understanding of the relationship between hardness and density.) We provide both the assignment handout (as the main body of this report plus Appendix A) and a solution to the assignment (as Appendix B, which would of course not be made available to the students until after they had handed in the assignment). The assignment handout, though the instructor can change this, is framed as having the students starting the assignment in teams in class for a whole class session, and then finishing it in those same teams as a take-home assignment, and handing it in before the next class session. We have found that student groups often succeed, partially or completely, in this challenge. This can mean a lot to the students: they see that they were able to make an advance that, when it was first obtained, appeared in what was arguably at the time the top journal venue for complexity theory research. This can give them confidence that they have substantial problem-solving skills (which basically means research skills) when they truly apply themselves to a given challenge.

Friday, August 14 2026, 00:00

PSPACE-Completeness of Multi-Agent Path Finding for Large Agents

Authors: Maichi Zhang, Naoyuki Kamiyama, Kanae Yoshiwatari

Multi-Agent Path Finding for Large Agents (LA-MAPF) is a geometric variant of MAPF in which agents are modeled as disks and conflicts are determined by physical overlap in the underlying Euclidean workspace. The goal of LA-MAPF is to decide whether there exists a sequence of conflict-free transitions from a start configuration to a goal configuration. Agafonov and Yakovlev proved that LA-MAPF is NP-hard. In this paper, we strengthen their result by proving that LA-MAPF is PSPACE-complete via a polynomial-time reduction from Restricted Sliding Tokens.

Authors: Maichi Zhang, Naoyuki Kamiyama, Kanae Yoshiwatari

Multi-Agent Path Finding for Large Agents (LA-MAPF) is a geometric variant of MAPF in which agents are modeled as disks and conflicts are determined by physical overlap in the underlying Euclidean workspace. The goal of LA-MAPF is to decide whether there exists a sequence of conflict-free transitions from a start configuration to a goal configuration. Agafonov and Yakovlev proved that LA-MAPF is NP-hard. In this paper, we strengthen their result by proving that LA-MAPF is PSPACE-complete via a polynomial-time reduction from Restricted Sliding Tokens.

Friday, August 14 2026, 00:00

On the Expressive Power of Transformers

Authors: Phokion Kolaitis, Rik Sengupta

Multi-layer transformers form the critical component of essentially all large language models (LLMs) in use today. Because of their ubiquity and computational capability, there is a rapidly growing body of work that aims to precisely calibrate the expressive power of transformers as language recognizers by comparing them against standard models of computation studied for decades by the theoretical computer science community. In this endeavor, circuit complexity has by and large emerged as the "correct" branch of computational complexity to analyze the expressive power of transformers; the reason is that parameterizing transformers by the various resources they use, such as attention and precision, leads to direct comparisons with different classes of circuits parameterized by resources such as type of gates, size, and depth. Here, we present an overview of selected results that delineate the expressive power of transformers using concepts and methods from circuit complexity.

Authors: Phokion Kolaitis, Rik Sengupta

Multi-layer transformers form the critical component of essentially all large language models (LLMs) in use today. Because of their ubiquity and computational capability, there is a rapidly growing body of work that aims to precisely calibrate the expressive power of transformers as language recognizers by comparing them against standard models of computation studied for decades by the theoretical computer science community. In this endeavor, circuit complexity has by and large emerged as the "correct" branch of computational complexity to analyze the expressive power of transformers; the reason is that parameterizing transformers by the various resources they use, such as attention and precision, leads to direct comparisons with different classes of circuits parameterized by resources such as type of gates, size, and depth. Here, we present an overview of selected results that delineate the expressive power of transformers using concepts and methods from circuit complexity.

Friday, August 14 2026, 00:00

Euclidean SVP is deterministically NP-hard to approximate within any constant factor

Authors: Daqing Wan

We prove that, for every constant $ρ>1$, the Euclidean shortest vector problem is NP-hard to approximate within any constant factor $ρ$ under a deterministic polynomial-time many-one reduction. This extends our previous deterministic NP-hardness result from $ρ<\sqrt 2$ to arbitrary constants and gives a deterministic version of Khot's randomized arbitrary-constant theorem. Our proof also gives deterministic counterparts of the two classical dimension-dependent regimes of Haviv and Regev: $2^{(\log n)^{1-\varepsilon}}$ under quasipolynomial-time reductions and $n^{c/\log\log n}$ under subexponential-time reductions.

Authors: Daqing Wan

We prove that, for every constant $ρ>1$, the Euclidean shortest vector problem is NP-hard to approximate within any constant factor $ρ$ under a deterministic polynomial-time many-one reduction. This extends our previous deterministic NP-hardness result from $ρ<\sqrt 2$ to arbitrary constants and gives a deterministic version of Khot's randomized arbitrary-constant theorem. Our proof also gives deterministic counterparts of the two classical dimension-dependent regimes of Haviv and Regev: $2^{(\log n)^{1-\varepsilon}}$ under quasipolynomial-time reductions and $n^{c/\log\log n}$ under subexponential-time reductions.

Friday, August 14 2026, 00:00

On the Exponential Circuit Imbalance of the Ben-Tal Nemirovski Approximation

Authors: Jonah Bondar, Stephen Vavasis

Dadush et al.\ (2024) recently developed a scaling-invariant layered least squares algorithm for linear programming whose complexity depends on the optimal condition measure $\barχ_A^*$. Their work builds on Vavasis and Ye's (1996) algorithm whose running time depends only on the constraint matrix $A$ through the condition number $\barχ_A$. The optimal condition measure $\barχ_A^*$ is defined as the minimum $\barχ_{AD}$ achievable over all positive diagonal column rescalings $D$. Dadush et al.\ (2024) also introduced the optimal circuit imbalance measure $κ_W^*$, which serves as a lower bound for $\barχ^*_A$. Instances with artificially large optimal circuit imbalance measures $κ_W^*$ can be easily constructed; however, finding naturally occurring examples where this optimal scaling-invariant measure grows exponentially is of independent interest. In this paper, we show that the Ben-Tal Nemirovski (BN) linear programming approximation of the unit disk provides such an example. By explicitly constructing circuits in the kernel of the BN formulation, we prove that the optimal circuit imbalance measure $κ_W^*$ grows exponentially in the number of approximation steps. Since $κ_W^*$ lower bounds $\barχ_A^*$, our result demonstrates that the BN approximation yields an exponentially ill-conditioned family of constraint matrices.

Authors: Jonah Bondar, Stephen Vavasis

Dadush et al.\ (2024) recently developed a scaling-invariant layered least squares algorithm for linear programming whose complexity depends on the optimal condition measure $\barχ_A^*$. Their work builds on Vavasis and Ye's (1996) algorithm whose running time depends only on the constraint matrix $A$ through the condition number $\barχ_A$. The optimal condition measure $\barχ_A^*$ is defined as the minimum $\barχ_{AD}$ achievable over all positive diagonal column rescalings $D$. Dadush et al.\ (2024) also introduced the optimal circuit imbalance measure $κ_W^*$, which serves as a lower bound for $\barχ^*_A$. Instances with artificially large optimal circuit imbalance measures $κ_W^*$ can be easily constructed; however, finding naturally occurring examples where this optimal scaling-invariant measure grows exponentially is of independent interest. In this paper, we show that the Ben-Tal Nemirovski (BN) linear programming approximation of the unit disk provides such an example. By explicitly constructing circuits in the kernel of the BN formulation, we prove that the optimal circuit imbalance measure $κ_W^*$ grows exponentially in the number of approximation steps. Since $κ_W^*$ lower bounds $\barχ_A^*$, our result demonstrates that the BN approximation yields an exponentially ill-conditioned family of constraint matrices.

Friday, August 14 2026, 00:00

New Quantitative Bounds for the $(p,q)$-Theorem for Unions of Convex Sets

Authors: Chaya Keller, Shakhar Smorodinsky

A set in $\mathbb{R}^d$ is $s$-convex if it is the union of at most $s$ convex sets. A family $F$ satisfies the $(p,q)$ property if among any $p$ sets in $F$, some $q$ intersect. Let $\mathrm{HD}_d^{(s)}(p,q)$ be the minimum number of points needed to pierce a finite family of $s$-convex sets that satisfies the $(p,q)$-property. Alon and Kalai (1995) proved that $\mathrm{HD}_d^{(s)}(p,q)$ exists for any $p \geq q \geq d+1$ and any $s \geq 1$, but the quantitative bounds they obtained are very loose. We present several improved upper and lower bounds, for a general $d$ and for $s$-intervals of the line (i.e., $\mathrm{HD}_1^{(s)}(p,q)$). In particular, we prove the following: (i) For every $d\ge2$, $s \geq 1$ and $δ>0$, if $p>q$ and $q\ge C_d\log(e sp)$, then $\mathrm{HD}_d^{(s)}(p,q) \le p-q+1 + O_{d,δ}((s \cdot \tfrac{p}{q} \cdot \log \tfrac{esp}{q})^{ρ_d+δ}),$ where $ρ_d2$. (iii) For any fixed $s$, there are an integer $κ_s\in\{s,\ldots,2s\}$ and constants $C_s,p_s>0$ such that, whenever $p\ge p_s$ and $q\ge C_s\log(ep)$, $ \mathrm{HD}_1^{(s)}(p,q)\in\{p-q+κ_s,\;p-q+κ_s+1\}. $ Interestingly, this two-value concentration result holds, although the exact value of the threshold remains unknown. (iv) For any $s \geq 1$, $\mathrm{HD}_3^{(s)}(p,4) \geq sp^{2-o(1)}$. Already for families of convex sets, this significantly improves the best known lower bound on $\mathrm{HD}_d^{(1)}(p,d+1)$, for all $d \geq 3$.

Authors: Chaya Keller, Shakhar Smorodinsky

A set in $\mathbb{R}^d$ is $s$-convex if it is the union of at most $s$ convex sets. A family $F$ satisfies the $(p,q)$ property if among any $p$ sets in $F$, some $q$ intersect. Let $\mathrm{HD}_d^{(s)}(p,q)$ be the minimum number of points needed to pierce a finite family of $s$-convex sets that satisfies the $(p,q)$-property. Alon and Kalai (1995) proved that $\mathrm{HD}_d^{(s)}(p,q)$ exists for any $p \geq q \geq d+1$ and any $s \geq 1$, but the quantitative bounds they obtained are very loose. We present several improved upper and lower bounds, for a general $d$ and for $s$-intervals of the line (i.e., $\mathrm{HD}_1^{(s)}(p,q)$). In particular, we prove the following: (i) For every $d\ge2$, $s \geq 1$ and $δ>0$, if $p>q$ and $q\ge C_d\log(e sp)$, then $\mathrm{HD}_d^{(s)}(p,q) \le p-q+1 + O_{d,δ}((s \cdot \tfrac{p}{q} \cdot \log \tfrac{esp}{q})^{ρ_d+δ}),$ where $ρ_d2$. (iii) For any fixed $s$, there are an integer $κ_s\in\{s,\ldots,2s\}$ and constants $C_s,p_s>0$ such that, whenever $p\ge p_s$ and $q\ge C_s\log(ep)$, $ \mathrm{HD}_1^{(s)}(p,q)\in\{p-q+κ_s,\;p-q+κ_s+1\}. $ Interestingly, this two-value concentration result holds, although the exact value of the threshold remains unknown. (iv) For any $s \geq 1$, $\mathrm{HD}_3^{(s)}(p,4) \geq sp^{2-o(1)}$. Already for families of convex sets, this significantly improves the best known lower bound on $\mathrm{HD}_d^{(1)}(p,d+1)$, for all $d \geq 3$.

Friday, August 14 2026, 00:00

Defensive Boosting for Online Probabilistic Forecasting

Authors: Georgy Noarov, Aaron Roth

We study online probabilistic forecasting of binary outcomes chosen by an adaptive adversary. Given an online learning algorithm for a weak hypothesis class $H$, we would like to efficiently obtain two incomparable guarantees that existing online boosting techniques provide separately. Online gradient boosting competes in Brier score with the best predictor induced by the span of $H$ on every sequence, but promises nothing when the span does not contain an accurate predictor. Online weak-to-strong boosting drives classification error to zero under a weak-learning condition, but promises little when that condition fails. We give a simple defensive forecasting algorithm, the Defensive Booster, that obtains both guarantees. On every adaptive sequence, its Brier score is competitive with the best prediction induced by the span of $H$ at the same rate as online gradient boosting; simultaneously, whenever the realized transcript satisfies the smooth weak-learning condition, its Brier score and randomized classification error satisfy the same rate guarantee as online classification boosting. This is achieved by operationalizing the "dual view" of boosting: When the algorithm's randomized classification error is persistently high, its mistake weights form a smooth reweighting on which every weak hypothesis has low edge, yielding an ex-post hard-core certificate that the weak-learning condition fails. We also develop a strongly adaptive variant, which satisfies both guarantees on every time interval. The Defensive Booster is very efficient: it accesses just one weak-class learner, whereas the prior online boosting methods we compare against maintain large weak-learner ensembles. Experiments on synthetic and real data streams demonstrate its strong predictive performance (sometimes substantially improving over all prior baselines) coupled with orders-of-magnitude faster runtime.

Authors: Georgy Noarov, Aaron Roth

We study online probabilistic forecasting of binary outcomes chosen by an adaptive adversary. Given an online learning algorithm for a weak hypothesis class $H$, we would like to efficiently obtain two incomparable guarantees that existing online boosting techniques provide separately. Online gradient boosting competes in Brier score with the best predictor induced by the span of $H$ on every sequence, but promises nothing when the span does not contain an accurate predictor. Online weak-to-strong boosting drives classification error to zero under a weak-learning condition, but promises little when that condition fails. We give a simple defensive forecasting algorithm, the Defensive Booster, that obtains both guarantees. On every adaptive sequence, its Brier score is competitive with the best prediction induced by the span of $H$ at the same rate as online gradient boosting; simultaneously, whenever the realized transcript satisfies the smooth weak-learning condition, its Brier score and randomized classification error satisfy the same rate guarantee as online classification boosting. This is achieved by operationalizing the "dual view" of boosting: When the algorithm's randomized classification error is persistently high, its mistake weights form a smooth reweighting on which every weak hypothesis has low edge, yielding an ex-post hard-core certificate that the weak-learning condition fails. We also develop a strongly adaptive variant, which satisfies both guarantees on every time interval. The Defensive Booster is very efficient: it accesses just one weak-class learner, whereas the prior online boosting methods we compare against maintain large weak-learner ensembles. Experiments on synthetic and real data streams demonstrate its strong predictive performance (sometimes substantially improving over all prior baselines) coupled with orders-of-magnitude faster runtime.

Friday, August 14 2026, 00:00

Three trees suffice for a constant stretch in minor-free graphs

Authors: Hung Le, Huy Pham, Cuong Than, Tuan Tran

In this short note, we show that $H$-minor-free graphs have a tree cover with $3$ trees and constant stretch for any fixed graph $H$. The number of trees matches the recent lower bound by Chen, Tan, and Xu who showed that a toroidal grid requires at least $3$ trees for constant stretch. Our result is obtained by establishing a connection between tree covers and Assouad--Nagata dimension and then invoking the recent dimension bound for minor-free metrics by Liu.

Authors: Hung Le, Huy Pham, Cuong Than, Tuan Tran

In this short note, we show that $H$-minor-free graphs have a tree cover with $3$ trees and constant stretch for any fixed graph $H$. The number of trees matches the recent lower bound by Chen, Tan, and Xu who showed that a toroidal grid requires at least $3$ trees for constant stretch. Our result is obtained by establishing a connection between tree covers and Assouad--Nagata dimension and then invoking the recent dimension bound for minor-free metrics by Liu.

Friday, August 14 2026, 00:00

Bagging Robustly Learns VC Classes with Linear Sample Complexity

Authors: Omar Montasser

We revisit the problem of learning predictors robust to adversarial examples at test-time. We prove that VC classes are adversarially robustly learnable with sample complexity linear in the VC dimension $d$, providing an exponential improvement over the previous upper bound of Montasser, Hanneke, and Srebro (2019). Remarkably, this result is achieved with a simple improper algorithm that combines the classic heuristic bagging (bootstrap aggregation) of Breiman (1996) with robust empirical risk minimization (RERM). Our algorithm computes RERMs on $O(d^\star)$ independent bootstrap samples and outputs their majority vote, where $d^\star$ denotes the dual VC dimension. We complement this result with a lower bound showing that this is unavoidable: in general, any learner in this oracle model requires $Ω(d^\star)$ calls to an RERM oracle, even when given arbitrarily many training examples.

Authors: Omar Montasser

We revisit the problem of learning predictors robust to adversarial examples at test-time. We prove that VC classes are adversarially robustly learnable with sample complexity linear in the VC dimension $d$, providing an exponential improvement over the previous upper bound of Montasser, Hanneke, and Srebro (2019). Remarkably, this result is achieved with a simple improper algorithm that combines the classic heuristic bagging (bootstrap aggregation) of Breiman (1996) with robust empirical risk minimization (RERM). Our algorithm computes RERMs on $O(d^\star)$ independent bootstrap samples and outputs their majority vote, where $d^\star$ denotes the dual VC dimension. We complement this result with a lower bound showing that this is unavoidable: in general, any learner in this oracle model requires $Ω(d^\star)$ calls to an RERM oracle, even when given arbitrarily many training examples.

Friday, August 14 2026, 00:00

Hit-and-Run Mixes as Fast as the Ball Walk

Authors: Ruizhe Zhang

Let $K\subset\mathbb{R}^n$ be an isotropic convex body. We prove that the hit-and-run walk, started from any $M$-warm distribution, reaches total-variation distance $\varepsilon$ from the uniform distribution on $K$ in $O\!\left(n^2ψ_n^{-2}\log^3(M/\varepsilon)\right)$ steps, where $ψ_n^{-1}$ is the Kannan-Lovász-Simonovits (KLS) constant. Up to logarithmic factors, this matches the best-known warm-start mixing time for the ball walk. Chen and Eldan [Discrete Comput. Geom. 2026] obtained the same $n^2ψ_n^{-2}$ dependence for hit-and-run, but with polynomial dependence on $M/\varepsilon$. Our result improves that polynomial dependence to a polylogarithmic one, fully resolving their open question about warm-start mixing of hit-and-run in isotropic convex bodies.

Authors: Ruizhe Zhang

Let $K\subset\mathbb{R}^n$ be an isotropic convex body. We prove that the hit-and-run walk, started from any $M$-warm distribution, reaches total-variation distance $\varepsilon$ from the uniform distribution on $K$ in $O\!\left(n^2ψ_n^{-2}\log^3(M/\varepsilon)\right)$ steps, where $ψ_n^{-1}$ is the Kannan-Lovász-Simonovits (KLS) constant. Up to logarithmic factors, this matches the best-known warm-start mixing time for the ball walk. Chen and Eldan [Discrete Comput. Geom. 2026] obtained the same $n^2ψ_n^{-2}$ dependence for hit-and-run, but with polynomial dependence on $M/\varepsilon$. Our result improves that polynomial dependence to a polylogarithmic one, fully resolving their open question about warm-start mixing of hit-and-run in isotropic convex bodies.

Friday, August 14 2026, 00:00

Compact Path Representation in DAGs via Colored Edge Pebbling

Authors: Paola Bonizzoni, Alessio Conte, Gianluca Della Vedova, Younan Gao, Roberto Grossi, Brian Riccardi

Compactly representing a variation graph is a core problem in computational pangenomics that is usually attacked with techniques that have been originated on texts and adapted to graphs. In this paper we propose a new framework that takes a topology-centric perspective instead. A variation graph is modeled as a directed acyclic graph (DAG) together with a set of distinguished paths, where each path is assigned a distinct color. Our compact representation is centered on pebbling the graph, i.e. placing colored pebbles on edges so that every predefined path can be univocally reconstructed from the pebbled edges. In particular, a saturated pebbling marks each chosen edge with every path (color) traversing it. We first propose a data structure to represent and query a variation graph with storage space depending on the size of the pebbling. The supported queries are: (i) path query, which recovers a path given its color, and (ii) edge query, which reports the colors of paths traversing a given edge. We then prove that the problem of finding a pebbling of minimum size is solvable in polynomial time. On the contrary, we prove that finding a saturated pebbling of minimum size is NP-hard, but can be reduced to the minimum-weight set cover problem, allowing us to leverage integer linear programming (ILP) solvers. We show how to exploit saturated pebblings to achieve faster queries times than minimum size pebbling. Our framework opens a new algorithmic viewpoint on developing more efficient variation graph representations rooted on the study of the topology of those graphs.

Authors: Paola Bonizzoni, Alessio Conte, Gianluca Della Vedova, Younan Gao, Roberto Grossi, Brian Riccardi

Compactly representing a variation graph is a core problem in computational pangenomics that is usually attacked with techniques that have been originated on texts and adapted to graphs. In this paper we propose a new framework that takes a topology-centric perspective instead. A variation graph is modeled as a directed acyclic graph (DAG) together with a set of distinguished paths, where each path is assigned a distinct color. Our compact representation is centered on pebbling the graph, i.e. placing colored pebbles on edges so that every predefined path can be univocally reconstructed from the pebbled edges. In particular, a saturated pebbling marks each chosen edge with every path (color) traversing it. We first propose a data structure to represent and query a variation graph with storage space depending on the size of the pebbling. The supported queries are: (i) path query, which recovers a path given its color, and (ii) edge query, which reports the colors of paths traversing a given edge. We then prove that the problem of finding a pebbling of minimum size is solvable in polynomial time. On the contrary, we prove that finding a saturated pebbling of minimum size is NP-hard, but can be reduced to the minimum-weight set cover problem, allowing us to leverage integer linear programming (ILP) solvers. We show how to exploit saturated pebblings to achieve faster queries times than minimum size pebbling. Our framework opens a new algorithmic viewpoint on developing more efficient variation graph representations rooted on the study of the topology of those graphs.

Friday, August 14 2026, 00:00

Solving Square-Submatrix Equation Systems

Authors: Lorenzo Carfagna, Giovanni Manzini

We consider systems of submatrix equations, that is, sets of equality constraints over square submatrices of the input. By generalising the recursive algorithm of Gawrychowski et al. [Universal reconstruction of a string, Theoretical Computer Science 2020] to two dimensions, we obtain a linear-time procedure that finds a solution for any such input system. As an immediate by-product, this yields an optimal-time algorithm for decompressing any two-dimensional macro scheme based on copy operations of sub-squares.

Authors: Lorenzo Carfagna, Giovanni Manzini

We consider systems of submatrix equations, that is, sets of equality constraints over square submatrices of the input. By generalising the recursive algorithm of Gawrychowski et al. [Universal reconstruction of a string, Theoretical Computer Science 2020] to two dimensions, we obtain a linear-time procedure that finds a solution for any such input system. As an immediate by-product, this yields an optimal-time algorithm for decompressing any two-dimensional macro scheme based on copy operations of sub-squares.

Friday, August 14 2026, 00:00

Triangle-Free Coloring in LOCAL via Resilient Lovász Local Lemma

Authors: Peter Davies-Peck, Xusheng Zhang

The Lovász Local Lemma (LLL) is a probabilistic tool that has been shown to be of central importance in the study of distributed algorithms. For example, the constructive LLL is known to be complete for the class of locally-checkable labeling problems with $o(\log n)$ randomized complexities in the LOCAL model. One classic application of the LLL is in coloring graphs with some sparse structure, such as triangle-free graphs. Triangle-free coloring therefore serves as a benchmark problem for techniques for sublogarithmic randomized distributed algorithms. The state-of-the-art distributed triangle-free coloring algorithm of Pettie and Su [ICALP 2013, Information and Computation 2015] uses $\fracΔ{k}$ colors (where $k$ can be up to $(\frac14 - \varepsilon)\ln Δ$) and consists of $O(k+\log^* n)$ applications of the distributed LLL. However, the distributed LLL is itself a difficult problem; despite significant study, the fastest algorithms known require $O(\log_Δn)$ or $O(\fracΔ{\logΔ})+\log^{O(1)}\log n$ rounds. In this work, we adapt the Pettie-Su's algorithm so that the resulting LLL instances can be solved in $\log^{O(1)}\log n$ rounds, by employing the 'resilience' definition of Davies [SODA 2023]. This gives an $O(k)+ \log^{O(1)}\log n$ complexity (since the LLL is not needed when $k= \log^{ω(1)}\log n$), essentially causing the LLL steps to no longer be the bottleneck of the algorithm. As a corollary we obtain the first $\log^{O(1)}\log n$-round algorithms for coloring triangle-free graphs with $o(Δ)$ colors. The same framework also yields a companion girth-$5$ algorithm, using $(1+\varepsilon)Δ/\ln Δ$ colors in $O(k)+ \log^{O(1)}\log n$ rounds, matching the best known existential upper bound for the number of colors.

Authors: Peter Davies-Peck, Xusheng Zhang

The Lovász Local Lemma (LLL) is a probabilistic tool that has been shown to be of central importance in the study of distributed algorithms. For example, the constructive LLL is known to be complete for the class of locally-checkable labeling problems with $o(\log n)$ randomized complexities in the LOCAL model. One classic application of the LLL is in coloring graphs with some sparse structure, such as triangle-free graphs. Triangle-free coloring therefore serves as a benchmark problem for techniques for sublogarithmic randomized distributed algorithms. The state-of-the-art distributed triangle-free coloring algorithm of Pettie and Su [ICALP 2013, Information and Computation 2015] uses $\fracΔ{k}$ colors (where $k$ can be up to $(\frac14 - \varepsilon)\ln Δ$) and consists of $O(k+\log^* n)$ applications of the distributed LLL. However, the distributed LLL is itself a difficult problem; despite significant study, the fastest algorithms known require $O(\log_Δn)$ or $O(\fracΔ{\logΔ})+\log^{O(1)}\log n$ rounds. In this work, we adapt the Pettie-Su's algorithm so that the resulting LLL instances can be solved in $\log^{O(1)}\log n$ rounds, by employing the 'resilience' definition of Davies [SODA 2023]. This gives an $O(k)+ \log^{O(1)}\log n$ complexity (since the LLL is not needed when $k= \log^{ω(1)}\log n$), essentially causing the LLL steps to no longer be the bottleneck of the algorithm. As a corollary we obtain the first $\log^{O(1)}\log n$-round algorithms for coloring triangle-free graphs with $o(Δ)$ colors. The same framework also yields a companion girth-$5$ algorithm, using $(1+\varepsilon)Δ/\ln Δ$ colors in $O(k)+ \log^{O(1)}\log n$ rounds, matching the best known existential upper bound for the number of colors.

Friday, August 14 2026, 00:00

A minimum witness for the 3/2 configuration-linear-program gap in two-weight graph balancing, unique at its size

Authors: Adam Y. Shavit

In restricted assignment - makespan minimization where each job has one size and a set of allowed machines - the configuration LP is the tightest studied relaxation, and its integrality gap is open in general. On two-weight graph balancing - each job allowed on at most two machines, sizes from two values - the value is known, both bounds due to Jansen, Land, and Maack (2016): their Table 1 instance attains 3/2, and their Corollary 11 bound of 2 - s/b for sizes s < b meets it at {1,2}. We ask how small such an instance - a witness - can be. We give I*, a six-job witness: the complete graph on four machines, unit jobs on a Hamiltonian cycle, weight-2 jobs on the complementary perfect matching, with integral optimum 3 against relaxation value 2. That is one job fewer than the smallest previously in print, and we prove it minimum and unique at its size. No instance of the class with at most five jobs reaches gap 3/2, on any number of machines; at six jobs, again on any number of machines, I* is the only witness, up to relabeling machines and adding machines no job can use. At seven jobs uniqueness fails: exactly thirteen witnesses, classified - the Jansen-Land-Maack instance among them - and at eight jobs exactly 154. Three machines never suffice, at any size: four are necessary for the gap. Results of this shape are in print for the same relaxation in one-dimensional cutting stock, where the extremal non-round-up instances have been enumerated and classified for small demand; the Discussion sets out the relation. Recognizing witnesses at relaxation value 2 - where all of ours live - is coNP-complete, so no min-max characterization exists unless NP = coNP. Every feasibility decision behind the exhaustive claims was made twice, in floating point and in exact rational arithmetic, with full agreement, and the pipeline must rediscover I* before its negatives are believed.

Authors: Adam Y. Shavit

In restricted assignment - makespan minimization where each job has one size and a set of allowed machines - the configuration LP is the tightest studied relaxation, and its integrality gap is open in general. On two-weight graph balancing - each job allowed on at most two machines, sizes from two values - the value is known, both bounds due to Jansen, Land, and Maack (2016): their Table 1 instance attains 3/2, and their Corollary 11 bound of 2 - s/b for sizes s < b meets it at {1,2}. We ask how small such an instance - a witness - can be. We give I*, a six-job witness: the complete graph on four machines, unit jobs on a Hamiltonian cycle, weight-2 jobs on the complementary perfect matching, with integral optimum 3 against relaxation value 2. That is one job fewer than the smallest previously in print, and we prove it minimum and unique at its size. No instance of the class with at most five jobs reaches gap 3/2, on any number of machines; at six jobs, again on any number of machines, I* is the only witness, up to relabeling machines and adding machines no job can use. At seven jobs uniqueness fails: exactly thirteen witnesses, classified - the Jansen-Land-Maack instance among them - and at eight jobs exactly 154. Three machines never suffice, at any size: four are necessary for the gap. Results of this shape are in print for the same relaxation in one-dimensional cutting stock, where the extremal non-round-up instances have been enumerated and classified for small demand; the Discussion sets out the relation. Recognizing witnesses at relaxation value 2 - where all of ours live - is coNP-complete, so no min-max characterization exists unless NP = coNP. Every feasibility decision behind the exhaustive claims was made twice, in floating point and in exact rational arithmetic, with full agreement, and the pipeline must rediscover I* before its negatives are believed.

Friday, August 14 2026, 00:00

$\tilde{O}(1)$-Depth Parallel Reachability Faster than Transitive Closure

Authors: Shimon Kogan, Merav Parter

A $d$-shortcut of a directed graph $G=(V,E)$ is a subset of edges drawn from the transitive closure $TC(G)$ whose addition reduces the graph diameter to at most $d$. In the special case $d=1$, computing a $1$-shortcut is \emph{equivalent} to computing the transitive closure. For larger values of $d$, a lower bound of [Hesse, SODA 2003] shows that $n^δ$-shortcuts, for small constants $δ>0$, may still contain a large fraction of the edges of $TC(G)$, suggesting that shortcut construction may remain as hard as transitive closure even in this regime. Consequently, since $\widetilde{O}(d)$-depth parallel reachability algorithms rely on computing $d$-shortcuts, achieving $\widetilde{O}(1)$ depth by this approach has so far required computing the full transitive closure. Assuming $ω=2$, the PS-AE-Triangle hypothesis of [Abboud, Bringmann, Fischer, and Künnemann, SODA 2024] yields a conditional $T^{4/3-o(1)}$ time barrier for computing transitive closure when $T\leq n^{3/2}$, where $T=|TC(G)|$. In this work, we bypass the transitive-closure barrier for $\widetilde{O}(1)$-depth parallel reachability. We introduce randomized $d$-shortcut constructions that already circumvent this barrier for $d=3$ and, more generally, for every even $d\geq4$ up to $O(\log n)$. Our approach yields a randomized $\widetilde{O}(1)$-depth parallel reachability algorithm with total work $\widetilde{O}(T^{ω/2})$, which becomes $\widetilde{O}(T)$ when $ω=2$, falling below this conditional $T^{4/3-o(1)}$ barrier throughout that regime. Under the current bound of $ω$, this gives $\widetilde{O}(T^{1.186})$ work, improving on the current $T^{1.3459+o(1)}$ sequential-time bound for transitive closure due to Abboud et al. Thus, although $\widetilde{O}(1)$-shortcuts might be almost as dense as the full transitive closure, they can nevertheless be computed substantially faster.

Authors: Shimon Kogan, Merav Parter

A $d$-shortcut of a directed graph $G=(V,E)$ is a subset of edges drawn from the transitive closure $TC(G)$ whose addition reduces the graph diameter to at most $d$. In the special case $d=1$, computing a $1$-shortcut is \emph{equivalent} to computing the transitive closure. For larger values of $d$, a lower bound of [Hesse, SODA 2003] shows that $n^δ$-shortcuts, for small constants $δ>0$, may still contain a large fraction of the edges of $TC(G)$, suggesting that shortcut construction may remain as hard as transitive closure even in this regime. Consequently, since $\widetilde{O}(d)$-depth parallel reachability algorithms rely on computing $d$-shortcuts, achieving $\widetilde{O}(1)$ depth by this approach has so far required computing the full transitive closure. Assuming $ω=2$, the PS-AE-Triangle hypothesis of [Abboud, Bringmann, Fischer, and Künnemann, SODA 2024] yields a conditional $T^{4/3-o(1)}$ time barrier for computing transitive closure when $T\leq n^{3/2}$, where $T=|TC(G)|$. In this work, we bypass the transitive-closure barrier for $\widetilde{O}(1)$-depth parallel reachability. We introduce randomized $d$-shortcut constructions that already circumvent this barrier for $d=3$ and, more generally, for every even $d\geq4$ up to $O(\log n)$. Our approach yields a randomized $\widetilde{O}(1)$-depth parallel reachability algorithm with total work $\widetilde{O}(T^{ω/2})$, which becomes $\widetilde{O}(T)$ when $ω=2$, falling below this conditional $T^{4/3-o(1)}$ barrier throughout that regime. Under the current bound of $ω$, this gives $\widetilde{O}(T^{1.186})$ work, improving on the current $T^{1.3459+o(1)}$ sequential-time bound for transitive closure due to Abboud et al. Thus, although $\widetilde{O}(1)$-shortcuts might be almost as dense as the full transitive closure, they can nevertheless be computed substantially faster.

Friday, August 14 2026, 00:00

Minimum eccentricity shortest paths of $K_{2,3}$-minor-free graphs

Authors: Dibyayan Chakraborty, Sandip Das, Sk Samim Islam, Ritam Manna Mitra, Saumya Sen

Given a simple, undirected, and unweighted graph $G$, and an integer $R$, the objective of the \textsc{Minimum Eccentricity Shortest Path (MESP)} is to decide whether there exists an \emph{isometric path} $P$ in $G$ such that the distance from every vertex in the graph to its nearest vertex in $P$ is at most $R$. In this paper, we prove that MESP admits an $O(n^4)$-time algorithm on $K_{2,3}$-minor-free graphs. Our algorithm has a cubic running time when the inputs are restricted to a cactus.

Authors: Dibyayan Chakraborty, Sandip Das, Sk Samim Islam, Ritam Manna Mitra, Saumya Sen

Given a simple, undirected, and unweighted graph $G$, and an integer $R$, the objective of the \textsc{Minimum Eccentricity Shortest Path (MESP)} is to decide whether there exists an \emph{isometric path} $P$ in $G$ such that the distance from every vertex in the graph to its nearest vertex in $P$ is at most $R$. In this paper, we prove that MESP admits an $O(n^4)$-time algorithm on $K_{2,3}$-minor-free graphs. Our algorithm has a cubic running time when the inputs are restricted to a cactus.

Friday, August 14 2026, 00:00

Unlocking Fractional Moments in Delphic Set Streams

Authors: Aranya Kumar Bal, Sourav Chakraborty, Arijit Ghosh, Rudrayan Kundu

We consider estimation of non-integer frequency moments $F_k$ and related Bernstein-type statistics in the Delphic set stream model under a bounded-frequency assumption: every universe element appears at most $τ$ times. The main challenge of this model is to keep space low while also keeping update time low, which is not trivial because the sets can be exponential in size compared to their representations. Our core insight is that by sampling the stream at different rates and observing the resulting distinct-counts, we can 'probe' the frequency distribution and numerically integrate these probes to reconstruct a broad class of statistics. Building on that, we crucially observe that the distinct-count of a randomly sampled substream, viewed as a function of the sampling rate, is a single analytic object whose evaluations determine a broad class of statistics via a complementary Laplace-type integral. Algorithmically we exploit this by: 1. estimating those evaluations using only standard $F_0$ (distinct-count) algorithms on sampled substreams and 2. recovering target statistics by controlled numerical integration on a judiciously chosen grid. For $F_k$ with $k\in (0,1)$ we obtain the first one-pass streaming algorithms for Delphic set streams whose space and per-set update time are $\mathrm{poly}(\log|Ω|,\log m,\varepsilon^{-1},\log(1/δ))$ in the practically relevant regime $τ=\mathrm{polylog}(|Ω|,m)$; in general the bounds are polynomial in $τ$ and $\varepsilon^{-1}$ and logarithmic in $δ^{-1}$. We also give a complexity-theoretic barrier explaining why lower bounds for removing the bounded-frequency assumption appear difficult: ruling out polylogarithmic algorithms for unrestricted Delphic $F_k$ would imply a linear-space threshold-counting separation.

Authors: Aranya Kumar Bal, Sourav Chakraborty, Arijit Ghosh, Rudrayan Kundu

We consider estimation of non-integer frequency moments $F_k$ and related Bernstein-type statistics in the Delphic set stream model under a bounded-frequency assumption: every universe element appears at most $τ$ times. The main challenge of this model is to keep space low while also keeping update time low, which is not trivial because the sets can be exponential in size compared to their representations. Our core insight is that by sampling the stream at different rates and observing the resulting distinct-counts, we can 'probe' the frequency distribution and numerically integrate these probes to reconstruct a broad class of statistics. Building on that, we crucially observe that the distinct-count of a randomly sampled substream, viewed as a function of the sampling rate, is a single analytic object whose evaluations determine a broad class of statistics via a complementary Laplace-type integral. Algorithmically we exploit this by: 1. estimating those evaluations using only standard $F_0$ (distinct-count) algorithms on sampled substreams and 2. recovering target statistics by controlled numerical integration on a judiciously chosen grid. For $F_k$ with $k\in (0,1)$ we obtain the first one-pass streaming algorithms for Delphic set streams whose space and per-set update time are $\mathrm{poly}(\log|Ω|,\log m,\varepsilon^{-1},\log(1/δ))$ in the practically relevant regime $τ=\mathrm{polylog}(|Ω|,m)$; in general the bounds are polynomial in $τ$ and $\varepsilon^{-1}$ and logarithmic in $δ^{-1}$. We also give a complexity-theoretic barrier explaining why lower bounds for removing the bounded-frequency assumption appear difficult: ruling out polylogarithmic algorithms for unrestricted Delphic $F_k$ would imply a linear-space threshold-counting separation.

Friday, August 14 2026, 00:00

From One Solution to Many: An Oracle-Based FPT Framework for Diverse Solutions under Generalized Diversity Measures

Authors: Pradeesha Ashok, Sobyasachi Chatterjee, Soumi Nandi, Saket Saurabh, Priyanshu Tiwari

The problem of computing \emph{diverse} solutions has recently emerged as an important area of study, motivated by applications in fairness, robustness, and security. Instead of returning a single feasible or optimal solution, the goal is to output a \emph{collection} of meaningfully different solutions, often measured by symmetric differences. Diverse variants have been studied using sparsification, network-flow reductions, and algebraic techniques. We investigate the fixed-parameter tractability of diverse variants of an implicit set-system problem. Given parameters $k$ and $r$ and a threshold $b$, the task is to compute $r$ feasible solutions, each of size at most $k$, whose diversity under a specified objective is at least $b$. Our main contribution is an oracle-based meta-theorem. We identify a broad class of objectives, called \emph{consistently diverse}, that includes several standard measures. Assuming an \emph{exact empty-extension oracle} given a forbidden set ${\sf Forb}$, which returns a feasible solution of a prescribed size avoiding ${\sf Forb}$ or reports that none exists, we obtain a fixed-parameter tractable algorithm parameterized by $k+r$. The algorithm makes at most $(2kr)^{kr} \cdot r$ oracle calls, and in each call the oracle parameter satisfies $s+|{\sf Forb}| \leq k+2kr$. Our framework unifies and strengthens previous oracle-based approaches. Compared with Kumabe's framework (ESA 2025), which gives a doubly exponential bound on the number of oracle calls, our approach achieves the single exponential bound $2^{O(kr\log(kr))}$ and directly constructs the desired tuple of solutions. We recover fixed-parameter tractable algorithms for all problems covered by that framework, with improved oracle complexity, and obtain strong bounds for diverse variants of classical graph and matroid problems.

Authors: Pradeesha Ashok, Sobyasachi Chatterjee, Soumi Nandi, Saket Saurabh, Priyanshu Tiwari

The problem of computing \emph{diverse} solutions has recently emerged as an important area of study, motivated by applications in fairness, robustness, and security. Instead of returning a single feasible or optimal solution, the goal is to output a \emph{collection} of meaningfully different solutions, often measured by symmetric differences. Diverse variants have been studied using sparsification, network-flow reductions, and algebraic techniques. We investigate the fixed-parameter tractability of diverse variants of an implicit set-system problem. Given parameters $k$ and $r$ and a threshold $b$, the task is to compute $r$ feasible solutions, each of size at most $k$, whose diversity under a specified objective is at least $b$. Our main contribution is an oracle-based meta-theorem. We identify a broad class of objectives, called \emph{consistently diverse}, that includes several standard measures. Assuming an \emph{exact empty-extension oracle} given a forbidden set ${\sf Forb}$, which returns a feasible solution of a prescribed size avoiding ${\sf Forb}$ or reports that none exists, we obtain a fixed-parameter tractable algorithm parameterized by $k+r$. The algorithm makes at most $(2kr)^{kr} \cdot r$ oracle calls, and in each call the oracle parameter satisfies $s+|{\sf Forb}| \leq k+2kr$. Our framework unifies and strengthens previous oracle-based approaches. Compared with Kumabe's framework (ESA 2025), which gives a doubly exponential bound on the number of oracle calls, our approach achieves the single exponential bound $2^{O(kr\log(kr))}$ and directly constructs the desired tuple of solutions. We recover fixed-parameter tractable algorithms for all problems covered by that framework, with improved oracle complexity, and obtain strong bounds for diverse variants of classical graph and matroid problems.

Friday, August 14 2026, 00:00

Efficient Randomized LL/SC that Preserves History Independence

Authors: Dante Bencivenga, Homa Habashi, Philipp Woelfel

We study the fundamental problem of implementing $m$ linearizable LL/SC objects with constant expected step complexity in a system of $n$ processes, using bounded base objects commonly available in hardware. Assuming that each process may have at most $τ$ outstanding LL operations, the best known deterministic algorithm requires $Ω(n^2τ+ m)$ base objects (CAS and registers) [Blelloch and Wei, DISC 2020]. Previously, no comparable randomized algorithm was known. By employing randomization and FADD in addition to CAS and registers, we obtain a space bound of $O(nτ+m)$ against the weak adaptive adversary. For $m=O(1)$ this matches a lower bound for algorithms using CAS and registers [Aghazadeh and Woelfel, PODC 2015]. In addition, our object can be employed by quiescently history-independent (QHI) algorithms: Whenever no operation on the object is pending and no process has an outstanding LL operation, its internal memory state is uniquely determined by the values of the $m$ LL/SC objects. An important application is a QHI dynamic hashing algorithm presented at STOC 2025, which uses $Θ(m)$ hardware LL/SC objects to maintain a hash table of size $m$ [Attiya, Bender, Farach-Colton, Oshman, and Schiller, STOC 2025]. But LL/SC is not available in hardware, and prior to our work no wait-free or efficiently lock-free software implementation of LL/SC with similar properties was known. Our work demonstrates that one can actually implement the hashing algorithm on available hardware, without an asymptotic increase in step and space complexity, under the reasonable assumption that $m=Ω(n)$.

Authors: Dante Bencivenga, Homa Habashi, Philipp Woelfel

We study the fundamental problem of implementing $m$ linearizable LL/SC objects with constant expected step complexity in a system of $n$ processes, using bounded base objects commonly available in hardware. Assuming that each process may have at most $τ$ outstanding LL operations, the best known deterministic algorithm requires $Ω(n^2τ+ m)$ base objects (CAS and registers) [Blelloch and Wei, DISC 2020]. Previously, no comparable randomized algorithm was known. By employing randomization and FADD in addition to CAS and registers, we obtain a space bound of $O(nτ+m)$ against the weak adaptive adversary. For $m=O(1)$ this matches a lower bound for algorithms using CAS and registers [Aghazadeh and Woelfel, PODC 2015]. In addition, our object can be employed by quiescently history-independent (QHI) algorithms: Whenever no operation on the object is pending and no process has an outstanding LL operation, its internal memory state is uniquely determined by the values of the $m$ LL/SC objects. An important application is a QHI dynamic hashing algorithm presented at STOC 2025, which uses $Θ(m)$ hardware LL/SC objects to maintain a hash table of size $m$ [Attiya, Bender, Farach-Colton, Oshman, and Schiller, STOC 2025]. But LL/SC is not available in hardware, and prior to our work no wait-free or efficiently lock-free software implementation of LL/SC with similar properties was known. Our work demonstrates that one can actually implement the hashing algorithm on available hardware, without an asymptotic increase in step and space complexity, under the reasonable assumption that $m=Ω(n)$.

Friday, August 14 2026, 00:00

The Cost of Changing Edges for Diameter Computation and More

Authors: Sam Hiken, Yael Kirkpatrick, Jakob Nogler, Virginia Vassilevska Williams

The sensitivity setting is a restricted setting for dynamic algorithms, particularly practical for scenarios where extensive preprocessing is feasible but responses to real-time modifications must be near-instantaneous before the data structure is eventually rebuilt. For graph problems, a sensitivity data structure is constructed with a preprocessing time P so that the following queries can be answered quickly, preferably in $O(1)$ time: given an edge $e$, return the answer to the problem on either $G \setminus e$ (decremental) or $G \cup e$ (incremental). In this paper, we almost entirely settle the decremental setting for the diameter and eccentricities problems in a variety of approximation regimes by matching P to the static runtime while supporting $O(1)$-time queries, thereby improving upon all previous results for a single failure [Bilò, Cohen, Friedrich, Schirneck, MFCS 2021; Bilò, Choudhary, Cohen, Friedrich, Krogmann, Schirneck, ICALP 2021]. More precisely: (1) We provide a tight reduction demonstrating that any exact distance sensitivity oracle can be used to efficiently solve decremental exact diameter and all-node eccentricities; (2) For the approximate setting, we match the runtime of all known static diameter algorithms across all sparsity settings, up to an additional $1+o(1)$ factor in approximation. Conversely, for the previously unexplored incremental setting of these problems: (3) We develop new lower bounds, demonstrating that no incremental algorithm can efficiently approximate diameter, radius, or eccentricity beyond a $5/3$ factor in undirected graphs or a $2$ factor in directed graphs; (4) We introduce two new instructive techniques and demonstrate how to utilize them to construct several new algorithms. Most notably, we develop incremental single-node eccentricity approximations for both directed and undirected graphs that match our new lower bounds.

Authors: Sam Hiken, Yael Kirkpatrick, Jakob Nogler, Virginia Vassilevska Williams

The sensitivity setting is a restricted setting for dynamic algorithms, particularly practical for scenarios where extensive preprocessing is feasible but responses to real-time modifications must be near-instantaneous before the data structure is eventually rebuilt. For graph problems, a sensitivity data structure is constructed with a preprocessing time P so that the following queries can be answered quickly, preferably in $O(1)$ time: given an edge $e$, return the answer to the problem on either $G \setminus e$ (decremental) or $G \cup e$ (incremental). In this paper, we almost entirely settle the decremental setting for the diameter and eccentricities problems in a variety of approximation regimes by matching P to the static runtime while supporting $O(1)$-time queries, thereby improving upon all previous results for a single failure [Bilò, Cohen, Friedrich, Schirneck, MFCS 2021; Bilò, Choudhary, Cohen, Friedrich, Krogmann, Schirneck, ICALP 2021]. More precisely: (1) We provide a tight reduction demonstrating that any exact distance sensitivity oracle can be used to efficiently solve decremental exact diameter and all-node eccentricities; (2) For the approximate setting, we match the runtime of all known static diameter algorithms across all sparsity settings, up to an additional $1+o(1)$ factor in approximation. Conversely, for the previously unexplored incremental setting of these problems: (3) We develop new lower bounds, demonstrating that no incremental algorithm can efficiently approximate diameter, radius, or eccentricity beyond a $5/3$ factor in undirected graphs or a $2$ factor in directed graphs; (4) We introduce two new instructive techniques and demonstrate how to utilize them to construct several new algorithms. Most notably, we develop incremental single-node eccentricity approximations for both directed and undirected graphs that match our new lower bounds.

Friday, August 14 2026, 00:00

Arithmetic Variable LogLog: Advancing the Memory-Variance Frontier

Authors: Brian Bushnell

Cardinality estimation - counting the number of distinct elements in a data stream - requires a tradeoff between memory and accuracy. ExaLogLog recently established the state of the art for this tradeoff by combining wide registers with a Fisher-information-optimal maximum likelihood (ML) estimator, achieving the best known memory-variance product (MVP) among HyperLogLog variants. Here we present Arithmetic Variable LogLog (AVLL), which surpasses ExaLogLog at every memory point tested using arithmetic encoding and eliminating uncommon states to consume 64-bit words completely with 11 registers each, yielding a 5.5x register-count advantage. Its four-component blended estimator, HLDLC, exploits this density advantage to surpass ExaLogLog's ML accuracy without iterative solving. At 1 KB, AVLL achieves 1.63% width-weighted mean absolute error compared to ExaLogLog's 1.71% - a 4.7% improvement. The corresponding empirical MVP is 3.4, surpassing ExaLogLog's practical MVP of 3.78 and its theoretical optimum of 3.67. This holds at every tested size from 0.25 to 4 KB. AVLL inherits DynamicLogLog's early exit mechanism, which filters most elements before any register is touched. With thousands of simultaneous sketches per thread, AVLL is 2.7-4.5x faster than ExaLogLog due to the reduced memory bandwidth from early exits. Like DynamicLogLog, AVLL stores relative NLZ values with a shared offset, so its memory scales as O(B + log log C) rather than O(B x log log C) - decoupling maximum representable cardinality from register width. These results hold under both high-complexity (all-unique) and low-complexity (nonuniformly high duplication rate) data distributions, with zero accuracy degradation from duplication. AVLL is implemented as a single self-contained Java class with all correction formulas embedded, available in the BBTools suite at bbmap.org.

Authors: Brian Bushnell

Cardinality estimation - counting the number of distinct elements in a data stream - requires a tradeoff between memory and accuracy. ExaLogLog recently established the state of the art for this tradeoff by combining wide registers with a Fisher-information-optimal maximum likelihood (ML) estimator, achieving the best known memory-variance product (MVP) among HyperLogLog variants. Here we present Arithmetic Variable LogLog (AVLL), which surpasses ExaLogLog at every memory point tested using arithmetic encoding and eliminating uncommon states to consume 64-bit words completely with 11 registers each, yielding a 5.5x register-count advantage. Its four-component blended estimator, HLDLC, exploits this density advantage to surpass ExaLogLog's ML accuracy without iterative solving. At 1 KB, AVLL achieves 1.63% width-weighted mean absolute error compared to ExaLogLog's 1.71% - a 4.7% improvement. The corresponding empirical MVP is 3.4, surpassing ExaLogLog's practical MVP of 3.78 and its theoretical optimum of 3.67. This holds at every tested size from 0.25 to 4 KB. AVLL inherits DynamicLogLog's early exit mechanism, which filters most elements before any register is touched. With thousands of simultaneous sketches per thread, AVLL is 2.7-4.5x faster than ExaLogLog due to the reduced memory bandwidth from early exits. Like DynamicLogLog, AVLL stores relative NLZ values with a shared offset, so its memory scales as O(B + log log C) rather than O(B x log log C) - decoupling maximum representable cardinality from register width. These results hold under both high-complexity (all-unique) and low-complexity (nonuniformly high duplication rate) data distributions, with zero accuracy degradation from duplication. AVLL is implemented as a single self-contained Java class with all correction formulas embedded, available in the BBTools suite at https://bbmap.org.

Friday, August 14 2026, 00:00

Fast Length-Squared Sampling for Positive-Semidefinite Matrices

Authors: Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco, Aaron Tian

We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an $n \times n$ positive-semidefinite (psd) matrix: that is, to sample a column with probability proportional to its squared $\ell_2$-norm. The algorithm runs in just $O(n)$ expected time, which is significantly sublinear in the input matrix size. The runtime is optimal, even when the input is assumed to be diagonal. Our result has several applications. Length-squared sampling is used by a number of sublinear time algorithms for matrix problems, like low-rank approximation and eigenvalue approximation. Often, it is assumed that the algorithm is given access to the matrix column norms, and thus can perform length-squared sampling efficiently. Our result shows that, at least for psd matrices, we can remove this assumption. We also discuss an application to an asymptotically optimal algorithm for estimating the Frobenius norm of a psd matrix to relative error. Finally, we show that our sampling algorithm yields a very simple sublinear time algorithm for the robust psd low-rank approximation problem introduced by Bakshi et al. (FOCS, 2020), which nearly matches the more complex method developed there.

Authors: Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco, Aaron Tian

We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an $n \times n$ positive-semidefinite (psd) matrix: that is, to sample a column with probability proportional to its squared $\ell_2$-norm. The algorithm runs in just $O(n)$ expected time, which is significantly sublinear in the input matrix size. The runtime is optimal, even when the input is assumed to be diagonal. Our result has several applications. Length-squared sampling is used by a number of sublinear time algorithms for matrix problems, like low-rank approximation and eigenvalue approximation. Often, it is assumed that the algorithm is given access to the matrix column norms, and thus can perform length-squared sampling efficiently. Our result shows that, at least for psd matrices, we can remove this assumption. We also discuss an application to an asymptotically optimal algorithm for estimating the Frobenius norm of a psd matrix to relative error. Finally, we show that our sampling algorithm yields a very simple sublinear time algorithm for the robust psd low-rank approximation problem introduced by Bakshi et al. (FOCS, 2020), which nearly matches the more complex method developed there.

Friday, August 14 2026, 00:00

Online balancing of vectors with small coordinates

Authors: Antonios Hmadi

Let $v_1,\ldots,v_T\in B_2^m$ be fixed in advance and revealed sequentially, and assume that $\|v_t\|_\infty\leqslant d^{-1/2}$ for some $d\geqslant 1$ and every $1\leqslant t\leqslant T$. There are absolute constants $L,C,c>0$ and a randomized online signing such that $$\mathbb{P}\left\{\max_{k\leqslant T}\left\|\sum_{t=1}^k\varepsilon_t v_t\right\|_\infty>6L\right\} \leqslant CT\exp\left(-\frac{cd}{\ln^2(ed)}\right).$$ Consequently, constant prefix discrepancy holds with probability at least $1-\varepsilon$ once $d$ is at least $C\ln\frac{3T}{\varepsilon}\left[\ln\left(e+\ln\frac{3T}{\varepsilon}\right)\right]^2$. In particular, every fixed sequence of vectors $a_t\in[-1,1]^m$ with at most $d$ nonzero coordinates admits an online signing with prefix discrepancy $O(\sqrt d)$ and failure probability at most $CT\exp[-cd/\ln^2(ed)]$. We also prove a nonuniform version in which the failure probability depends on the individual parameters $d_t=\|v_t\|_\infty^{-2}$, and a lower bound showing that a universal constant prefix discrepancy is impossible when $d=o(\ln T)$. We identify the corresponding $\ln^2 d$ barrier for the compact-potential method and extend the argument to general symmetric target bodies admitting a quadratic smoothness estimate.

Authors: Antonios Hmadi

Let $v_1,\ldots,v_T\in B_2^m$ be fixed in advance and revealed sequentially, and assume that $\|v_t\|_\infty\leqslant d^{-1/2}$ for some $d\geqslant 1$ and every $1\leqslant t\leqslant T$. There are absolute constants $L,C,c>0$ and a randomized online signing such that $$\mathbb{P}\left\{\max_{k\leqslant T}\left\|\sum_{t=1}^k\varepsilon_t v_t\right\|_\infty>6L\right\} \leqslant CT\exp\left(-\frac{cd}{\ln^2(ed)}\right).$$ Consequently, constant prefix discrepancy holds with probability at least $1-\varepsilon$ once $d$ is at least $C\ln\frac{3T}{\varepsilon}\left[\ln\left(e+\ln\frac{3T}{\varepsilon}\right)\right]^2$. In particular, every fixed sequence of vectors $a_t\in[-1,1]^m$ with at most $d$ nonzero coordinates admits an online signing with prefix discrepancy $O(\sqrt d)$ and failure probability at most $CT\exp[-cd/\ln^2(ed)]$. We also prove a nonuniform version in which the failure probability depends on the individual parameters $d_t=\|v_t\|_\infty^{-2}$, and a lower bound showing that a universal constant prefix discrepancy is impossible when $d=o(\ln T)$. We identify the corresponding $\ln^2 d$ barrier for the compact-potential method and extend the argument to general symmetric target bodies admitting a quadratic smoothness estimate.

Friday, August 14 2026, 00:00

Gianni Eugenio Viola, 1946-2026

from Emanuele Viola

Through a personal connection, my paternal grandfather was told to go on a plane to escape the start of World War II in Italy. He was told to go just like that, without bringing anything, and so he flew to Spain with his family: his wife and daughter. He was an academic himself and was […]

Through a personal connection, my paternal grandfather was told to go on a plane to escape the start of World War II in Italy. He was told to go just like that, without bringing anything, and so he flew to Spain with his family: his wife and daughter. He was an academic himself and was arranged to have a position in an Italian institute. And so my father was born in Madrid in 1946. After that, he lived in Paris, where he attended French school, Venice, and Athens, before finally moving to Rome. My grandfather died when my father was very young and was buried in the Lido cemetery in Venice. Unfortunately, his tomb is apparently no longer.

Traveling continued to be a main feature of my father’s life. He went to Soviet Russia. He rode a yak in Tibet. He went to India. He went to Syria before the start of the recent civil war. He went to Africa. He went to Iceland and countless other places. For a period, he did back-and-forth between New York and Rome, traveling, I think, at least once a month, where he was organizing various exhibitions. He was twice a fellow at the Getty foundation. During his lifetime, he was fluent in four languages: Italian, French, Greek, and English.

He was the humanities scholar par excellence, a living encyclopedia who could talk about anything and wrote about everything: from the Columbus expedition to a guide of Rome to avant-garde movements. Online, you can find a list of his more well-known publications, which give a sense of his breadth. He could enter a museum or a Church and talk about any painting, see any statue and tell you the story behind. I particularly remember his jokes, which always had a philosophical bent. He was also involved with exhibitions on fractals and modern logics, whose proceedings naturally piqued my interests more than others. I feel sorry that all this knowledge now must be gone forever. Here he is delivering one of his last lectures, just few months before passing away:

He was always with a book in his hands, always writing. Something which seems to have transmitted to me. At a later stage of my life, I’ve also become interested in history and started devouring books to tile the vast unknown with which I had emerged from school, at times following his suggestions.

Sadly, I really didn’t have a relationship with him, which I think was a major loss for me and perhaps also for him.

Here is us on the Dolomites in 2009. You’ll see how he’s stepping back to lower his height to match mine, a habit he had acquired.

Here he is in Boston with my wife, a few years earlier:

My father also loved good dining. Its one of the things he really did not compromise about. Here he is enjoying a meal by Lake Trasimeno with my mom, whom he was married to since 1970. They got married in the church of the artists, opened just for them thanks to a church friend. He insisted on having the ritual performed in Latin, just to give you a sense of the man.

He was about 2 m tall (6.5 ft) and weighed about 100 kg (200 lbs) and gave the impression of a mountain of energy. I always envied his ability to process lots of food and still function, as well as withstand extreme temperatures, all wearing a suit.

He continued to travel and enjoy fine dining, study and write until the end, despite mobility issues. In the end, he wasn’t in the best of health. Still, it seems he could have lived a little longer. Instead, he met a doctor who was the type of person I described earlier in this blog as a liable person. The doctor didn’t care about his condition, just noticed that it required hospitalization according to the protocol. They didn’t care if my father’s body could withstand that. It couldn’t, and unfortunately I was not there when he passed away.

However, I went to visit him in Rome just a few months before he did. I hadn’t been back in maybe 15 years. Here is us at our last encounter, with my sister.

Ciao Papi

By Manu

Thursday, August 13 2026, 18:01

Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning

Authors: Vaneet Aggarwal

We study nonnegative submodular maximization subject to a general matroid when the offline algorithm is given an arbitrary controlled value oracle. Our main result is an adversarial resilience theorem for the Spiteful Greedy Swap Poisson Process (SGS-Poisson): without modifying its Poisson intensity, single-element exchange rule, or spiteful drop step, the algorithm retains limiting approximation factors $1/e$ for non-monotone objectives and $1-1/e$ for monotone objectives. More precisely, under every controlled oracle $\widehat f$ satisfying $|\widehat f(S)-f(S)|\le ξ$ for every set $S$, our implementation returns a feasible set with expected value at least $(1/e-\varepsilon)\OPT-O(kξ)$ and $(1-1/e-\varepsilon)\OPT-O(kξ)$, respectively, using $\widetilde O(nk^2\varepsilon^{-2})$ oracle calls. As a consequence, the offline-to-online reduction yields full-bandit CMAB algorithms for general matroid-constrained submodular rewards with exact limiting approximation-regret factors $1/e$ and $1-1/e$ and $\widetilde O(n^{1/5}k^{4/5}T^{4/5})$ regret.

Authors: Vaneet Aggarwal

We study nonnegative submodular maximization subject to a general matroid when the offline algorithm is given an arbitrary controlled value oracle. Our main result is an adversarial resilience theorem for the Spiteful Greedy Swap Poisson Process (SGS-Poisson): without modifying its Poisson intensity, single-element exchange rule, or spiteful drop step, the algorithm retains limiting approximation factors $1/e$ for non-monotone objectives and $1-1/e$ for monotone objectives. More precisely, under every controlled oracle $\widehat f$ satisfying $|\widehat f(S)-f(S)|\le ξ$ for every set $S$, our implementation returns a feasible set with expected value at least $(1/e-\varepsilon)\OPT-O(kξ)$ and $(1-1/e-\varepsilon)\OPT-O(kξ)$, respectively, using $\widetilde O(nk^2\varepsilon^{-2})$ oracle calls. As a consequence, the offline-to-online reduction yields full-bandit CMAB algorithms for general matroid-constrained submodular rewards with exact limiting approximation-regret factors $1/e$ and $1-1/e$ and $\widetilde O(n^{1/5}k^{4/5}T^{4/5})$ regret.

Thursday, August 13 2026, 00:00

Evaluating QAOA expectation values can be as hard as counting optimal solutions

Authors: Stuart Hadfield

Evaluating expectation values is a critical task for variational quantum eigensolvers, and for parameterized quantum circuits and other quantum algorithms more generally. We consider the well-studied case of the Quantum Approximate Optimization Algorithm (QAOA) for the MaxCut problem. Recent work of Wang et al. [arXiv:2511.20212] showed this task to be NP-hard in general for any QAOA depth $p\geq 2$, complementing past results showing efficiently computable formulas for $p=1$ with arbitrary problem graphs. We sharpen this dichotomy showing that for $p\geq 2$ exact or exponentially precise cost expectation value evaluation is #P-hard under deterministic polynomial-time Turing reductions. Hardness at $p\geq 2$ is shown to remain even for evaluating single pairwise correlators $\langle Z\otimes Z\rangle $, as well as for highly restricted sets of algorithm parameters. Our proof refines the NP-hardness construction of Wang et al. that recovers the maximum cut value from the largest exponent of a QAOA Laurent polynomial, utilizing a distinct and simpler construction that extracts a value proportional to the total number of maximum cuts, in addition to the optimal cut value. Thus we show that the QAOA expectation value hardness transition from $p=1$ to $p=2$ is not only from tractability to optimization hardness, but to that of counting optimal solutions. As an application we show our results imply analogous hardness results for computing gradients and Hessians of QAOA circuits.

Authors: Stuart Hadfield

Evaluating expectation values is a critical task for variational quantum eigensolvers, and for parameterized quantum circuits and other quantum algorithms more generally. We consider the well-studied case of the Quantum Approximate Optimization Algorithm (QAOA) for the MaxCut problem. Recent work of Wang et al. [arXiv:2511.20212] showed this task to be NP-hard in general for any QAOA depth $p\geq 2$, complementing past results showing efficiently computable formulas for $p=1$ with arbitrary problem graphs. We sharpen this dichotomy showing that for $p\geq 2$ exact or exponentially precise cost expectation value evaluation is #P-hard under deterministic polynomial-time Turing reductions. Hardness at $p\geq 2$ is shown to remain even for evaluating single pairwise correlators $\langle Z\otimes Z\rangle $, as well as for highly restricted sets of algorithm parameters. Our proof refines the NP-hardness construction of Wang et al. that recovers the maximum cut value from the largest exponent of a QAOA Laurent polynomial, utilizing a distinct and simpler construction that extracts a value proportional to the total number of maximum cuts, in addition to the optimal cut value. Thus we show that the QAOA expectation value hardness transition from $p=1$ to $p=2$ is not only from tractability to optimization hardness, but to that of counting optimal solutions. As an application we show our results imply analogous hardness results for computing gradients and Hessians of QAOA circuits.

Thursday, August 13 2026, 00:00

RevCRN: Reversible Analog Computation using Chemical Reaction Networks

Authors: Saptarshi Biswas, James I. Lathrop, Rana D. Parshad

The computability of real numbers and functions using Turing Machines has been a central area of theoretical computer science since the mid-20th century. In the late 20th century, it was shown that chemical reactions can serve as a basis for computation using the Chemical Reaction Network (CRN) model. Recent advances in computing real numbers using Deterministic Chemical Reaction Networks (DCRNs) have identified numerous classes of DCRN-computable real numbers. In parallel, the works of R. Landauer and C. H. Bennett, spanning the 1960s to the early 2000s, showed that reversible computing offers significant advantages over irreversible methods, particularly in energy efficiency, motivating extensive research on reversible computation. In this work, we investigate the computability of real numbers using Reversible Chemical Reaction Networks (RevCRNs). The paper has two primary contributions: (1) establishing relationships among CRN-computable real number classes including Lyapunov CRN ($\mathbb{R}_{LCRN}$), Real-Time CRN ($\mathbb{R}_{RTCRN}$), rational numbers ($\mathbb{Q}$), and RevCRNs ($\mathbb{R}_{RevCRN}$), with key results: (i) $\mathbb{Q}$ is a strict subset of $\mathbb{R}_{RevCRN}$; (ii) the set of positive algebraic numbers ($ALG$), $\mathbb{R}_{LCRN}$, and real numbers computable by 1-species RevCRN ($\mathbb{R}_{RevCRN}^{1s}$) are equal; (iii) $\mathbb{R}_{RTCRN}$ and $\mathbb{R}_{RevCRN}$ exhibit non-empty overlap; and (iv) the set of real numbers computable by detailed-balanced RevCRNs ($\mathbb{R}^{DetBal}_{RevCRN}$) is a subset of $ALG$; and (2) exploring the existence of a hierarchy within $\mathbb{R}_{RevCRN}$. Finally, we leave open the exact relationship between $\mathbb{R}_{RevCRN}$ and $\mathbb{R}_{RTCRN}$ while conjecturing a general hierarchy of RevCRN-computable reals.

Authors: Saptarshi Biswas, James I. Lathrop, Rana D. Parshad

The computability of real numbers and functions using Turing Machines has been a central area of theoretical computer science since the mid-20th century. In the late 20th century, it was shown that chemical reactions can serve as a basis for computation using the Chemical Reaction Network (CRN) model. Recent advances in computing real numbers using Deterministic Chemical Reaction Networks (DCRNs) have identified numerous classes of DCRN-computable real numbers. In parallel, the works of R. Landauer and C. H. Bennett, spanning the 1960s to the early 2000s, showed that reversible computing offers significant advantages over irreversible methods, particularly in energy efficiency, motivating extensive research on reversible computation. In this work, we investigate the computability of real numbers using Reversible Chemical Reaction Networks (RevCRNs). The paper has two primary contributions: (1) establishing relationships among CRN-computable real number classes including Lyapunov CRN ($\mathbb{R}_{LCRN}$), Real-Time CRN ($\mathbb{R}_{RTCRN}$), rational numbers ($\mathbb{Q}$), and RevCRNs ($\mathbb{R}_{RevCRN}$), with key results: (i) $\mathbb{Q}$ is a strict subset of $\mathbb{R}_{RevCRN}$; (ii) the set of positive algebraic numbers ($ALG$), $\mathbb{R}_{LCRN}$, and real numbers computable by 1-species RevCRN ($\mathbb{R}_{RevCRN}^{1s}$) are equal; (iii) $\mathbb{R}_{RTCRN}$ and $\mathbb{R}_{RevCRN}$ exhibit non-empty overlap; and (iv) the set of real numbers computable by detailed-balanced RevCRNs ($\mathbb{R}^{DetBal}_{RevCRN}$) is a subset of $ALG$; and (2) exploring the existence of a hierarchy within $\mathbb{R}_{RevCRN}$. Finally, we leave open the exact relationship between $\mathbb{R}_{RevCRN}$ and $\mathbb{R}_{RTCRN}$ while conjecturing a general hierarchy of RevCRN-computable reals.

Thursday, August 13 2026, 00:00

An FKN Theorem for the Binary Grassmann Scheme

Authors: Yuval Filmus, Anqi Li, Dor Minzer

A classical theorem due to Friedgut, Kalai and Naor asserts that if a function $f\colon \{0,1\}^n\to\{-1,1\}$ close to a degree $1$ function, then either $f$ or $-f$ is close to either the all $1$ function, or to $(-1)^{x_i}$ for some $i\in [n]$. We prove a version of their theorem for the Grassmann scheme over $\mathbb{F}_2$. More precisely, we prove if a function $f\colon \genfrac{[}{]}{0pt}{}{\mathbb{F}_2^n}{\ell}\to\{0,1\}$ is close to a degree $1$ function, then either $f$ or $1-f$ must be close to a function of the form $g(L) = \sum_{x\in\mathcal{X}}1_{x\in L}+\sum_{W\in\mathcal{W}}1_{L\subseteq W}$, where $\mathcal{X}\subseteq\mathbb{F}_2^n$ is a set of points and $\mathcal{W}$ is a set of hyperplanes in $\mathbb{F}_2^n$.

Authors: Yuval Filmus, Anqi Li, Dor Minzer

A classical theorem due to Friedgut, Kalai and Naor asserts that if a function $f\colon \{0,1\}^n\to\{-1,1\}$ close to a degree $1$ function, then either $f$ or $-f$ is close to either the all $1$ function, or to $(-1)^{x_i}$ for some $i\in [n]$. We prove a version of their theorem for the Grassmann scheme over $\mathbb{F}_2$. More precisely, we prove if a function $f\colon \genfrac{[}{]}{0pt}{}{\mathbb{F}_2^n}{\ell}\to\{0,1\}$ is close to a degree $1$ function, then either $f$ or $1-f$ must be close to a function of the form $g(L) = \sum_{x\in\mathcal{X}}1_{x\in L}+\sum_{W\in\mathcal{W}}1_{L\subseteq W}$, where $\mathcal{X}\subseteq\mathbb{F}_2^n$ is a set of points and $\mathcal{W}$ is a set of hyperplanes in $\mathbb{F}_2^n$.

Thursday, August 13 2026, 00:00

Topology-Preserving Meshing of Implicit Scalar Fields via Monotonicity Constraints

Authors: Tanner Finken, Jixian Li, Bei Wang, Hanqi Guo, Joshua A. Levine

Topological analysis of scalar fields yields structures such as the Morse-Smale complex (MSC) that summarize salient features across multiple scales. Existing MSC extraction algorithms typically assume an explicit representation of the input field, such as a discretely sampled mesh. However, recent advances in visualization have popularized implicit field representations, for which these assumptions no longer hold. In this work, we address the problem of extracting an MSC from an implicitly defined 2D scalar field. We present a method for constructing a triangulated piecewise-linear (PL) mesh that aims to preserve the critical points of an underlying implicit scalar field. Our central insight is that if all edges are monotonic with respect to the underlying field, then the resulting PL approximation is topologically consistent with respect to critical points. Based on this insight, we introduce a refinement procedure that mitigates monotonicity violations. Requiring only pointwise evaluations and modest mesh refinement, the approach produces PL meshes that are correct with regards to critical points in our experiments. Finally, we demonstrate that additional targeted refinement improves the geometric fidelity of MSC separatrices.

Authors: Tanner Finken, Jixian Li, Bei Wang, Hanqi Guo, Joshua A. Levine

Topological analysis of scalar fields yields structures such as the Morse-Smale complex (MSC) that summarize salient features across multiple scales. Existing MSC extraction algorithms typically assume an explicit representation of the input field, such as a discretely sampled mesh. However, recent advances in visualization have popularized implicit field representations, for which these assumptions no longer hold. In this work, we address the problem of extracting an MSC from an implicitly defined 2D scalar field. We present a method for constructing a triangulated piecewise-linear (PL) mesh that aims to preserve the critical points of an underlying implicit scalar field. Our central insight is that if all edges are monotonic with respect to the underlying field, then the resulting PL approximation is topologically consistent with respect to critical points. Based on this insight, we introduce a refinement procedure that mitigates monotonicity violations. Requiring only pointwise evaluations and modest mesh refinement, the approach produces PL meshes that are correct with regards to critical points in our experiments. Finally, we demonstrate that additional targeted refinement improves the geometric fidelity of MSC separatrices.

Thursday, August 13 2026, 00:00

A Probabilistic Interpretation of the Ball Mapper Graph

Authors: John Rick Manzanares, Jay-Anne Bulauan

We introduce Probabilistic Ball Mapper, a formulation of Ball Mapper in which each data point is assigned a probability distribution supported only on the metric balls that contain it. This assignment defines both a partition subordinate to the Ball Mapper cover and a Markov kernel from the finite data space to the cover. We study two assignment schemes: a uniform-on-support rule and a localized radial-basis rule that incorporates distance to landmarks while preserving the underlying cover. Pushing the empirical data distribution through the kernel produces a probability distribution over vertices. Drawing twice, conditionally and independently, from each pointwise distribution produces a soft-overlap matrix. This matrix is symmetric, nonnegative, positive semidefinite, and has the vertex distribution as both marginals. It therefore provides a mass-normalized refinement of classical Ball Mapper overlap rather than another unnormalized edge count. For graphs constructed on a common cover, the vertex and overlap distributions can be compared directly. For independently fitted covers, we formulate Wasserstein and fused Gromov--Wasserstein-type discrepancies that account for vertex mass, landmark geometry when a common ambient metric is available, and intrinsic graph relations. For a fixed cover, we derive explicit perturbation bounds controlled by the sensitivity of the assignment rule, the magnitude of the data perturbation, and the data mass near cover boundaries. When the cover is recomputed, landmark motion creates an additional source of variation, for which we state a transport-based stability principle rather than an unconditional theorem. The resulting framework turns Ball Mapper into a probability-valued representation suitable for quantitative comparison while retaining its geometric interpretability and computational simplicity.

Authors: John Rick Manzanares, Jay-Anne Bulauan

We introduce Probabilistic Ball Mapper, a formulation of Ball Mapper in which each data point is assigned a probability distribution supported only on the metric balls that contain it. This assignment defines both a partition subordinate to the Ball Mapper cover and a Markov kernel from the finite data space to the cover. We study two assignment schemes: a uniform-on-support rule and a localized radial-basis rule that incorporates distance to landmarks while preserving the underlying cover. Pushing the empirical data distribution through the kernel produces a probability distribution over vertices. Drawing twice, conditionally and independently, from each pointwise distribution produces a soft-overlap matrix. This matrix is symmetric, nonnegative, positive semidefinite, and has the vertex distribution as both marginals. It therefore provides a mass-normalized refinement of classical Ball Mapper overlap rather than another unnormalized edge count. For graphs constructed on a common cover, the vertex and overlap distributions can be compared directly. For independently fitted covers, we formulate Wasserstein and fused Gromov--Wasserstein-type discrepancies that account for vertex mass, landmark geometry when a common ambient metric is available, and intrinsic graph relations. For a fixed cover, we derive explicit perturbation bounds controlled by the sensitivity of the assignment rule, the magnitude of the data perturbation, and the data mass near cover boundaries. When the cover is recomputed, landmark motion creates an additional source of variation, for which we state a transport-based stability principle rather than an unconditional theorem. The resulting framework turns Ball Mapper into a probability-valued representation suitable for quantitative comparison while retaining its geometric interpretability and computational simplicity.

Thursday, August 13 2026, 00:00

Going in Circles: Collaborative Multi-Robot Treasure Hunting

Authors: Bogumil Kaminski, Pawel Pralat, Maria Sadza

This paper investigates a multi-robot search-and-visit problem involving $n$ robots starting at the origin and $k$ unknown treasures hidden on the unit circle $\mathcal{C}$. The robots move independently anywhere in the plane with a maximum speed of 1 and instantly share discovery information. The goal is to determine an algorithm that minimizes the total time needed for all robots to individually visit every treasure. To establish the foundational limits of this task, we first solve an auxiliary optimal routing problem for a single robot on $\mathcal{C}$ that possesses complete prior knowledge of the treasure locations. The exact analysis of this auxiliary problem yields explicit upper and lower bounds for the original search problem.

Authors: Bogumil Kaminski, Pawel Pralat, Maria Sadza

This paper investigates a multi-robot search-and-visit problem involving $n$ robots starting at the origin and $k$ unknown treasures hidden on the unit circle $\mathcal{C}$. The robots move independently anywhere in the plane with a maximum speed of 1 and instantly share discovery information. The goal is to determine an algorithm that minimizes the total time needed for all robots to individually visit every treasure. To establish the foundational limits of this task, we first solve an auxiliary optimal routing problem for a single robot on $\mathcal{C}$ that possesses complete prior knowledge of the treasure locations. The exact analysis of this auxiliary problem yields explicit upper and lower bounds for the original search problem.

Thursday, August 13 2026, 00:00

Asymmetric Palette Sparsification, Slightly Simplified

Authors: Andrew McGregor

We present a slightly simplified analysis of the asymmetric palette sparsification result by Assadi and Yazdanyar [TheoretiCS, 2026]. The motivation is mainly pedagogical; our approach avoids hypergeometric concentration bounds and extra constant factors in the palette size.

Authors: Andrew McGregor

We present a slightly simplified analysis of the asymmetric palette sparsification result by Assadi and Yazdanyar [TheoretiCS, 2026]. The motivation is mainly pedagogical; our approach avoids hypergeometric concentration bounds and extra constant factors in the palette size.

Thursday, August 13 2026, 00:00

Faster Exponential Algorithms for Multi-Machine Scheduling Problems

Authors: Anubhav Dhar, Anita Dürr, Ahmed Ghazy, Jakob Greilhuber, Karol Węgrzycki

Minimizing the weighted completion times ($P \mid \mid Σw_j C_j$) and weighted number of tardy jobs ($P \mid \mid Σw_j U_j$) on multiple identical machines are two classical NP-hard scheduling problems. As shown by Lenté et al. (2014), both problems can be solved in time ${O}^{\star}(3^n)$. In this paper, we improve these bounds to ${O}(2.755^n)$ and ${O}^{\star}(2^n)$, respectively. Our algorithm for $P \mid \mid Σw_j C_j$ exploits the meet-in-the-middle paradigm and an efficient data structure answering linear programming queries. Additionally, when the number of machines is at most $6$, we show that the running time for $P \mid \mid Σw_j C_j$ can further be improved. Both scheduling problems are generalizations of the classical Bin Packing problem, which can be solved in ${O}^{\star}(2^n)$ time. Improving this running time is an important open question. We show that, when assuming the Asymptotic Rank Conjecture (ARC), Bin Packing can be solved in time ${O}((2-\varepsilon)^n)$ for some $\varepsilon >0$. Our algorithm makes use of two main ingredients: the recent ${O}((2-\varepsilon)^n)$-time algorithm of Nederlof et al. [SICOMP'23] for Bin Packing when the number of bins is a fixed constant, and the ${O}((2-\varepsilon)^n)$-time algorithm of Björklund et al. [SODA'25] for special instances of the $3$-way Partitioning problem when assuming ARC.

Authors: Anubhav Dhar, Anita Dürr, Ahmed Ghazy, Jakob Greilhuber, Karol Węgrzycki

Minimizing the weighted completion times ($P \mid \mid Σw_j C_j$) and weighted number of tardy jobs ($P \mid \mid Σw_j U_j$) on multiple identical machines are two classical NP-hard scheduling problems. As shown by Lenté et al. (2014), both problems can be solved in time ${O}^{\star}(3^n)$. In this paper, we improve these bounds to ${O}(2.755^n)$ and ${O}^{\star}(2^n)$, respectively. Our algorithm for $P \mid \mid Σw_j C_j$ exploits the meet-in-the-middle paradigm and an efficient data structure answering linear programming queries. Additionally, when the number of machines is at most $6$, we show that the running time for $P \mid \mid Σw_j C_j$ can further be improved. Both scheduling problems are generalizations of the classical Bin Packing problem, which can be solved in ${O}^{\star}(2^n)$ time. Improving this running time is an important open question. We show that, when assuming the Asymptotic Rank Conjecture (ARC), Bin Packing can be solved in time ${O}((2-\varepsilon)^n)$ for some $\varepsilon >0$. Our algorithm makes use of two main ingredients: the recent ${O}((2-\varepsilon)^n)$-time algorithm of Nederlof et al. [SICOMP'23] for Bin Packing when the number of bins is a fixed constant, and the ${O}((2-\varepsilon)^n)$-time algorithm of Björklund et al. [SODA'25] for special instances of the $3$-way Partitioning problem when assuming ARC.

Thursday, August 13 2026, 00:00

Harmonic Ranking for Edge-Weighted Oblivious Matching

Authors: Bo Peng, Zhihao Gavin Tang

We study edge-weighted oblivious bipartite matching. The weight of every potential edge is known, but its existence is revealed only when the edge is probed, and a successful probe between two free vertices must be accepted immediately. We give an explicit randomized algorithm with certified competitive ratio $0.698$, improving the previous best guarantee of $0.659$ (Huang, Sun, Wu, and Zhao, FOCS 2025). The result is computer-assisted and verified by a reproducible exact-integer computation. The same algorithm has a $0.698$-competitive online implementation for the vertex-weighted random-arrival model, improving the previous $0.696$ unweighted guarantee of Mahdian and Yan (STOC 2011) and the $0.686$ vertex-weighted guarantee of Peng and Tang (EC 2025). Our algorithm, Harmonic Ranking, is a role-symmetric generalization of \textsc{Ranking}. It assigns an independent random rank $x_z$ to each vertex and probes a potential edge $uv$ in decreasing order of \[ w_{uv}\frac{h(x_u)h(x_v)}{h(x_u)+h(x_v)}. \] This harmonic priority arises from a budget-balanced gain split and a mutual-proposal interpretation. The analysis lifts two cutoff curves into indicators, reducing the exponential-size factor-revealing problem to a polynomial-size directed minimum-cut instance. A maximum-flow computation with rounded-down integer capacities gives a rigorous certificate. Independently, we observe that the finite-grid unweighted relaxation of our factor-revealing program coincides exactly with a Mahdian--Yan program.

Authors: Bo Peng, Zhihao Gavin Tang

We study edge-weighted oblivious bipartite matching. The weight of every potential edge is known, but its existence is revealed only when the edge is probed, and a successful probe between two free vertices must be accepted immediately. We give an explicit randomized algorithm with certified competitive ratio $0.698$, improving the previous best guarantee of $0.659$ (Huang, Sun, Wu, and Zhao, FOCS 2025). The result is computer-assisted and verified by a reproducible exact-integer computation. The same algorithm has a $0.698$-competitive online implementation for the vertex-weighted random-arrival model, improving the previous $0.696$ unweighted guarantee of Mahdian and Yan (STOC 2011) and the $0.686$ vertex-weighted guarantee of Peng and Tang (EC 2025). Our algorithm, Harmonic Ranking, is a role-symmetric generalization of \textsc{Ranking}. It assigns an independent random rank $x_z$ to each vertex and probes a potential edge $uv$ in decreasing order of \[ w_{uv}\frac{h(x_u)h(x_v)}{h(x_u)+h(x_v)}. \] This harmonic priority arises from a budget-balanced gain split and a mutual-proposal interpretation. The analysis lifts two cutoff curves into indicators, reducing the exponential-size factor-revealing problem to a polynomial-size directed minimum-cut instance. A maximum-flow computation with rounded-down integer capacities gives a rigorous certificate. Independently, we observe that the finite-grid unweighted relaxation of our factor-revealing program coincides exactly with a Mahdian--Yan program.

Thursday, August 13 2026, 00:00

Strongly Polynomial Parallel Maximum Flow Revisited

Authors: Adam Karczmarz, Paweł Pilarski

We study the maximum flow problem in directed networks with real capacities in the parallel setting. For a network with $n$ vertices and $m$ arcs, we show that a randomized parallel implementation of a variant of the strongly polynomial max-flow algorithm of Dadush, Orlin, Sidford, and Végh [SODA 2026] runs in $\tilde{O}(mn)$ work and $\tilde{O}(m)$ depth. This improves upon the previously described tradeoffs between work and depth for strongly polynomial parallel maximum flow algorithms: earlier $\tilde{O}(n^3)$-work algorithms have $\tilde{O}(n^2)$ depth [Shiloach and Vishkin, J. Algorithms 1982; Goldberg and Tarjan, J. ACM 1988], while the known $\tilde{O}(m)$-depth approach uses $\tilde{O}(mn^3)$ work [Orlin, Oper. Res. 1993].

Authors: Adam Karczmarz, Paweł Pilarski

We study the maximum flow problem in directed networks with real capacities in the parallel setting. For a network with $n$ vertices and $m$ arcs, we show that a randomized parallel implementation of a variant of the strongly polynomial max-flow algorithm of Dadush, Orlin, Sidford, and Végh [SODA 2026] runs in $\tilde{O}(mn)$ work and $\tilde{O}(m)$ depth. This improves upon the previously described tradeoffs between work and depth for strongly polynomial parallel maximum flow algorithms: earlier $\tilde{O}(n^3)$-work algorithms have $\tilde{O}(n^2)$ depth [Shiloach and Vishkin, J. Algorithms 1982; Goldberg and Tarjan, J. ACM 1988], while the known $\tilde{O}(m)$-depth approach uses $\tilde{O}(mn^3)$ work [Orlin, Oper. Res. 1993].

Thursday, August 13 2026, 00:00

Parallel Machine Scheduling with a Singler Server and Loading-Unloading Operations

Authors: Keramat Hasani, Frank Werner

This paper investigates a parallel machine scheduling problem featuring a single common server responsible for both loading and unloading operations. Each job consists of a unit-time loading operation, non-preemptive processing on one of $m$ identical machines, and a unit-time unloading operation executed by the same server. The objective is to minimize the makespan. Unlike classical loading-only common-server models, our setting requires the server to handle an unloading operation immediately after a job's processing phase concludes. We prove that the corresponding decision problem is strongly NP-complete when the number of machines is given as part of the input. Furthermore, we analyse the worst-case performance of the List Scheduling (LS) and Longest Processing Time (LPT) heuristics. For three machines, we establish that Algorithm LS achieves an approximation ratio of at most $5/2$. For an arbitrary fixed $m \ge 3$, we show that the general LS bound approaches $4-3/m$ as the number of jobs grows, whereas for Algorithm LPT, we prove the finite-instance ratio $3-\frac{2}{m}+\frac{(m-1)(m-2)}{mn}.$ Thus, for each fixed $m$, the LPT bound approaches $3-2/m$ as the number of jobs grows.

Authors: Keramat Hasani, Frank Werner

This paper investigates a parallel machine scheduling problem featuring a single common server responsible for both loading and unloading operations. Each job consists of a unit-time loading operation, non-preemptive processing on one of $m$ identical machines, and a unit-time unloading operation executed by the same server. The objective is to minimize the makespan. Unlike classical loading-only common-server models, our setting requires the server to handle an unloading operation immediately after a job's processing phase concludes. We prove that the corresponding decision problem is strongly NP-complete when the number of machines is given as part of the input. Furthermore, we analyse the worst-case performance of the List Scheduling (LS) and Longest Processing Time (LPT) heuristics. For three machines, we establish that Algorithm LS achieves an approximation ratio of at most $5/2$. For an arbitrary fixed $m \ge 3$, we show that the general LS bound approaches $4-3/m$ as the number of jobs grows, whereas for Algorithm LPT, we prove the finite-instance ratio $3-\frac{2}{m}+\frac{(m-1)(m-2)}{mn}.$ Thus, for each fixed $m$, the LPT bound approaches $3-2/m$ as the number of jobs grows.

Thursday, August 13 2026, 00:00

Polynomial-Time Singular Witnesses for Non-SNS Sign Patterns

Authors: Tao Jiang, Minbo Gao, Shaowei Cai

Sign-nonsingularity asks whether every real matrix with prescribed entry signs is nonsingular. Polynomial-time algorithms recognize square sign-nonsingular patterns through their connection with even directed cycles, but recognition does not itself produce an exact numerical witness in the negative case. We give a deterministic polynomial-time algorithm that, for any square sign pattern $A$, either reports that $A$ is sign-nonsingular or outputs $B\in\mathbb{Z}^{n\times n}$ and $z\in\mathbb{Z}^n\setminus\{0\}$ such that $\operatorname{sgn}(B)=A$ and $Bz=0$. After normalizing a perfect matching, an even directed cycle yields two determinant terms of opposite signs. Making either term dominant produces endpoint realizations with opposite determinant signs. Changing their magnitudes one coordinate at a time exposes an affine sign-changing step, whose zero is rational; clearing its denominator gives the integer witness. Entries of $B$ have $O(n^2\log n)$ bits, and entries of $z$ have $O(n^3\log n)$ bits. The result settles Conjecture 14.12.4 in the Handbook of Satisfiability.

Authors: Tao Jiang, Minbo Gao, Shaowei Cai

Sign-nonsingularity asks whether every real matrix with prescribed entry signs is nonsingular. Polynomial-time algorithms recognize square sign-nonsingular patterns through their connection with even directed cycles, but recognition does not itself produce an exact numerical witness in the negative case. We give a deterministic polynomial-time algorithm that, for any square sign pattern $A$, either reports that $A$ is sign-nonsingular or outputs $B\in\mathbb{Z}^{n\times n}$ and $z\in\mathbb{Z}^n\setminus\{0\}$ such that $\operatorname{sgn}(B)=A$ and $Bz=0$. After normalizing a perfect matching, an even directed cycle yields two determinant terms of opposite signs. Making either term dominant produces endpoint realizations with opposite determinant signs. Changing their magnitudes one coordinate at a time exposes an affine sign-changing step, whose zero is rational; clearing its denominator gives the integer witness. Entries of $B$ have $O(n^2\log n)$ bits, and entries of $z$ have $O(n^3\log n)$ bits. The result settles Conjecture 14.12.4 in the Handbook of Satisfiability.

Thursday, August 13 2026, 00:00

A Tight Scale-Locality Bound for Partial Detection in Non-Adaptive Group Testing

Authors: Nader H. Bshouty

We give a lower bound for randomized non-adaptive group testing when the goal is to find any $\ell$ defective items but the total number $d$ of defectives is unknown. Bshouty and Haddad-Zaknoon proved an upper bound of $O(\ell\log^2 n)$ tests and a lower bound of $$Ω\!\left(\frac{\ell\log^2 n}{\log \ell+\log\log n}\right).$$ We prove the matching lower bound. More generally, we show that every randomized non-adaptive algorithm that succeeds with constant probability for every defective set must use $$Ω\!\left(\ell\log^2(n/\ell)\right)$$ tests. The proof is as follows. At a fixed value of $d$, finding $\ell$ defectives requires about $\ell\log(n/d)$ bits of information. On the other hand, one fixed group test is informative only when its size is tuned to the scale of $d$; across all logarithmic scales of $d$, a single test contributes only $O(1)$ bits. Summing over all scales gives the lower bound. We also record the matching upper bound $$O\!\left(\ell\log^2(n/\ell)\right),$$ obtained by running the known-$d$ algorithm in parallel over dyadic guesses for $d$. Thus the randomized non-adaptive complexity of unknown-$d$ partial detection is $Θ\!\left(\ell\log^2(n/\ell)\right)$ for constant success probability.

Authors: Nader H. Bshouty

We give a lower bound for randomized non-adaptive group testing when the goal is to find any $\ell$ defective items but the total number $d$ of defectives is unknown. Bshouty and Haddad-Zaknoon proved an upper bound of $O(\ell\log^2 n)$ tests and a lower bound of $$Ω\!\left(\frac{\ell\log^2 n}{\log \ell+\log\log n}\right).$$ We prove the matching lower bound. More generally, we show that every randomized non-adaptive algorithm that succeeds with constant probability for every defective set must use $$Ω\!\left(\ell\log^2(n/\ell)\right)$$ tests. The proof is as follows. At a fixed value of $d$, finding $\ell$ defectives requires about $\ell\log(n/d)$ bits of information. On the other hand, one fixed group test is informative only when its size is tuned to the scale of $d$; across all logarithmic scales of $d$, a single test contributes only $O(1)$ bits. Summing over all scales gives the lower bound. We also record the matching upper bound $$O\!\left(\ell\log^2(n/\ell)\right),$$ obtained by running the known-$d$ algorithm in parallel over dyadic guesses for $d$. Thus the randomized non-adaptive complexity of unknown-$d$ partial detection is $Θ\!\left(\ell\log^2(n/\ell)\right)$ for constant success probability.

Thursday, August 13 2026, 00:00

Distributed Quantum Algorithms Cannot Color Cycles with Probability 1

Authors: Xavier Coiteux-Roy, Maxime Flin, Carlos de Gois, Marc-Olivier Renou, Jukka Suomela, Isadora Veeren

We prove that any distributed quantum algorithm that finds a $3$-coloring with probability $1$ in a cycle of anonymous identical computers has to be global, that is, it needs $Ω(n)$ communication rounds. It follows that quantum computation and communication does not help with this problem. All prior lower bounds on quantum advantage in distributed graph algorithms use arguments related to physical causality. However, it is known that such arguments cannot rule out fast quantum advantage for $3$-coloring cycles. In particular, any causality-based argument would rule out the existence of finitely dependent coloring, but Holroyd and Liggett (2016) showed that such colorings do exist. Hence to tackle this problem, we need a ``genuinely quantum'' lower-bound technique that can distinguish between (1) distributions that do not violate physical causality vs. (2) distributions that can be realized with a quantum strategy. We present the first such lower-bound technique in this context. First, we show that $1$-round quantum algorithms cannot break symmetry with probability $1$. Second, we present a wishful teleportation strategy that can be used to turn $T$-round quantum 3-coloring algorithms into $1$-round quantum algorithms breaking symmetry, while preserving success probability $1$. Put together, the lower bound follows.

Authors: Xavier Coiteux-Roy, Maxime Flin, Carlos de Gois, Marc-Olivier Renou, Jukka Suomela, Isadora Veeren

We prove that any distributed quantum algorithm that finds a $3$-coloring with probability $1$ in a cycle of anonymous identical computers has to be global, that is, it needs $Ω(n)$ communication rounds. It follows that quantum computation and communication does not help with this problem. All prior lower bounds on quantum advantage in distributed graph algorithms use arguments related to physical causality. However, it is known that such arguments cannot rule out fast quantum advantage for $3$-coloring cycles. In particular, any causality-based argument would rule out the existence of finitely dependent coloring, but Holroyd and Liggett (2016) showed that such colorings do exist. Hence to tackle this problem, we need a ``genuinely quantum'' lower-bound technique that can distinguish between (1) distributions that do not violate physical causality vs. (2) distributions that can be realized with a quantum strategy. We present the first such lower-bound technique in this context. First, we show that $1$-round quantum algorithms cannot break symmetry with probability $1$. Second, we present a wishful teleportation strategy that can be used to turn $T$-round quantum 3-coloring algorithms into $1$-round quantum algorithms breaking symmetry, while preserving success probability $1$. Put together, the lower bound follows.

Thursday, August 13 2026, 00:00

Graphic Matroid Secretary without the Graph

Authors: Paul Dütting, Renato Paes Leme, Martin Pál, Neel Patel

The matroid secretary problem (MSP) is one of the cleanest, and most captivating open problems in online algorithms. The famous MSP conjecture stipulates that there exists a constant-competitive algorithm, yet to date the best known algorithms are $O(\log \log (\text{rank}))$ competitive. It is widely believed that all information that an algorithm for the MSP should use is information that is available through an independence oracle on the already arrived elements. Despite this, there are natural classes of matroids where a constant-competitive algorithm is known if we are given additional upfront information about the matroid; while no such algorithm is known if all the algorithm can use is an independence oracle on the arrived elements. In this work, we tackle the perhaps most appealing such class of matroids, graphic matroids. We develop an algorithm for the MSP that has access to the independence oracle only. Our algorithm runs in polynomial time, and if the underlying matroid is graphic, it produces an independent set whose weight is at least $1/36$ of the maximum-weight independent set. Ours is the first constant-competitive algorithm for MSP on unknown graphic matroids.

Authors: Paul Dütting, Renato Paes Leme, Martin Pál, Neel Patel

The matroid secretary problem (MSP) is one of the cleanest, and most captivating open problems in online algorithms. The famous MSP conjecture stipulates that there exists a constant-competitive algorithm, yet to date the best known algorithms are $O(\log \log (\text{rank}))$ competitive. It is widely believed that all information that an algorithm for the MSP should use is information that is available through an independence oracle on the already arrived elements. Despite this, there are natural classes of matroids where a constant-competitive algorithm is known if we are given additional upfront information about the matroid; while no such algorithm is known if all the algorithm can use is an independence oracle on the arrived elements. In this work, we tackle the perhaps most appealing such class of matroids, graphic matroids. We develop an algorithm for the MSP that has access to the independence oracle only. Our algorithm runs in polynomial time, and if the underlying matroid is graphic, it produces an independent set whose weight is at least $1/36$ of the maximum-weight independent set. Ours is the first constant-competitive algorithm for MSP on unknown graphic matroids.

Thursday, August 13 2026, 00:00

Distribution-Free Halfspace Testing with Samples

Authors: Xi Chen, Renato Ferreira Pinto, Nathaniel Harms, Shyamal Patel, Rocco A. Servedio

We prove a tight $Θ(n/ε)$ lower bound on the number of samples required for testing halfspaces over $\mathbb{R}^n$, in the distribution-free sample-based model where the underlying probability distribution is unknown to the algorithm, and the algorithm only receives random samples (i.e., it cannot make queries). This shows that testing is no more efficient than learning for halfspaces. We also show a matching upper bound for one-sided testers, improving on the standard (two-sided) testing-by-learning reduction, establishing that two-sided halfspace testers in this model have no advantage over one-sided testers.

Authors: Xi Chen, Renato Ferreira Pinto, Nathaniel Harms, Shyamal Patel, Rocco A. Servedio

We prove a tight $Θ(n/ε)$ lower bound on the number of samples required for testing halfspaces over $\mathbb{R}^n$, in the distribution-free sample-based model where the underlying probability distribution is unknown to the algorithm, and the algorithm only receives random samples (i.e., it cannot make queries). This shows that testing is no more efficient than learning for halfspaces. We also show a matching upper bound for one-sided testers, improving on the standard (two-sided) testing-by-learning reduction, establishing that two-sided halfspace testers in this model have no advantage over one-sided testers.

Thursday, August 13 2026, 00:00

PhD and Postdoctoral Positions at TUM – Fundamentals of Programming at TU München (apply by September 1, 2026 )

from CCI: jobs

TUM’s newly established Fundamentals of Programming Group invites applications for PhD and postdoctoral positions. Our research spans programming languages and type systems, program analysis and verification, logic and automata, and formal methods and AI, from foundational theory to algorithms and research tools. Review begins September 1, 2026, and continues until the positions are filled. Website: […]

TUM’s newly established Fundamentals of Programming Group invites applications for PhD and postdoctoral positions. Our research spans programming languages and type systems, program analysis and verification, logic and automata, and formal methods and AI, from foundational theory to algorithms and research tools. Review begins September 1, 2026, and continues until the positions are filled.

Website: https://www.cs.cit.tum.de/en/prog/open-positions/
Email: f.zuleger@tum.de

By shacharlovett

Wednesday, August 12 2026, 20:23

Unexpected Unemployment

from Computational Complexity

♦ Enjoying Idaho while ignoring Illinois
Today is the first day of my life that I am unemployed. And not by choice.
As I mentioned on LinkedIn last week, me and about 160 of my colleagues, staff and faculty, untenured and tenured, lost our positions at Illinois Tech after they declared "financial exigency" which allows them to eliminate tenured positions. I'll use this post to tell my story, but keep in mind there are 160 other ones.
The president announced that he would be asking the board to declare financial exigency in mid-July so we knew layoffs were coming but not when. On July 25th, we left for a planned 12-day vacation to Idaho. Why Idaho? It's my fiftieth state, so my wife and I decided to make a vacation of it. We saw Boise, canyons, craters, mountains, lakes. We were in Twin Falls three days before a mass shooting but that's a different story.
Usually I avoid reading work emails on vacation but decided I probably should this time. And on day four of vacation, I got an email invite to a meeting with the Vice-Provost of Faculty Affairs and an HR representative titled "Organizational Update" and I knew my fate was sealed. By the next day I was tired thinking about it and just decided to enjoy the rest of the vacation and deal with everything when I got back last Thursday. It might have been better if I simply didn't read email like usual.
It really hit me as I started to pack up my office Monday, for the first time with no office on the other side. Monday was also the first day of orientation week and a group of new students walked by as I was packing boxes into my car, though I don't think they noticed.
Illinois Tech got hit hard by a large drop in foreign graduate enrollment due to changing visa requirements, general anti-US sentiment, more opportunities in other countries and a weaker job market for graduating Masters students partly due to artificial intelligence. Universities face challenges beyond international students including Baumol's disease, administrative bloat to meet expanding regulations, the demographic cliff, reduced grant funding, and less support of universities by the public and both political parties, and AI changing how and why we teach. Illinois Tech is one of the first tech research schools to eliminate tenured roles, but it won't be the last.
I'll be okay but many of the other faculty could really use another position, in some cases so they can stay in the US. If you have opportunities for faculty in any discipline, let me know and I'll pass it along.

By Lance Fortnow

Enjoying Idaho while ignoring Illinois

Today is the first day of my life that I am unemployed. And not by choice.

As I mentioned on LinkedIn last week, me and about 160 of my colleagues, staff and faculty, untenured and tenured, lost our positions at Illinois Tech after they declared "financial exigency" which allows them to eliminate tenured positions. I'll use this post to tell my story, but keep in mind there are 160 other ones.

The president announced that he would be asking the board to declare financial exigency in mid-July so we knew layoffs were coming but not when. On July 25th, we left for a planned 12-day vacation to Idaho. Why Idaho? It's my fiftieth state, so my wife and I decided to make a vacation of it. We saw Boise, canyons, craters, mountains, lakes. We were in Twin Falls three days before a mass shooting but that's a different story.

Usually I avoid reading work emails on vacation but decided I probably should this time. And on day four of vacation, I got an email invite to a meeting with the Vice-Provost of Faculty Affairs and an HR representative titled "Organizational Update" and I knew my fate was sealed. By the next day I was tired thinking about it and just decided to enjoy the rest of the vacation and deal with everything when I got back last Thursday. It might have been better if I simply didn't read email like usual.

It really hit me as I started to pack up my office Monday, for the first time with no office on the other side. Monday was also the first day of orientation week and a group of new students walked by as I was packing boxes into my car, though I don't think they noticed.

Illinois Tech got hit hard by a large drop in foreign graduate enrollment due to changing visa requirements, general anti-US sentiment, more opportunities in other countries and a weaker job market for graduating Masters students partly due to artificial intelligence. Universities face challenges beyond international students including Baumol's disease, administrative bloat to meet expanding regulations, the demographic cliff, reduced grant funding, and less support of universities by the public and both political parties, and AI changing how and why we teach. Illinois Tech is one of the first tech research schools to eliminate tenured roles, but it won't be the last.

I'll be okay but many of the other faculty could really use another position, in some cases so they can stay in the US. If you have opportunities for faculty in any discipline, let me know and I'll pass it along.

By Lance Fortnow

Wednesday, August 12 2026, 13:32

How to Verify Consistency of Probabilistic Claims

Authors: Orr Paradise, Oliver Richardson, Yoshua Bengio, Shafi Goldwasser

When a probabilistic predictor answers many conditional-probability queries, are its answers self-consistent, and can this be verified in polynomial time? This problem is of interest for AI safety, where safety is derived from honesty about probabilistic predictions of unwanted outcomes potentially caused by an AI action. We construct an interactive PCP as follows. Let a predictive model be specified by a probability circuit P and a circuit Q which outputs confidence in predictions. Together, P and Q implicitly specify exponentially many probabilistic claims. We show a protocol in which a polynomial-time verifier can verify the approximate consistency of (P,Q). The verifier is given the pair of circuits (P,Q), which it evaluates at only a few points; alongside them it is given a proof oracle, an encoding of a witnessing probability distribution allegedly consistent with the predictions of (P,Q), which it reads at a few locations while interacting with a single untrusted prover. En route, we must ensure the existence of a sparse witnessing distribution consistent with the model's predictions. To do so, we first consider witness distributions for the consistency of explicit probabilistic claims, rather than claims specified by a predictor: say m claims, each of the form Pr[Y = 1 | X = x] = p, over n Boolean variables. Building on work initiated by Nilsson (Artif. Intell., 1986), we place l_2-approximate probabilistic consistency of explicit claims in NP, with certificates of length O(mn + log B) in the input bit-precision B; we further show how a small additive completeness-soundness gap removes the dependence on B. Together these results provide a complexity-theoretic foundation for certifying the self-consistency of probabilistic predictors. We view our interactive PCP as a first step toward training predictive models to prove their own consistency.

Authors: Orr Paradise, Oliver Richardson, Yoshua Bengio, Shafi Goldwasser

When a probabilistic predictor answers many conditional-probability queries, are its answers self-consistent, and can this be verified in polynomial time? This problem is of interest for AI safety, where safety is derived from honesty about probabilistic predictions of unwanted outcomes potentially caused by an AI action. We construct an interactive PCP as follows. Let a predictive model be specified by a probability circuit P and a circuit Q which outputs confidence in predictions. Together, P and Q implicitly specify exponentially many probabilistic claims. We show a protocol in which a polynomial-time verifier can verify the approximate consistency of (P,Q). The verifier is given the pair of circuits (P,Q), which it evaluates at only a few points; alongside them it is given a proof oracle, an encoding of a witnessing probability distribution allegedly consistent with the predictions of (P,Q), which it reads at a few locations while interacting with a single untrusted prover. En route, we must ensure the existence of a sparse witnessing distribution consistent with the model's predictions. To do so, we first consider witness distributions for the consistency of explicit probabilistic claims, rather than claims specified by a predictor: say m claims, each of the form Pr[Y = 1 | X = x] = p, over n Boolean variables. Building on work initiated by Nilsson (Artif. Intell., 1986), we place l_2-approximate probabilistic consistency of explicit claims in NP, with certificates of length O(mn + log B) in the input bit-precision B; we further show how a small additive completeness-soundness gap removes the dependence on B. Together these results provide a complexity-theoretic foundation for certifying the self-consistency of probabilistic predictors. We view our interactive PCP as a first step toward training predictive models to prove their own consistency.

Wednesday, August 12 2026, 00:00

Quantum Coordination Advantages in AI State-Tracking Tasks: Semantic Compilation and Latent Memory

Authors: Ming Yang

We prove inference-time quantum coordination advantages for specified AI state-tracking tasks. A solver compresses semantic history into a future-accessible boundary state and later answers a query. We count communication $B$, persistent instance-dependent memory $M$, and local work $D$; classical recurrence, caches, tools, and recomputation are allowed and charged. The central result is a boundary-preserving semantic-compilation theorem. It maps a finite one-way, streaming, or adaptive causal task into a semantic AI interface while preserving event order and access to past input. Classical boundary-state lower bounds and quantum-memory upper bounds transfer up to explicit compiler overhead, independently of the finite-precision recurrent architecture. Two applications have classical semantics. Matched-entity synopsis QA inherits the hidden-matching separation between $O(\log N)$ qubits and $Ω(\sqrt{N})$ classical boundary bits. Continual requirements auditing inherits a Max-$k$SAT streaming separation: a recurrent solver uses $O(\log^5 n\log(1/δ))$ qubits and polylogarithmic classical workspace to obtain a $0.7172$-approximation, whereas every classical one-pass finite-information solver attaining that ratio requires $Ω(\sqrt{n})$ coordination width. As a quantum-native compiler test, a stabilizer latent-state dialogue uses $n$ qubits, while every exact finite-state classical causal online realization satisfies $B+M \ge \frac{1}{2}n^2+(\frac{3}{2}-\log_2 3)n+O(1)$. The source protocols, streaming algorithms, and stabilizer witness are imported; the new result is their architecture-independent semantic transfer. These are memory and coordination separations, not runtime or empirical advantages for present-day language models. The stabilizer result assumes exact simulation and ideal noiseless quantum memory.

Authors: Ming Yang

We prove inference-time quantum coordination advantages for specified AI state-tracking tasks. A solver compresses semantic history into a future-accessible boundary state and later answers a query. We count communication $B$, persistent instance-dependent memory $M$, and local work $D$; classical recurrence, caches, tools, and recomputation are allowed and charged. The central result is a boundary-preserving semantic-compilation theorem. It maps a finite one-way, streaming, or adaptive causal task into a semantic AI interface while preserving event order and access to past input. Classical boundary-state lower bounds and quantum-memory upper bounds transfer up to explicit compiler overhead, independently of the finite-precision recurrent architecture. Two applications have classical semantics. Matched-entity synopsis QA inherits the hidden-matching separation between $O(\log N)$ qubits and $Ω(\sqrt{N})$ classical boundary bits. Continual requirements auditing inherits a Max-$k$SAT streaming separation: a recurrent solver uses $O(\log^5 n\log(1/δ))$ qubits and polylogarithmic classical workspace to obtain a $0.7172$-approximation, whereas every classical one-pass finite-information solver attaining that ratio requires $Ω(\sqrt{n})$ coordination width. As a quantum-native compiler test, a stabilizer latent-state dialogue uses $n$ qubits, while every exact finite-state classical causal online realization satisfies $B+M \ge \frac{1}{2}n^2+(\frac{3}{2}-\log_2 3)n+O(1)$. The source protocols, streaming algorithms, and stabilizer witness are imported; the new result is their architecture-independent semantic transfer. These are memory and coordination separations, not runtime or empirical advantages for present-day language models. The stabilizer result assumes exact simulation and ideal noiseless quantum memory.

Wednesday, August 12 2026, 00:00

Chronological Certificates for Shellsort: Ray Defects and Signed-Positive Transference

Authors: Ziqi Zhao, Qingjian Ni

Shellsort's best general lower and classical upper bounds differ by an iterated-logarithmic factor. Lower bounds use signed, order-free cancellation, whereas upper bounds require positive representations respecting pass order. We develop a common certificate framework for these two geometries. A prefix Fourier phase defect lower-bounds worst-case exchanges and hence comparisons. At pass $j$, the chronological ray quotient records multiples of the current gap already eliminated by earlier passes. Its truncated, pair-weighted hole mass bounds exchanges in that pass, and adding the $np$ overhead bounds comparisons. In a sufficiently long active window, $g_j^{(n)}$ ray holes imply signed transfer length at most $4g_j^{(n)}-1$, so approximate prefix characters propagate to the current gap. Signed transfer length two can coexist with arbitrarily large ray genus; scale-local Apéry representatives control both parameters. The framework recovers Pratt's $O(n\log^2 n)$ scale and the sparse two-parent scale, and yields the following structural results. Uniformly bounded full ray genus after a fixed prefix forces $W_n=Ω(n^{1+1/j_0-o(1)})$ when $p_n-j_0=o(\log n)$. An affine family has ordinary global semigroup genus and conductor $Θ(n)$ but relevant ray genus two. Balanced three-generator full grids have terminal truncated ray genus at least $\exp(Ω((\log n)^{2/3}))$. The last result is a certificate barrier.

Authors: Ziqi Zhao, Qingjian Ni

Shellsort's best general lower and classical upper bounds differ by an iterated-logarithmic factor. Lower bounds use signed, order-free cancellation, whereas upper bounds require positive representations respecting pass order. We develop a common certificate framework for these two geometries. A prefix Fourier phase defect lower-bounds worst-case exchanges and hence comparisons. At pass $j$, the chronological ray quotient records multiples of the current gap already eliminated by earlier passes. Its truncated, pair-weighted hole mass bounds exchanges in that pass, and adding the $np$ overhead bounds comparisons. In a sufficiently long active window, $g_j^{(n)}$ ray holes imply signed transfer length at most $4g_j^{(n)}-1$, so approximate prefix characters propagate to the current gap. Signed transfer length two can coexist with arbitrarily large ray genus; scale-local Apéry representatives control both parameters. The framework recovers Pratt's $O(n\log^2 n)$ scale and the sparse two-parent scale, and yields the following structural results. Uniformly bounded full ray genus after a fixed prefix forces $W_n=Ω(n^{1+1/j_0-o(1)})$ when $p_n-j_0=o(\log n)$. An affine family has ordinary global semigroup genus and conductor $Θ(n)$ but relevant ray genus two. Balanced three-generator full grids have terminal truncated ray genus at least $\exp(Ω((\log n)^{2/3}))$. The last result is a certificate barrier.

Wednesday, August 12 2026, 00:00

Polynomial Bounds on Degeneration Order from Commutativity Properties of Tensor Slices

Authors: Shree Ganesh, Pascal Koiran, Rafael Oliveira

A tensor has border rank at most $r$ if it can be written as $T=\lim_{\varepsilon \rightarrow 0} T(\varepsilon)$ where $T(\varepsilon)$ has rank at most $r$ for all sufficiently small $\varepsilon$. It is known that the map $\varepsilon \mapsto T(\varepsilon)$ can be assumed to be a (tensor valued) polynomial in $\varepsilon$. The smallest possible degree of such a map is called the error degree of $T$. The error degree and the related notion of order of degeneration are the two key quantities that we study in this paper. One motivation comes from debordering: by polynomial interpolation on the map $\varepsilon \mapsto T(\varepsilon)$ we can upper bound the tensor rank of $T$. For order 3 tensors, exponential upper bounds on the error degree and degeneration order were given almost 40 years ago in (Lehmkuhl Lickteig, 1989) and were not improved ever since. In this paper we give bounds that apply to a wide class of tensors, exponentially improving on (Lehmkuhl Lickteig, 1989). Our results are most general for tensors with 3 slices (format $m \times n \times 3$). In this case, our main assumption is on the rank of the matrix slices. We also give bounds that apply to arbitrary rectangular formats ($m \times n \times p$). In this case, we need an additional 1-regularity assumption on one of the slices of the tensor (recall that a matrix is said to be 1-regular if its eigenspaces are 1-dimensional). Under these assumptions we show that the error degree is at most 1, which yields a nontrivial debordering result (tensor rank at most $2r$ for border rank $r$). The results in (Lehmkuhl Lickteig, 1989) rely on an upper bound on the degree of the variety of tensors of border rank at most $r$. We rely instead on more specific properties of this algebraic variety, and in particular on commutativity properties of certain matrices derived from the tensor slices.

Authors: Shree Ganesh, Pascal Koiran, Rafael Oliveira

A tensor has border rank at most $r$ if it can be written as $T=\lim_{\varepsilon \rightarrow 0} T(\varepsilon)$ where $T(\varepsilon)$ has rank at most $r$ for all sufficiently small $\varepsilon$. It is known that the map $\varepsilon \mapsto T(\varepsilon)$ can be assumed to be a (tensor valued) polynomial in $\varepsilon$. The smallest possible degree of such a map is called the error degree of $T$. The error degree and the related notion of order of degeneration are the two key quantities that we study in this paper. One motivation comes from debordering: by polynomial interpolation on the map $\varepsilon \mapsto T(\varepsilon)$ we can upper bound the tensor rank of $T$. For order 3 tensors, exponential upper bounds on the error degree and degeneration order were given almost 40 years ago in (Lehmkuhl Lickteig, 1989) and were not improved ever since. In this paper we give bounds that apply to a wide class of tensors, exponentially improving on (Lehmkuhl Lickteig, 1989). Our results are most general for tensors with 3 slices (format $m \times n \times 3$). In this case, our main assumption is on the rank of the matrix slices. We also give bounds that apply to arbitrary rectangular formats ($m \times n \times p$). In this case, we need an additional 1-regularity assumption on one of the slices of the tensor (recall that a matrix is said to be 1-regular if its eigenspaces are 1-dimensional). Under these assumptions we show that the error degree is at most 1, which yields a nontrivial debordering result (tensor rank at most $2r$ for border rank $r$). The results in (Lehmkuhl Lickteig, 1989) rely on an upper bound on the degree of the variety of tensors of border rank at most $r$. We rely instead on more specific properties of this algebraic variety, and in particular on commutativity properties of certain matrices derived from the tensor slices.

Wednesday, August 12 2026, 00:00

Gromov-Wasserstein Quantization and Clustering: Structure, Rates, and Algorithms