Theory of Computing Report

Authors: Marius Drop, Benjamin G. Rin, Finn van der Velde

Quoridor is an award-winning abstract strategy game designed by Mirko Marchesi and published in 1997. Similar games include Maze Attack, Blockade (also known as Cul-de-sac), and Pinko Pallino. In line with chess, checkers, Go, and other classic combinatorial games, Quoridor is a turn-based, deterministic, perfect-information game played on a square grid. We show that it is PSPACE-complete to determine whether a given player has a winning strategy in a given Quoridor position on a board with size $n \times n$. We prove this by reduction from Gpos(POS CNF), a Boolean formula game originally defined in 1978 by T. Schaefer.

Authors: Marius Drop, Benjamin G. Rin, Finn van der Velde

Quoridor is an award-winning abstract strategy game designed by Mirko Marchesi and published in 1997. Similar games include Maze Attack, Blockade (also known as Cul-de-sac), and Pinko Pallino. In line with chess, checkers, Go, and other classic combinatorial games, Quoridor is a turn-based, deterministic, perfect-information game played on a square grid. We show that it is PSPACE-complete to determine whether a given player has a winning strategy in a given Quoridor position on a board with size $n \times n$. We prove this by reduction from Gpos(POS CNF), a Boolean formula game originally defined in 1978 by T. Schaefer.

Friday, May 22 2026, 00:00

A Simple Sub-Polynomial Degree Coboundary Expander

Authors: Max Hopkins, Arka Ray

High dimensional expanders simultaneously satisfying spectral and combinatorial (coboundary) expansion have recently played a major role in breakthroughs in PCP and coding theory, but the only known construction of such complexes is extremely involved, requiring deep algebraic number theory. In this work, we give an extremely simple combinatorial construction of a sub-polynomial degree complex based on projections of the flags complex (subspace chains) that is (i) a local spectral expander, (ii) a coboundary expander, and (iii) a swap coboundary expander. As a corollary, we also give the first near-linear size combinatorial hypergraphs with good agreement tests in the '1%' regime, and a simple PCP construction with near-linear size.

Authors: Max Hopkins, Arka Ray

High dimensional expanders simultaneously satisfying spectral and combinatorial (coboundary) expansion have recently played a major role in breakthroughs in PCP and coding theory, but the only known construction of such complexes is extremely involved, requiring deep algebraic number theory. In this work, we give an extremely simple combinatorial construction of a sub-polynomial degree complex based on projections of the flags complex (subspace chains) that is (i) a local spectral expander, (ii) a coboundary expander, and (iii) a swap coboundary expander. As a corollary, we also give the first near-linear size combinatorial hypergraphs with good agreement tests in the '1%' regime, and a simple PCP construction with near-linear size.

Friday, May 22 2026, 00:00

Maximum-Weight Two Boxes Symmetric Difference Problem

Authors: José Fernández Goycoolea, Luis H. Herrera, Pablo Pérez Lantero, Carlos Seara

Let $P$ be a set of $n$ points in the plane, where each element of $P$ is assigned a weight $ω(p)$, positive or negative. In this paper, we present an algorithm that runs in $O(n^4\log n)$ time and $O(n)$ space to find two possibly overlapping axis-aligned rectangles $A$ and $B$ so as to maximize the total weight of the points contained in the symmetric difference of $A$ and $B$. The same optimization framework can easily be adapted to solve related problems such as to maximize the total weight in the symmetric difference of $k \geq 3$ boxes and/or in the union of $k \geq 2$ boxes.

Authors: José Fernández Goycoolea, Luis H. Herrera, Pablo Pérez Lantero, Carlos Seara

Let $P$ be a set of $n$ points in the plane, where each element of $P$ is assigned a weight $ω(p)$, positive or negative. In this paper, we present an algorithm that runs in $O(n^4\log n)$ time and $O(n)$ space to find two possibly overlapping axis-aligned rectangles $A$ and $B$ so as to maximize the total weight of the points contained in the symmetric difference of $A$ and $B$. The same optimization framework can easily be adapted to solve related problems such as to maximize the total weight in the symmetric difference of $k \geq 3$ boxes and/or in the union of $k \geq 2$ boxes.

Friday, May 22 2026, 00:00

A geometric modelling framework to support the design of heterogeneous lattice structures with non-linearly varying geometry

Authors: Nikita Letov, Yaoyao Fiona Zhao

Geometric modelling has been a crucial component of the design process ever since the introduction of the first Computer-Aided Design (CAD) systems. Additive Manufacturing (AM) pushes design freedom to previously unachievable limits. AM allows the manufacturing of lattice structures which are otherwise close to impossible to be manufactured conventionally. Yet, the geometric modelling of heterogeneous lattice structures is still greatly limited. Thus, the AM industry is now in a situation where the manufacturing capabilities exceed the geometric modelling capabilities. While there have been advancements in the modelling of heterogeneous lattice structures, the review of relevant literature revealed critical limitations of the existing approaches. These limitations include their inability to model non-linear variation of geometric parameters, as well as the limited amount of controllable geometric parameters. This work presents a novel geometric modelling methodology based on function representation as an attempt to bridge this gap. The proposed approach avoids the manual definition of geometric parameters and provides a method to control them with mathematical functions instead. A software prototype implementing the proposed approach is presented, and several use-cases are analysed.

Authors: Nikita Letov, Yaoyao Fiona Zhao

Geometric modelling has been a crucial component of the design process ever since the introduction of the first Computer-Aided Design (CAD) systems. Additive Manufacturing (AM) pushes design freedom to previously unachievable limits. AM allows the manufacturing of lattice structures which are otherwise close to impossible to be manufactured conventionally. Yet, the geometric modelling of heterogeneous lattice structures is still greatly limited. Thus, the AM industry is now in a situation where the manufacturing capabilities exceed the geometric modelling capabilities. While there have been advancements in the modelling of heterogeneous lattice structures, the review of relevant literature revealed critical limitations of the existing approaches. These limitations include their inability to model non-linear variation of geometric parameters, as well as the limited amount of controllable geometric parameters. This work presents a novel geometric modelling methodology based on function representation as an attempt to bridge this gap. The proposed approach avoids the manual definition of geometric parameters and provides a method to control them with mathematical functions instead. A software prototype implementing the proposed approach is presented, and several use-cases are analysed.

Friday, May 22 2026, 00:00

Exact Uniform L1 Spacing for Solow-Polasky Diversity on Lines and Ordered Pareto Fronts

Authors: Michael T. M. Emmerich, Mahboubeh Nezhadmoghaddam, Jesús Guillermo Falcón Cardona

We study fixed-cardinality maximization of the inverse-matrix Solow--Polasky diversity, equivalently finite metric magnitude for the exponential kernel, on one-dimensional and ordered metric sets. The analysis starts from the known finite-line gap formula for the exponential kernel, which writes the excess inverse-matrix diversity as a sum of functions of consecutive gaps. Building on this formula, the main interval theorem proves that, for every $k\geq 2$, the unique maximizing $k$-point subset of $[0,1]$ is the equally spaced set. Thus the objective selects a uniform gap representation on the real line. A converse kernel proposition shows that, among normalized non-increasing distance kernels, requiring the corresponding adjacent-gap additive structure forces the exponential family. Further results transfer the interval theorem to ordered $\ell_1$ (L1, or Manhattan) curves by isometry: the maximizing sets are uniform in accumulated $\ell_1$ length. As a consequence, monotone biobjective Pareto fronts admit Solow--Polasky optimal finite approximations that are uniformly spaced in accumulated objective-space change, a natural representation when all parts of a continuous front should be covered. Examples, including a dense connected front and a finite disconnected ZDT3 front, illustrate how the continuous uniform-gap result appears on discrete candidate sets. Solow-Polasky diversity; diversity measures; finite metric magnitude; L1 distance; uniform spacing; Pareto-front approximation; multiobjective optimization; fixed-cardinality subset selection

Authors: Michael T. M. Emmerich, Mahboubeh Nezhadmoghaddam, Jesús Guillermo Falcón Cardona

We study fixed-cardinality maximization of the inverse-matrix Solow--Polasky diversity, equivalently finite metric magnitude for the exponential kernel, on one-dimensional and ordered metric sets. The analysis starts from the known finite-line gap formula for the exponential kernel, which writes the excess inverse-matrix diversity as a sum of functions of consecutive gaps. Building on this formula, the main interval theorem proves that, for every $k\geq 2$, the unique maximizing $k$-point subset of $[0,1]$ is the equally spaced set. Thus the objective selects a uniform gap representation on the real line. A converse kernel proposition shows that, among normalized non-increasing distance kernels, requiring the corresponding adjacent-gap additive structure forces the exponential family. Further results transfer the interval theorem to ordered $\ell_1$ (L1, or Manhattan) curves by isometry: the maximizing sets are uniform in accumulated $\ell_1$ length. As a consequence, monotone biobjective Pareto fronts admit Solow--Polasky optimal finite approximations that are uniformly spaced in accumulated objective-space change, a natural representation when all parts of a continuous front should be covered. Examples, including a dense connected front and a finite disconnected ZDT3 front, illustrate how the continuous uniform-gap result appears on discrete candidate sets. Solow-Polasky diversity; diversity measures; finite metric magnitude; L1 distance; uniform spacing; Pareto-front approximation; multiobjective optimization; fixed-cardinality subset selection

Friday, May 22 2026, 00:00

Bifunction and Interlevel Delaunay Trifiltrations

Authors: Ángel Javier Alonso, Michael Kerber, Tung Lam, Michael Lesnick, Abhishek Rathod

A key property of the Delaunay filtration is that it is topologically (i.e., weakly) equivalent to the offset (union-of-balls) filtration. Recently, this filtration has been extended to point clouds equipped with an $\mathbb{R}$-valued function, yielding a computable 2-parameter filtration that satisfies an analogous weak equivalence. Motivated in part by the study of time-varying data, we introduce a 3-parameter extension of the Delaunay filtration for point clouds equipped with an $\mathbb{R}^2$-valued function, also satisfying an analogous weak equivalence. For a point cloud $X \subset \mathbb{R}^d$, our trifiltration has size $O\bigl(|X|^{\lceil(d+1)/2\rceil+1}\bigr)$. We present an algorithm that computes this trifiltration in time $O\bigl(|X|^{\lceil d/2\rceil+2}\bigr)$, together with an implementation. Our experiments demonstrate that implementation can handle thousands of points in $\mathbb{R}^3$, with memory growth that is nearly linear.

Authors: Ángel Javier Alonso, Michael Kerber, Tung Lam, Michael Lesnick, Abhishek Rathod

A key property of the Delaunay filtration is that it is topologically (i.e., weakly) equivalent to the offset (union-of-balls) filtration. Recently, this filtration has been extended to point clouds equipped with an $\mathbb{R}$-valued function, yielding a computable 2-parameter filtration that satisfies an analogous weak equivalence. Motivated in part by the study of time-varying data, we introduce a 3-parameter extension of the Delaunay filtration for point clouds equipped with an $\mathbb{R}^2$-valued function, also satisfying an analogous weak equivalence. For a point cloud $X \subset \mathbb{R}^d$, our trifiltration has size $O\bigl(|X|^{\lceil(d+1)/2\rceil+1}\bigr)$. We present an algorithm that computes this trifiltration in time $O\bigl(|X|^{\lceil d/2\rceil+2}\bigr)$, together with an implementation. Our experiments demonstrate that implementation can handle thousands of points in $\mathbb{R}^3$, with memory growth that is nearly linear.

Friday, May 22 2026, 00:00

On the Parameterized Complexity of Min-Sum-Radii

Authors: Pankaj Kumar, Haiko Müller, Sebastian Ordyniak, Melanie Schmidt

In the Min-Sum-Radii (MSR) clustering problem, we are given a finite set X of n points in a metric space. The objective is to find at most k clusters centered at a subset of these points such that every point of X is assigned to one of the clusters, minimizing the sum of the radii of the clusters. The problem is known to be NP-hard even on metrics induced by weighted planar graphs and metrics with constant doubling dimension, as shown by Gibson et al. (SWAT 2008). In this work, we investigate the parameterized complexity of MSR on metrics induced by undirected graphs. We distinguish between weighted graph metrics (with positive edge weights) and unweighted graph metrics (where all edges have unit weight). Weighted Graph Metrics: We show that MSR is W[1]-hard on metrics induced by weighted bipartite graphs, when parameterized by the combined parameter k (the number of clusters) and Delta (the cost of the clustering). We then investigate the structural parameterized complexity of the problem. Drexler et al. (arXiv:2310.02130) showed that the MSR problem admits an XP algorithm on metrics induced by weighted graphs when parameterized by treewidth, and asked whether this can be improved to fixed-parameter tractability. We first answer their question in the negative, and more strongly show that MSR stays W[1]-hard on metrics induced by undirected weighted bipartite graphs when parameterized by the vertex cover number plus k. We then turn our attention to parameters for dense graphs and show that MSR remains W[1]-hard when parameterized by k+Delta even on cliques and complete bipartite graphs. On the positive side, we employ the known XP algorithm parameterized by treewidth, to show that the MSR problem is FPT when parameterized by the parameter treewidth plus Delta.

Authors: Pankaj Kumar, Haiko Müller, Sebastian Ordyniak, Melanie Schmidt

In the Min-Sum-Radii (MSR) clustering problem, we are given a finite set X of n points in a metric space. The objective is to find at most k clusters centered at a subset of these points such that every point of X is assigned to one of the clusters, minimizing the sum of the radii of the clusters. The problem is known to be NP-hard even on metrics induced by weighted planar graphs and metrics with constant doubling dimension, as shown by Gibson et al. (SWAT 2008). In this work, we investigate the parameterized complexity of MSR on metrics induced by undirected graphs. We distinguish between weighted graph metrics (with positive edge weights) and unweighted graph metrics (where all edges have unit weight). Weighted Graph Metrics: We show that MSR is W[1]-hard on metrics induced by weighted bipartite graphs, when parameterized by the combined parameter k (the number of clusters) and Delta (the cost of the clustering). We then investigate the structural parameterized complexity of the problem. Drexler et al. (arXiv:2310.02130) showed that the MSR problem admits an XP algorithm on metrics induced by weighted graphs when parameterized by treewidth, and asked whether this can be improved to fixed-parameter tractability. We first answer their question in the negative, and more strongly show that MSR stays W[1]-hard on metrics induced by undirected weighted bipartite graphs when parameterized by the vertex cover number plus k. We then turn our attention to parameters for dense graphs and show that MSR remains W[1]-hard when parameterized by k+Delta even on cliques and complete bipartite graphs. On the positive side, we employ the known XP algorithm parameterized by treewidth, to show that the MSR problem is FPT when parameterized by the parameter treewidth plus Delta.

Friday, May 22 2026, 00:00

Asymptotic Rank Speedup Theorems, Revisited

Authors: Josh Alman, Baitian Li

Motivated by fast matrix multiplication and recent connections between asymptotic tensor rank and fine-grained complexity, we revisit classical tools from the matrix multiplication literature and develop a framework for obtaining improved asymptotic rank upper bounds for tensors beyond matrix multiplication. In the 1980s, Coppersmith-Winograd and Strassen discovered a series of speedup theorems for asymptotic rank: in certain regimes, one can extract additional terms from a border rank upper bound on a tensor $T$, and then use these terms to obtain an improved asymptotic rank of $T$. We establish general speedup theorems that subsume these results and enable quantitative improvements. Two representative applications are: (1) The asymptotic rank of the small Coppersmith-Winograd tensor $\mathrm{cw}_q$ is less than its border rank. For instance, we prove the asymptotic rank of $\mathrm{cw}_2$ is smaller than $3.931$, improving on $\underline{\mathrm{R}}(\mathrm{cw}_2)=4$. It is known that if the asymptotic rank of $\mathrm{cw}_2$ equals $3$, this would imply $ω=2$. (2) A general improvement over Strassen's bound: we obtain an upper bound below $d^{2ω/3}$ on the asymptotic rank of any $d\times d\times d$ tensor. To make full use of speedups, we analyze degenerations in which both sides are nontrivial direct sums, a setting where the optimal quantitative bound one can achieve was previously unclear. We do so via an approach we call Strassen calculus: a systematic method for converting such degeneration data into explicit asymptotic rank bounds using Strassen's theory of the asymptotic spectrum.

Authors: Josh Alman, Baitian Li

Motivated by fast matrix multiplication and recent connections between asymptotic tensor rank and fine-grained complexity, we revisit classical tools from the matrix multiplication literature and develop a framework for obtaining improved asymptotic rank upper bounds for tensors beyond matrix multiplication. In the 1980s, Coppersmith-Winograd and Strassen discovered a series of speedup theorems for asymptotic rank: in certain regimes, one can extract additional terms from a border rank upper bound on a tensor $T$, and then use these terms to obtain an improved asymptotic rank of $T$. We establish general speedup theorems that subsume these results and enable quantitative improvements. Two representative applications are: (1) The asymptotic rank of the small Coppersmith-Winograd tensor $\mathrm{cw}_q$ is less than its border rank. For instance, we prove the asymptotic rank of $\mathrm{cw}_2$ is smaller than $3.931$, improving on $\underline{\mathrm{R}}(\mathrm{cw}_2)=4$. It is known that if the asymptotic rank of $\mathrm{cw}_2$ equals $3$, this would imply $ω=2$. (2) A general improvement over Strassen's bound: we obtain an upper bound below $d^{2ω/3}$ on the asymptotic rank of any $d\times d\times d$ tensor. To make full use of speedups, we analyze degenerations in which both sides are nontrivial direct sums, a setting where the optimal quantitative bound one can achieve was previously unclear. We do so via an approach we call Strassen calculus: a systematic method for converting such degeneration data into explicit asymptotic rank bounds using Strassen's theory of the asymptotic spectrum.

Friday, May 22 2026, 00:00

Optimal Testing of Reed-Muller Codes with an Online Adversary

Authors: Esty Kelman, Uri Meir, Kai Zhe Zheng

Motivated by applications to property testing in the online-erasure model of Kalemaj, Raskhodnikova, and Varma (ITCS 2022 and Theory of Computing 2023), we define and analyze {\em semi-sample-based testers} for Reed-Muller codes. The task in Reed-Muller testing is to determine whether an input function $f: \F^n \to \F$ belongs to the Reed-Muller code or is far from it, using as few point queries to $f$ as possible. Reed-Muller testing is a well-studied task with its roots in both the Property Testing and Probabilistically Checkable Proofs literature. The online-erasure model introduces a twist: after each query made, an adversary may erase up to $t$ points of the input function, potentially thwarting any test in which the queries follow a predictable pattern. Semi-sample-based testers are a hybrid between sample-based testers -- which can only make uniformly random queries to the input function -- and standard testers, which can choose their queries freely. They are designed with the online-erasure model in mind and operate by first choosing some subset $S$ of the domain and then making their queries uniformly at random inside of $S$. We describe semi-sample-based testers for the Reed-Muller code and give an optimal analysis of their soundness. Consequently, we show that semi-sample-based testers are indeed effective in the presence of online erasures, and thereby achieve optimal query complexity for testing the Reed-Muller code in the online-erasure model. This result improves upon prior work of Minzer and Zheng (SODA 2024). As an added bonus, we show that semi-sample-based testers also exist for the lifted affine-invariant codes of Guo, Kopparty, and Sudan (ITCS 2013), thereby providing the first known testers for these codes in the online-erasure model.

Authors: Esty Kelman, Uri Meir, Kai Zhe Zheng

Motivated by applications to property testing in the online-erasure model of Kalemaj, Raskhodnikova, and Varma (ITCS 2022 and Theory of Computing 2023), we define and analyze {\em semi-sample-based testers} for Reed-Muller codes. The task in Reed-Muller testing is to determine whether an input function $f: \F^n \to \F$ belongs to the Reed-Muller code or is far from it, using as few point queries to $f$ as possible. Reed-Muller testing is a well-studied task with its roots in both the Property Testing and Probabilistically Checkable Proofs literature. The online-erasure model introduces a twist: after each query made, an adversary may erase up to $t$ points of the input function, potentially thwarting any test in which the queries follow a predictable pattern. Semi-sample-based testers are a hybrid between sample-based testers -- which can only make uniformly random queries to the input function -- and standard testers, which can choose their queries freely. They are designed with the online-erasure model in mind and operate by first choosing some subset $S$ of the domain and then making their queries uniformly at random inside of $S$. We describe semi-sample-based testers for the Reed-Muller code and give an optimal analysis of their soundness. Consequently, we show that semi-sample-based testers are indeed effective in the presence of online erasures, and thereby achieve optimal query complexity for testing the Reed-Muller code in the online-erasure model. This result improves upon prior work of Minzer and Zheng (SODA 2024). As an added bonus, we show that semi-sample-based testers also exist for the lifted affine-invariant codes of Guo, Kopparty, and Sudan (ITCS 2013), thereby providing the first known testers for these codes in the online-erasure model.

Friday, May 22 2026, 00:00

Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees

Authors: Christian Janos Lebeda, David Erb, Tudor Cebere, Aurélien Bellet

Random forests are widely used in fields involving sensitive tabular data, but existing approaches to enforcing differential privacy (DP) typically degrade performance to the point of impracticality. In this paper, we introduce Lumberjack, a differentially private random forest algorithm that achieves substantially higher utility by constructing large random decision trees and then applying aggressive, privacy-preserving pruning to retain only sufficiently populated nodes. A key component of our approach is a novel $(\varepsilon,δ)$-DP heavy hitter detection algorithm for hierarchical data, whose error is $O_{\varepsilon,δ}(\sqrt{\log h})$ for trees of height $h$ and may be of independent interest. This favorable scaling enables the use of significantly deeper trees than in prior work, leading to improved expressiveness under privacy constraints. Our empirical evaluation on benchmark datasets shows that Lumberjack consistently outperforms prior DP random forest methods, establishing a new state of the art. In particular, our approach yields substantial improvements in the privacy-utility trade-off for practical privacy budgets. Our findings suggest that carefully designed DP random forests can close much of the utility gap, highlighting a promising and underexplored direction for future research.

Authors: Christian Janos Lebeda, David Erb, Tudor Cebere, Aurélien Bellet

Random forests are widely used in fields involving sensitive tabular data, but existing approaches to enforcing differential privacy (DP) typically degrade performance to the point of impracticality. In this paper, we introduce Lumberjack, a differentially private random forest algorithm that achieves substantially higher utility by constructing large random decision trees and then applying aggressive, privacy-preserving pruning to retain only sufficiently populated nodes. A key component of our approach is a novel $(\varepsilon,δ)$-DP heavy hitter detection algorithm for hierarchical data, whose error is $O_{\varepsilon,δ}(\sqrt{\log h})$ for trees of height $h$ and may be of independent interest. This favorable scaling enables the use of significantly deeper trees than in prior work, leading to improved expressiveness under privacy constraints. Our empirical evaluation on benchmark datasets shows that Lumberjack consistently outperforms prior DP random forest methods, establishing a new state of the art. In particular, our approach yields substantial improvements in the privacy-utility trade-off for practical privacy budgets. Our findings suggest that carefully designed DP random forests can close much of the utility gap, highlighting a promising and underexplored direction for future research.

Friday, May 22 2026, 00:00

The Secretary Problem with a Stochastic Precursor

Authors: Franziska Eberle, Alexander Lindermayr

In learning-augmented online algorithms, predictions are usually valued for what they say: a value estimate, a solution, or an algorithmic recommendation. This paper shows that predictions can also be valuable solely due to their arrival time. We study the fundamental secretary problem augmented with a stochastic precursor: a content-free signal that is guaranteed to arrive no later than the best item, but is otherwise stochastically timed. The signal does not carry any additional information; nevertheless, its timing alone changes the structure of optimal stopping. We characterize optimal policies in the random-order and adversarial-order models. In random order, a single uniformly timed precursor already gives success probability at least $\frac12$, improving on the classic $\frac1e$ benchmark. With increasingly late precursors, the success probability approaches $1$. In adversarial order, for which traditional models do not admit strong guarantees, sufficiently concentrated precursors recover constant success guarantees. Our results show that such novel forms of asynchronous temporal information are a distinct and powerful form of advice in online decision making and may also be effective for other problems.

Authors: Franziska Eberle, Alexander Lindermayr

In learning-augmented online algorithms, predictions are usually valued for what they say: a value estimate, a solution, or an algorithmic recommendation. This paper shows that predictions can also be valuable solely due to their arrival time. We study the fundamental secretary problem augmented with a stochastic precursor: a content-free signal that is guaranteed to arrive no later than the best item, but is otherwise stochastically timed. The signal does not carry any additional information; nevertheless, its timing alone changes the structure of optimal stopping. We characterize optimal policies in the random-order and adversarial-order models. In random order, a single uniformly timed precursor already gives success probability at least $\frac12$, improving on the classic $\frac1e$ benchmark. With increasingly late precursors, the success probability approaches $1$. In adversarial order, for which traditional models do not admit strong guarantees, sufficiently concentrated precursors recover constant success guarantees. Our results show that such novel forms of asynchronous temporal information are a distinct and powerful form of advice in online decision making and may also be effective for other problems.

Friday, May 22 2026, 00:00

A Coalgebraic Dijkstra Algorithm

Authors: Takahiro Sanada, Yoàv Montacute, Kittiphon Phalakarn, Ichiro Hasuo

The Dijkstra algorithm is a classical method for solving the shortest path problem on weighted graphs. There are several variations of the Dijkstra algorithm, including algorithms for the widest path problem and for two-player games. In this paper, we introduce the coalgebraic shortest path problem (CSPP), a unifying framework for a broad class of optimization problems on state-transition systems. This framework encompasses not only the aforementioned problems but also new ones such as the shortest binary tree problem. We further present a coalgebraic Dijkstra algorithm for solving the CSPP efficiently under a suitable condition. Our condition is necessary and sufficient for the algorithm to return correct solutions, thereby providing a precise criterion for when Dijkstra-style acceleration is possible. We also show that the proposed algorithm achieves asymptotic complexity comparable to that of the classical Dijkstra algorithm.

Authors: Takahiro Sanada, Yoàv Montacute, Kittiphon Phalakarn, Ichiro Hasuo

The Dijkstra algorithm is a classical method for solving the shortest path problem on weighted graphs. There are several variations of the Dijkstra algorithm, including algorithms for the widest path problem and for two-player games. In this paper, we introduce the coalgebraic shortest path problem (CSPP), a unifying framework for a broad class of optimization problems on state-transition systems. This framework encompasses not only the aforementioned problems but also new ones such as the shortest binary tree problem. We further present a coalgebraic Dijkstra algorithm for solving the CSPP efficiently under a suitable condition. Our condition is necessary and sufficient for the algorithm to return correct solutions, thereby providing a precise criterion for when Dijkstra-style acceleration is possible. We also show that the proposed algorithm achieves asymptotic complexity comparable to that of the classical Dijkstra algorithm.

Friday, May 22 2026, 00:00

Optimal $e^{(γ+o(1))n}$-Approximation of the Permanent of Positive Semidefinite Matrices

Authors: Nima Anari, Farzam Ebrahimnejad

We determine, up to lower-order terms in the exponent, the best possible deterministic polynomial-time approximation ratio for the permanent of a Hermitian positive semidefinite matrix. If $A\succeq 0$ has no zero diagonal entry, $d=\operatorname{rank}(A)$, $A=VV^\dagger$ with $V\in\mathbb{C}^{n\times d}$ full column rank, and $v_1,\ldots,v_n$ are the rows of $V$, define \[ Φ(V)=\max_{X\succ 0} \left\{\sum_{i=1}^n \log(v_i^\dagger Xv_i)+\log\det X-\operatorname{tr} X+d\right\}, \qquad \widehat P(A)=e^{Φ(V)}. \] We prove the exact sandwich \[ e^{-γn}\widehat P(A)\le \operatorname{per}(A)\le \widehat P(A). \] Here $γ$ is the Euler--Mascheroni constant. Since the maximization is concave, this gives a deterministic polynomial-time $e^{(γ+\varepsilon)n}$-approximation for every $\varepsilon>0$. Combined with the previous $e^{(γ-\varepsilon)n}$-hardness of approximation for positive semidefinite permanents, this resolves the optimal exponential approximation ratio for deterministic polynomial-time algorithms as $e^{(γ+o(1))n}$, assuming $\mathrm{P}\ne\mathrm{NP}$. The proof is an entropy argument applied to the standard Wick integral formula for $\operatorname{per}(A)$; the loss is exactly $γ$ per factor because $\mathbb{E}[\log T]=-γ$ for $T\sim\operatorname{Exp}(1)$. The result was obtained through interactions with GPT 5.5 Pro Extended: the first author's interaction was one-shot, while the second author's was a separate multi-turn interaction with high-level guidance. Both authors verified the theorem and proof. Codex was used to assemble and typeset the manuscript.

Authors: Nima Anari, Farzam Ebrahimnejad

We determine, up to lower-order terms in the exponent, the best possible deterministic polynomial-time approximation ratio for the permanent of a Hermitian positive semidefinite matrix. If $A\succeq 0$ has no zero diagonal entry, $d=\operatorname{rank}(A)$, $A=VV^\dagger$ with $V\in\mathbb{C}^{n\times d}$ full column rank, and $v_1,\ldots,v_n$ are the rows of $V$, define \[ Φ(V)=\max_{X\succ 0} \left\{\sum_{i=1}^n \log(v_i^\dagger Xv_i)+\log\det X-\operatorname{tr} X+d\right\}, \qquad \widehat P(A)=e^{Φ(V)}. \] We prove the exact sandwich \[ e^{-γn}\widehat P(A)\le \operatorname{per}(A)\le \widehat P(A). \] Here $γ$ is the Euler--Mascheroni constant. Since the maximization is concave, this gives a deterministic polynomial-time $e^{(γ+\varepsilon)n}$-approximation for every $\varepsilon>0$. Combined with the previous $e^{(γ-\varepsilon)n}$-hardness of approximation for positive semidefinite permanents, this resolves the optimal exponential approximation ratio for deterministic polynomial-time algorithms as $e^{(γ+o(1))n}$, assuming $\mathrm{P}\ne\mathrm{NP}$. The proof is an entropy argument applied to the standard Wick integral formula for $\operatorname{per}(A)$; the loss is exactly $γ$ per factor because $\mathbb{E}[\log T]=-γ$ for $T\sim\operatorname{Exp}(1)$. The result was obtained through interactions with GPT 5.5 Pro Extended: the first author's interaction was one-shot, while the second author's was a separate multi-turn interaction with high-level guidance. Both authors verified the theorem and proof. Codex was used to assemble and typeset the manuscript.

Friday, May 22 2026, 00:00

Minimum Sum Set Cover: Structures and Algorithm

Authors: Zhongyi Zhang, Yixin Cao

A set cover of a hypergraph $H$ is a set of vertices intersecting every hyperedge. In the minimum sum set cover problem, vertices are selected one by one; each edge pays the position of the first vertex that hits it, and the objective is to minimize the total cost. When $H$ is a graph, this is the minimum sum vertex cover problem. A solution is specified by a set cover $S$ together with an ordering of its vertices. While the classical set cover problem seeks to minimize $|S|$, the minimum sum variant favors covering many edges early and may prefer larger covers. This motivates a natural question: how large can the gap between~$\overrightarrowτ$ and $τ$ be? We prove an upper bound $\overrightarrowτ \le τ\log_{2} \lvert E(H)\rvert$, and show that for any positive~$n$, there exists a hypergraph $H$ on $n + 3$ vertices with $τ=3$ and $\overrightarrowτ=n$. For graphs, we obtain stronger bounds: we prove~$\overrightarrowτ \le 2τ\log_{2} τ$, improving the bound of Liu et al.\ [Theor. Comput. Sci., 2025], and we construct graphs with~$\overrightarrowτ = Ω\left( \frac{τ\log τ}{\log\log τ}\right)$, nearly matching this upper bound. On the algorithmic side, we show that minimum sum set cover is fixed-parameter tractable on bounded-rank hypergraphs, parameterized by~$\overrightarrowτ$, extending the algorithm of Liu et al.\ for graphs (i.e., rank-two hypergraphs).

Authors: Zhongyi Zhang, Yixin Cao

A set cover of a hypergraph $H$ is a set of vertices intersecting every hyperedge. In the minimum sum set cover problem, vertices are selected one by one; each edge pays the position of the first vertex that hits it, and the objective is to minimize the total cost. When $H$ is a graph, this is the minimum sum vertex cover problem. A solution is specified by a set cover $S$ together with an ordering of its vertices. While the classical set cover problem seeks to minimize $|S|$, the minimum sum variant favors covering many edges early and may prefer larger covers. This motivates a natural question: how large can the gap between~$\overrightarrowτ$ and $τ$ be? We prove an upper bound $\overrightarrowτ \le τ\log_{2} \lvert E(H)\rvert$, and show that for any positive~$n$, there exists a hypergraph $H$ on $n + 3$ vertices with $τ=3$ and $\overrightarrowτ=n$. For graphs, we obtain stronger bounds: we prove~$\overrightarrowτ \le 2τ\log_{2} τ$, improving the bound of Liu et al.\ [Theor. Comput. Sci., 2025], and we construct graphs with~$\overrightarrowτ = Ω\left( \frac{τ\log τ}{\log\log τ}\right)$, nearly matching this upper bound. On the algorithmic side, we show that minimum sum set cover is fixed-parameter tractable on bounded-rank hypergraphs, parameterized by~$\overrightarrowτ$, extending the algorithm of Liu et al.\ for graphs (i.e., rank-two hypergraphs).

Friday, May 22 2026, 00:00

Robust Statistical Estimators with Bounded Empirical Sensitivity

Authors: Valentio Iverson, Gautam Kamath, Argyris Mouzakis, Adam Smith

We introduce a new measure of robustness for statistical estimators, which we call \emph{empirical sensitivity}. An estimator $\hat θ$ has bounded empirical sensitivity if, with high probability over a dataset $X = (X_1, \dots, X_n) \sim \mathcal{D}^{\otimes n}$, for any dataset $Y$ obtained by modifying at most $ηn$ points in $X$, we have that $\hat θ(Y)$ is close to $\hat θ(X)$. We study bounds on this quantity for the prototypical problem of Gaussian mean estimation. We prove new lower bounds, showing that for any estimator $\hat μ$ which achieves an optimal $\ell_2$-error bound of $O\left(\sqrt{d/n}\right)$, the empirical sensitivity is at least $Ω\left(η+ \sqrt{ηd/n}\right)$. The two terms arise due to obstructions on the mean and variance (via an Efron-Stein argument) of such an estimator. We show that this bound is tight up to logarithmic factors, by employing recent results for robust empirical mean estimation.

Authors: Valentio Iverson, Gautam Kamath, Argyris Mouzakis, Adam Smith

We introduce a new measure of robustness for statistical estimators, which we call \emph{empirical sensitivity}. An estimator $\hat θ$ has bounded empirical sensitivity if, with high probability over a dataset $X = (X_1, \dots, X_n) \sim \mathcal{D}^{\otimes n}$, for any dataset $Y$ obtained by modifying at most $ηn$ points in $X$, we have that $\hat θ(Y)$ is close to $\hat θ(X)$. We study bounds on this quantity for the prototypical problem of Gaussian mean estimation. We prove new lower bounds, showing that for any estimator $\hat μ$ which achieves an optimal $\ell_2$-error bound of $O\left(\sqrt{d/n}\right)$, the empirical sensitivity is at least $Ω\left(η+ \sqrt{ηd/n}\right)$. The two terms arise due to obstructions on the mean and variance (via an Efron-Stein argument) of such an estimator. We show that this bound is tight up to logarithmic factors, by employing recent results for robust empirical mean estimation.

Friday, May 22 2026, 00:00

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces

Authors: Stephen Arndt, Kirk Pruhs, Trung Tran

We consider the classic cake cutting problem in the Robertson-Webb model, with the objective of proportional fairness. We show that any randomized algorithm must use $Ω(n \log n)$ queries.

Authors: Stephen Arndt, Kirk Pruhs, Trung Tran

We consider the classic cake cutting problem in the Robertson-Webb model, with the objective of proportional fairness. We show that any randomized algorithm must use $Ω(n \log n)$ queries.

Friday, May 22 2026, 00:00

Finding a Solution to the Erdős-Ginzburg-Ziv Theorem in Linear Time

Authors: Sunghyeon Jo

The Erdős-Ginzburg-Ziv theorem states that every sequence of 2n - 1 integers contains a subsequence of length n whose sum is divisible by n. Choi, Kang, and Lim gave a simple deterministic O(n log n) algorithm for finding such a subsequence, and Leung recently improved this to O(n log log log n). We give a deterministic linear-time algorithm. The core is a linear-time algorithm for the following prime target subset-sum problem: given p - 1 nonzero residues in Z_p and a target residue, find a subset with the prescribed sum. Our algorithm maintains a compact arithmetic-progression representation of reachable sums. When two progressions intersect, a bounded Frobenius interval in their sum allows them to be merged into one longer progression, with enough growth to pay for the update. When the representation either contains a full progression or covers all nonzero residues, the target residue is recovered constructively. The standard multiplicative reduction then extends the prime algorithm to arbitrary moduli.

Authors: Sunghyeon Jo

The Erdős-Ginzburg-Ziv theorem states that every sequence of 2n - 1 integers contains a subsequence of length n whose sum is divisible by n. Choi, Kang, and Lim gave a simple deterministic O(n log n) algorithm for finding such a subsequence, and Leung recently improved this to O(n log log log n). We give a deterministic linear-time algorithm. The core is a linear-time algorithm for the following prime target subset-sum problem: given p - 1 nonzero residues in Z_p and a target residue, find a subset with the prescribed sum. Our algorithm maintains a compact arithmetic-progression representation of reachable sums. When two progressions intersect, a bounded Frobenius interval in their sum allows them to be merged into one longer progression, with enough growth to pay for the update. When the representation either contains a full progression or covers all nonzero residues, the target residue is recovered constructively. The standard multiplicative reduction then extends the prime algorithm to arbitrary moduli.

Friday, May 22 2026, 00:00

Near-Optimal Generalized Private Testing

Authors: Anamay Chaturvedi, Monika Henzinger, Jalaj Upadhyay

In differential privacy (DP), the generalized private testing problem was introduced by Liu and Talwar (STOC 2019). Given a dataset $X \in \mathcal{X}$ and a sequence of black-box $\varepsilon_t$-DP mechanisms $M_t:\mathcal{X}\to\{+1,-1\}$, the analyst must accept the first mechanism whose success probability $p_t=\Pr[M_t(X)=+1]$ exceeds a given threshold $p^*\in(0,1)$, while achieving DP. Accuracy is measured by the gap between $p^*$ and a rejection threshold $\bar{p}$, such that with probability $1-β$ for all $t\geq1$, if $p_t\leq\bar{p}$, then $M_t$ is rejected, and if $p_t\geq p^*$, then it is accepted. This generalizes the standard private testing problem, whose solution, the Sparse Vector Technique, is ubiquitous in DP. We introduce the Generalized Thresholding Mechanism (GTM) for generalized private testing. For $\varepsilon>0$ and any sequence of $(\varepsilon_t,δ_t)$-DP mechanisms $M_t$, the GTM is pure $\varepsilon$-DP. For $θ>0$, $γ\in(1,2]$, and $β\in(0,1)$, $\bar{p}_t=\max(p^*/γΛ_t, 1 - γΛ_t(1-p^*))-δ_t/\varepsilon_t$ for $Λ_t=(5t\ln^3(t+2))^{(2+θ)\varepsilon_t/\varepsilon}(4/β)^{(3+θ+2/θ)\varepsilon_t/\varepsilon}$. With probability $1-β$, the number of evaluations of $M_t$ is at most $O((\ln(t/β)/(γ-1)^2)\max(Λ_t/p^*,(1-p^*)^{-1}))$ for all $t\geq 1$. Our lower bounds prove near-optimality of our accuracy and sample complexity guarantees. Via the GTM, we give a black-box reduction for DP optimization from the continual observation (CO) setting to the batch setting. This gives us the first DP-CO algorithms for many maximization problems. Further, the GTM permits an adaptive choice of acceptance thresholds $(p^*_t)_{t\geq1}$, addressing a challenge mentioned in prior work on using generalized private testing for hyperparameter optimization (Papernot and Steinke (ICLR 2022)).

Authors: Anamay Chaturvedi, Monika Henzinger, Jalaj Upadhyay

In differential privacy (DP), the generalized private testing problem was introduced by Liu and Talwar (STOC 2019). Given a dataset $X \in \mathcal{X}$ and a sequence of black-box $\varepsilon_t$-DP mechanisms $M_t:\mathcal{X}\to\{+1,-1\}$, the analyst must accept the first mechanism whose success probability $p_t=\Pr[M_t(X)=+1]$ exceeds a given threshold $p^*\in(0,1)$, while achieving DP. Accuracy is measured by the gap between $p^*$ and a rejection threshold $\bar{p}$, such that with probability $1-β$ for all $t\geq1$, if $p_t\leq\bar{p}$, then $M_t$ is rejected, and if $p_t\geq p^*$, then it is accepted. This generalizes the standard private testing problem, whose solution, the Sparse Vector Technique, is ubiquitous in DP. We introduce the Generalized Thresholding Mechanism (GTM) for generalized private testing. For $\varepsilon>0$ and any sequence of $(\varepsilon_t,δ_t)$-DP mechanisms $M_t$, the GTM is pure $\varepsilon$-DP. For $θ>0$, $γ\in(1,2]$, and $β\in(0,1)$, $\bar{p}_t=\max(p^*/γΛ_t, 1 - γΛ_t(1-p^*))-δ_t/\varepsilon_t$ for $Λ_t=(5t\ln^3(t+2))^{(2+θ)\varepsilon_t/\varepsilon}(4/β)^{(3+θ+2/θ)\varepsilon_t/\varepsilon}$. With probability $1-β$, the number of evaluations of $M_t$ is at most $O((\ln(t/β)/(γ-1)^2)\max(Λ_t/p^*,(1-p^*)^{-1}))$ for all $t\geq 1$. Our lower bounds prove near-optimality of our accuracy and sample complexity guarantees. Via the GTM, we give a black-box reduction for DP optimization from the continual observation (CO) setting to the batch setting. This gives us the first DP-CO algorithms for many maximization problems. Further, the GTM permits an adaptive choice of acceptance thresholds $(p^*_t)_{t\geq1}$, addressing a challenge mentioned in prior work on using generalized private testing for hyperparameter optimization (Papernot and Steinke (ICLR 2022)).

Friday, May 22 2026, 00:00

Interview with Naoki Kobayashi, CONCUR 2026 ToT Award recipient

from Luca Aceto

As mentioned in a previous post, Naoki Kobayashi will receive one of the two CONCUR 2026 Test-of-Time Awards at CONCUR 2026. Naoki has kindly agreed to answer some questions of mine on his award-winning paper via email. I am delighted to post his answers below and hope you'll enjoy reading them as much as I did. Thanks, Naoki!

Luca: You receive the CONCUR ToT Award 2026 for your paper A New Type System for Deadlock-Free Processes, which appeared at CONCUR 2006. That article is the culmination of a series of contributions you gave on the development of type systems for variations on the pi-calculus that guarantee deadlock-freedom. Could you briefly explain to our readers how you came to study the question addressed in your award-winning article and how the main ideas in your CONCUR 2006 paper evolved over time? Which of the ideas and results in your paper did you find most pleasing, surprising or challenging?

Naoki: If I remember correctly, the idea of using types to ensure deadlock-freedom came up during discussions on the linear pi-calculus with Benjamin Pierce and David Turner [1]. Indeed, if one wants to ensure that a channel is really used exactly once, one also has to ensure that the process does not get stuck before using it. An initial result on type systems for deadlock-freedom was published in LICS 1997 [2].

After that, the type system was extended in two directions: enabling automated type inference and increasing expressiveness. These were somewhat conflicting goals, and the CONCUR 2006 paper achieved a balance between them. The core idea was as follows. To ensure deadlock-freedom, it is necessary to control dependencies among different channels. In [2], such dependencies were expressed using “time tags” and a possibly infinite partial order on them. The time tags were later replaced by natural numbers, called capability and obligation levels, to enable automated inference [3], but at the cost of expressive power. The CONCUR 2006 paper combined a restricted form of time tags with capability and obligation levels, thereby recovering much of the expressive power while retaining automated inference.

What I found most pleasing was precisely this balance: the paper showed that one could make the type system significantly more practical without completely giving up the conceptual elegance and expressiveness of the earlier formulation.

[1] Naoki Kobayashi, Benjamin C. Pierce, David N. Turner, Linearity and the Pi-Calculus. POPL 1996: 358-37
[2] Naoki Kobayashi, A Partially Deadlock-Free Typed Process Calculus. LICS 1997: 128-139
[3] Naoki Kobayashi, Type-based information flow analysis for the pi-calculus. Acta Informatica 42(4-5): 291-347 (2005)
Luca: The contribution in your article achieves a good trade-off between expressiveness of the type system and ease of implementing its associated type inference algorithm. Did you or any other researcher try to extend the range of examples that could be handled by a variation on your type system? Do you think that it would be worth doing so or have we hit the point of diminishing returns, where any advance would be very technical and hard to implement?
Naoki: With Elena Giachino and Cosimo Laneve [4], I indeed investigated such an extension. The system developed there can deal with infinite chains of dependencies more general than those handled in the CONCUR 2006 paper. It was, however, developed for value-passing CCS rather than the pi-calculus. Incorporating the idea of [4] into the pi-calculus setting remains future work. Another possible direction would be to combine the approach with generic types [5], which can capture precise dependencies among a set of channels. Unfortunately, I did not have time to fully explore this direction.
As for whether it is worth pushing this line further, my feeling is that further general-purpose extensions may easily become technically involved and hard to implement. Perhaps a more promising direction would be to adapt the type system to real concurrent languages such as Go, and then see what kinds of extensions are most beneficial in practice.

[4] Elena Giachino, Naoki Kobayashi, Cosimo Laneve, Deadlock Analysis of Unbounded Process Networks. CONCUR 2014: 63-77[5] Atsushi Igarashi, Naoki Kobayashi, A generic type system for the Pi-calculus. Theor. Comput. Sci. 311(1-3): 121-163 (2004)
Luca: Commendably, you supported the theoretical developments in your article with an implementation in TyPiCal. What role did the implementation work play in your research on type systems guaranteeing deadlock-freedom? Did the theoretical developments benefit from the implementation? Do you think that every proposal for a type system for some language ought to be accompanied by an implementation?
Naoki: TyPiCal was initially developed as a proof of concept for the type inference algorithm of [3]. At that time, the theory had already been fully developed, and the implementation was mainly used to convince readers that the algorithm indeed works in practice. In later extensions of TyPiCal, for the CONCUR 2006 paper and the work of [6], the implementation was also useful for checking the theories.
I think it is desirable for every type-system proposal to be accompanied by an implementation, although I would not say that it is absolutely necessary. An implementation is useful not only for checking the theory, but also for identifying limitations of the theory and suggesting possible directions for improvement.

[6] Naoki Kobayashi, Davide Sangiorgi, A Hybrid Type System for Lock-Freedom of Mobile Processes. CAV 2008: 80-93
Luca: In your paper, you showed, amongst other things, that the simply-typed λ-calculus with recursion could be encoded in the deadlock-free fragment of your calculus. What role did this result play in convincing you that your type system was sufficiently expressive? What were the main challenges that you had to overcome in developing that encoding and what were the main inspirations for that result?
Naoki: The encodability of the simply-typed λ-calculus with recursion in the deadlock-free fragment was a sort of minimal requirement for expressiveness. Since that property had already been shown for the original deadlock-free type system [2], I wanted to show that a similar level of expressive power was retained in the CONCUR 2006 type system.
There was also a more conceptual reason for considering such an encoding. Deadlock-freedom corresponds to the progress property of well-typed functional programs: evaluation does not get stuck. Thus, the encodability result shows that this progress property can be preserved by compilation from possibly parallel functional programs into the pi-calculus, which may be viewed as a CPS-style, lower-level language with concurrency primitives.
The main challenge was how to give a finite representation, within the type system, of the infinite chains of causal dependencies induced by recursion. As mentioned in the answer to the first question, we achieved this by combining the ideas of capability/obligation levels from [3] with a partial order on time tags from [2].
Luca: Your article gave a seminal contribution to the study of type systems for the pi-calculus that guarantee some desirable properties. Other examples of such contributions are, for instance, your paper with Davide Sangiorgi on a type system for lock-freedom or the paper by Yuxin Deng and Davide Sangiorgi on ensuring termination by typability amongst others. In hindsight, are there any relations amongst those contributions or ideas that underlie them and that can guide further developments in a systematic fashion?
Naoki: All three type systems you mentioned are related in that they control causal dependencies using natural numbers called “levels.” The type system for deadlock-freedom forbids cyclic dependencies, while the type systems for lock-freedom and termination forbid infinite chains of dependencies. The formulation of such reasoning through types, however, suffers from inherent limitations in expressive power.
To address this limitation, my paper with Davide Sangiorgi [7] suggested a new direction: combining syntactic typing rules with semantic ones. The latter can be discharged by resorting to model checkers, interactive theorem provers, or other verification tools, thereby complementing the limitations of type systems. I think this combination of type-based reasoning and semantic verification may provide a useful guide for further developments: types can capture common structural patterns, while semantic methods can handle cases that fall outside the reach of purely syntactic typing rules.
[7] Naoki Kobayashi, Davide Sangiorgi, A hybrid type system for lock-freedom of mobile processes. ACM Trans. Program. Lang. Syst. 32(5): 16:1-16:49 (2010)
Luca: Are there any problems that you left open in your award-winning article that you'd still love to see solved?
Naoki: I would still like to see at least two directions explored further. First, increasing the expressiveness of the type system by integrating the ideas of [4] and [5], mentioned above, would probably be necessary to make the approach practical. Second, since the type-based approach is inherently incomplete, finding a smooth integration with other methods, such as model checking and interactive theorem proving, remains an important open problem, as suggested in [6].
Luca: How did the results and the techniques you developed in your award-winning paper influence your subsequent research? Is there any result obtained by other researchers that builds on, or is related to, your work and that you like in particular?
Naoki: A key ingredient of our type systems for deadlock-freedom is the notion of obligations and capabilities. An obligation of a send or receive operation describes the need to perform that operation, while a capability describes a guarantee that the operation can succeed. For example, in a client-server model, a client has the capability to send a request successfully, while a server has an obligation to receive and handle the request. In lock-based mutual exclusion, a thread has the capability to eventually acquire a lock, and, after acquiring the lock, it has an obligation to eventually release the lock.
These dual notions of obligations and capabilities turned out to be useful in other contexts. For example, we adapted them for automated verification of security protocols [8]. Another line of work developed related ideas for more conventional concurrent programming languages. Leino et al. [9] applied related techniques to deadlock-freedom of channels and locks, and this line was further extended to monitors and condition variables by Hamin and Jacobs [10]. I found this line of work particularly interesting because it shows that similar ideas arise naturally also in a more conventional programming-language setting.
[8] Morten Dahl, Naoki Kobayashi, Yunde Sun, Hans Hüttel, Type-Based Automated Verification of Authenticity in Asymmetric Cryptographic Protocols. ATVA 2011: 75-89 [9] K. Rustan M. Leino, Peter Müller, Jan Smans, Deadlock-Free Channels and Locks. ESOP 2010: 407-426
[10] Jafar Hamin, Bart Jacobs, Deadlock-Free Monitors. ESOP 2018: 415-441
Luca: What are the research topics related to type systems that you find most interesting right now? What role do you think type systems will or should have, if any, in the era of coding agents based on GenAI?
Naoki: I think GenAI may change not only type systems, but also the focus of formal methods more broadly. Traditionally, programs have been written by humans, and therefore “lightweight formal methods” have played an important role. In that setting, it was important to keep program annotations minimal and to automate verification or bug finding as much as possible, even if this sometimes came at the cost of precision or completeness.
In the era of GenAI-based coding agents, however, the situation may change. If coding agents can also generate annotations such as types and loop invariants, then the burden of writing annotations may no longer be such a serious issue. As a result, verification methods that aim at strong correctness guarantees, rather than merely finding bugs or checking lightweight properties, may become more important.
In this respect, the CONCUR 2006 type system can be seen as a product of the former design philosophy: it emphasized automation, at some cost in precision. A possible future direction would be to move beyond such lightweight type systems, by incorporating dependent types or combining type systems with other methods such as model checking, aiming at more complete verification methods.
Luca: What advice would you give to a young researcher who is keen to start working on topics related to types for programming languages?

Naoki: As discussed above, GenAI is rapidly changing the landscape of PL research, and we are facing significant challenges in adapting to these changes and finding new research directions to explore. I think this is a very good opportunity for “AI-native” young researchers to play important roles. My advice would be to learn the classical foundations carefully, but at the same time not to be constrained by traditional assumptions about how programs are written and verified.

By Luca Aceto

As mentioned in a previous post, Naoki Kobayashi will receive one of the two CONCUR 2026 Test-of-Time Awards at CONCUR 2026. Naoki has kindly agreed to answer some questions of mine on his award-winning paper via email. I am delighted to post his answers below and hope you'll enjoy reading them as much as I did. Thanks, Naoki!

Luca: You receive the CONCUR ToT Award 2026 for your paper A New Type System for Deadlock-Free Processes, which appeared at CONCUR 2006. That article is the culmination of a series of contributions you gave on the development of type systems for variations on the pi-calculus that guarantee deadlock-freedom. Could you briefly explain to our readers how you came to study the question addressed in your award-winning article and how the main ideas in your CONCUR 2006 paper evolved over time? Which of the ideas and results in your paper did you find most pleasing, surprising or challenging?

Naoki: If I remember correctly, the idea of using types to ensure deadlock-freedom came up during discussions on the linear pi-calculus with Benjamin Pierce and David Turner [1]. Indeed, if one wants to ensure that a channel is really used exactly once, one also has to ensure that the process does not get stuck before using it. An initial result on type systems for deadlock-freedom was published in LICS 1997 [2].

After that, the type system was extended in two directions: enabling automated type inference and increasing expressiveness. These were somewhat conflicting goals, and the CONCUR 2006 paper achieved a balance between them. The core idea was as follows. To ensure deadlock-freedom, it is necessary to control dependencies among different channels. In [2], such dependencies were expressed using “time tags” and a possibly infinite partial order on them. The time tags were later replaced by natural numbers, called capability and obligation levels, to enable automated inference [3], but at the cost of expressive power. The CONCUR 2006 paper combined a restricted form of time tags with capability and obligation levels, thereby recovering much of the expressive power while retaining automated inference.

What I found most pleasing was precisely this balance: the paper showed that one could make the type system significantly more practical without completely giving up the conceptual elegance and expressiveness of the earlier formulation.

[1] Naoki Kobayashi, Benjamin C. Pierce, David N. Turner, Linearity and the Pi-Calculus. POPL 1996: 358-37
[2] Naoki Kobayashi, A Partially Deadlock-Free Typed Process Calculus. LICS 1997: 128-139
[3] Naoki Kobayashi, Type-based information flow analysis for the pi-calculus. Acta Informatica 42(4-5): 291-347 (2005)

Luca: The contribution in your article achieves a good trade-off between expressiveness of the type system and ease of implementing its associated type inference algorithm. Did you or any other researcher try to extend the range of examples that could be handled by a variation on your type system? Do you think that it would be worth doing so or have we hit the point of diminishing returns, where any advance would be very technical and hard to implement?

Naoki: With Elena Giachino and Cosimo Laneve [4], I indeed investigated such an extension. The system developed there can deal with infinite chains of dependencies more general than those handled in the CONCUR 2006 paper. It was, however, developed for value-passing CCS rather than the pi-calculus. Incorporating the idea of [4] into the pi-calculus setting remains future work.

Another possible direction would be to combine the approach with generic types [5], which can capture precise dependencies among a set of channels. Unfortunately, I did not have time to fully explore this direction.
As for whether it is worth pushing this line further, my feeling is that further general-purpose extensions may easily become technically involved and hard to implement. Perhaps a more promising direction would be to adapt the type system to real concurrent languages such as Go, and then see what kinds of extensions are most beneficial in practice.

[4] Elena Giachino, Naoki Kobayashi, Cosimo Laneve, Deadlock Analysis of Unbounded Process Networks. CONCUR 2014: 63-77

[5] Atsushi Igarashi, Naoki Kobayashi, A generic type system for the Pi-calculus. Theor. Comput. Sci. 311(1-3): 121-163 (2004)

Luca: Commendably, you supported the theoretical developments in your article with an implementation in TyPiCal. What role did the implementation work play in your research on type systems guaranteeing deadlock-freedom? Did the theoretical developments benefit from the implementation? Do you think that every proposal for a type system for some language ought to be accompanied by an implementation?

Naoki: TyPiCal was initially developed as a proof of concept for the type inference algorithm of [3]. At that time, the theory had already been fully developed, and the implementation was mainly used to convince readers that the algorithm indeed works in practice. In later extensions of TyPiCal, for the CONCUR 2006 paper and the work of [6], the implementation was also useful for checking the theories.

I think it is desirable for every type-system proposal to be accompanied by an implementation, although I would not say that it is absolutely necessary. An implementation is useful not only for checking the theory, but also for identifying limitations of the theory and suggesting possible directions for improvement.

[6] Naoki Kobayashi, Davide Sangiorgi, A Hybrid Type System for Lock-Freedom of Mobile Processes. CAV 2008: 80-93

Luca: In your paper, you showed, amongst other things, that the simply-typed λ-calculus with recursion could be encoded in the deadlock-free fragment of your calculus. What role did this result play in convincing you that your type system was sufficiently expressive? What were the main challenges that you had to overcome in developing that encoding and what were the main inspirations for that result?

Naoki: The encodability of the simply-typed λ-calculus with recursion in the deadlock-free fragment was a sort of minimal requirement for expressiveness. Since that property had already been shown for the original deadlock-free type system [2], I wanted to show that a similar level of expressive power was retained in the CONCUR 2006 type system.

There was also a more conceptual reason for considering such an encoding. Deadlock-freedom corresponds to the progress property of well-typed functional programs: evaluation does not get stuck. Thus, the encodability result shows that this progress property can be preserved by compilation from possibly parallel functional programs into the pi-calculus, which may be viewed as a CPS-style, lower-level language with concurrency primitives.

The main challenge was how to give a finite representation, within the type system, of the infinite chains of causal dependencies induced by recursion. As mentioned in the answer to the first question, we achieved this by combining the ideas of capability/obligation levels from [3] with a partial order on time tags from [2].

Luca: Your article gave a seminal contribution to the study of type systems for the pi-calculus that guarantee some desirable properties. Other examples of such contributions are, for instance, your paper with Davide Sangiorgi on a type system for lock-freedom or the paper by Yuxin Deng and Davide Sangiorgi on ensuring termination by typability amongst others. In hindsight, are there any relations amongst those contributions or ideas that underlie them and that can guide further developments in a systematic fashion?

Naoki: All three type systems you mentioned are related in that they control causal dependencies using natural numbers called “levels.” The type system for deadlock-freedom forbids cyclic dependencies, while the type systems for lock-freedom and termination forbid infinite chains of dependencies. The formulation of such reasoning through types, however, suffers from inherent limitations in expressive power.

To address this limitation, my paper with Davide Sangiorgi [7] suggested a new direction: combining syntactic typing rules with semantic ones. The latter can be discharged by resorting to model checkers, interactive theorem provers, or other verification tools, thereby complementing the limitations of type systems. I think this combination of type-based reasoning and semantic verification may provide a useful guide for further developments: types can capture common structural patterns, while semantic methods can handle cases that fall outside the reach of purely syntactic typing rules.

[7] Naoki Kobayashi, Davide Sangiorgi, A hybrid type system for lock-freedom of mobile processes. ACM Trans. Program. Lang. Syst. 32(5): 16:1-16:49 (2010)

Luca: Are there any problems that you left open in your award-winning article that you'd still love to see solved?

Naoki: I would still like to see at least two directions explored further. First, increasing the expressiveness of the type system by integrating the ideas of [4] and [5], mentioned above, would probably be necessary to make the approach practical. Second, since the type-based approach is inherently incomplete, finding a smooth integration with other methods, such as model checking and interactive theorem proving, remains an important open problem, as suggested in [6].

Luca: How did the results and the techniques you developed in your award-winning paper influence your subsequent research? Is there any result obtained by other researchers that builds on, or is related to, your work and that you like in particular?

Naoki: A key ingredient of our type systems for deadlock-freedom is the notion of obligations and capabilities. An obligation of a send or receive operation describes the need to perform that operation, while a capability describes a guarantee that the operation can succeed. For example, in a client-server model, a client has the capability to send a request successfully, while a server has an obligation to receive and handle the request. In lock-based mutual exclusion, a thread has the capability to eventually acquire a lock, and, after acquiring the lock, it has an obligation to eventually release the lock.

These dual notions of obligations and capabilities turned out to be useful in other contexts. For example, we adapted them for automated verification of security protocols [8]. Another line of work developed related ideas for more conventional concurrent programming languages. Leino et al. [9] applied related techniques to deadlock-freedom of channels and locks, and this line was further extended to monitors and condition variables by Hamin and Jacobs [10]. I found this line of work particularly interesting because it shows that similar ideas arise naturally also in a more conventional programming-language setting.

[8] Morten Dahl, Naoki Kobayashi, Yunde Sun, Hans Hüttel, Type-Based Automated Verification of Authenticity in Asymmetric Cryptographic Protocols. ATVA 2011: 75-89

[9] K. Rustan M. Leino, Peter Müller, Jan Smans, Deadlock-Free Channels and Locks. ESOP 2010: 407-426
[10] Jafar Hamin, Bart Jacobs, Deadlock-Free Monitors. ESOP 2018: 415-441

Luca: What are the research topics related to type systems that you find most interesting right now? What role do you think type systems will or should have, if any, in the era of coding agents based on GenAI?

Naoki: I think GenAI may change not only type systems, but also the focus of formal methods more broadly. Traditionally, programs have been written by humans, and therefore “lightweight formal methods” have played an important role. In that setting, it was important to keep program annotations minimal and to automate verification or bug finding as much as possible, even if this sometimes came at the cost of precision or completeness.

In the era of GenAI-based coding agents, however, the situation may change. If coding agents can also generate annotations such as types and loop invariants, then the burden of writing annotations may no longer be such a serious issue. As a result, verification methods that aim at strong correctness guarantees, rather than merely finding bugs or checking lightweight properties, may become more important.

In this respect, the CONCUR 2006 type system can be seen as a product of the former design philosophy: it emphasized automation, at some cost in precision. A possible future direction would be to move beyond such lightweight type systems, by incorporating dependent types or combining type systems with other methods such as model checking, aiming at more complete verification methods.

Luca: What advice would you give to a young researcher who is keen to start working on topics related to types for programming languages?

Naoki: As discussed above, GenAI is rapidly changing the landscape of PL research, and we are facing significant challenges in adapting to these changes and finding new research directions to explore. I think this is a very good opportunity for “AI-native” young researchers to play important roles. My advice would be to learn the classical foundations carefully, but at the same time not to be constrained by traditional assumptions about how programs are written and verified.

By Luca Aceto

Thursday, May 21 2026, 10:31

Linear Functional Testing with General Loadings in Sparse Regression: Separation Rates and Computational Barriers

Authors: Jie Xie, Dongming Huang

We study the problem of testing $H_0: ξ^\topβ=t_0$ in high-dimensional sparse linear regression with Gaussian random design and unknown design covariance. The loading vector $ξ$ is arbitrary, and the exact sparsity level $k$ is unknown but bounded by a known value $k_u$. Tests are required to control Type I error uniformly over the $k_u$-sparse null, while power is evaluated against $k$-sparse alternatives. We construct a computationally efficient mixed test that gives an upper bound on the adaptive separation distance and establish an information-theoretic lower bound calibrated to the magnitude profile of $ξ$. In the ultra-sparse regime $k_u\lesssim \sqrt n/\log p$, these bounds characterize the adaptive separation rate up to logarithmic factors for arbitrary $ξ$. In the moderately sparse regime $\sqrt n/\log p\ll k_u\lesssim n/\log p$, these bounds match for several classes of loading vectors but may differ in general. In this regime, we further prove a low-degree lower bound that matches the upper bound up to logarithmic factors. This provides evidence that improving on the rate of the mixed test, if statistically possible, may be computationally hard. For flat sparse loadings, we complement this evidence with a polynomial-time reduction from sparse CCA. Finally, we examine how information about the design covariance affects the adaptive separation rate in two settings. Under a sparse signed-spiked covariance model, the information-theoretic lower bound is attainable up to logarithmic factors by a computationally inefficient procedure, while the low-degree lower bound and sparse-CCA reduction continue to apply, providing evidence for a statistical-computational gap. When the design covariance is known and diagonal, the adaptive separation rate takes the same form as in the ultra-sparse regime.

Authors: Jie Xie, Dongming Huang

We study the problem of testing $H_0: ξ^\topβ=t_0$ in high-dimensional sparse linear regression with Gaussian random design and unknown design covariance. The loading vector $ξ$ is arbitrary, and the exact sparsity level $k$ is unknown but bounded by a known value $k_u$. Tests are required to control Type I error uniformly over the $k_u$-sparse null, while power is evaluated against $k$-sparse alternatives. We construct a computationally efficient mixed test that gives an upper bound on the adaptive separation distance and establish an information-theoretic lower bound calibrated to the magnitude profile of $ξ$. In the ultra-sparse regime $k_u\lesssim \sqrt n/\log p$, these bounds characterize the adaptive separation rate up to logarithmic factors for arbitrary $ξ$. In the moderately sparse regime $\sqrt n/\log p\ll k_u\lesssim n/\log p$, these bounds match for several classes of loading vectors but may differ in general. In this regime, we further prove a low-degree lower bound that matches the upper bound up to logarithmic factors. This provides evidence that improving on the rate of the mixed test, if statistically possible, may be computationally hard. For flat sparse loadings, we complement this evidence with a polynomial-time reduction from sparse CCA. Finally, we examine how information about the design covariance affects the adaptive separation rate in two settings. Under a sparse signed-spiked covariance model, the information-theoretic lower bound is attainable up to logarithmic factors by a computationally inefficient procedure, while the low-degree lower bound and sparse-CCA reduction continue to apply, providing evidence for a statistical-computational gap. When the design covariance is known and diagonal, the adaptive separation rate takes the same form as in the ultra-sparse regime.

Thursday, May 21 2026, 00:00

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming

Authors: Victor Lagerkvist, Johanna Groven, Leif Eriksson

The region connection calculus ($RCC$) and Allen's interval algebra ($IA$) are two well-known NP-hard spatial-temporal qualitative reasoning problems. They are solvable in $2^{O(n \log n)}$ time, where $n$ is the number of variables, and $IA$ is additionally known to be solvable in $o(n)^n$ time. However, no improvement over exhaustive search is known for $RCC$, and if they are also solvable in single exponential time $2^{O(n)}$ is unknown. We investigate multiple avenues towards reaching such bounds. First, we show that branching is insufficient since there are too many non-redundant constraints. Concretely, we classify the maximum number of non-redundant constraints in $RCC$ and $IA$. Algorithmically, we make two significant contributions based on dynamic programming (DP). The first algorithm runs in $4^n$ time and is applicable to a non-trivial, NP-hard fragment of $IA$, which includes the well-known interval graph sandwich problem of Golumbic and Shamir (1993). For the richer $RCC$ problem with 8 basic relations we use a more sophisticated approach which asymptotically matches the $o(n)^n$ bound for $IA$.

Authors: Victor Lagerkvist, Johanna Groven, Leif Eriksson

The region connection calculus ($RCC$) and Allen's interval algebra ($IA$) are two well-known NP-hard spatial-temporal qualitative reasoning problems. They are solvable in $2^{O(n \log n)}$ time, where $n$ is the number of variables, and $IA$ is additionally known to be solvable in $o(n)^n$ time. However, no improvement over exhaustive search is known for $RCC$, and if they are also solvable in single exponential time $2^{O(n)}$ is unknown. We investigate multiple avenues towards reaching such bounds. First, we show that branching is insufficient since there are too many non-redundant constraints. Concretely, we classify the maximum number of non-redundant constraints in $RCC$ and $IA$. Algorithmically, we make two significant contributions based on dynamic programming (DP). The first algorithm runs in $4^n$ time and is applicable to a non-trivial, NP-hard fragment of $IA$, which includes the well-known interval graph sandwich problem of Golumbic and Shamir (1993). For the richer $RCC$ problem with 8 basic relations we use a more sophisticated approach which asymptotically matches the $o(n)^n$ bound for $IA$.

Thursday, May 21 2026, 00:00

Resource bounded Kučera-Gács Theorems

Authors: Satyadev Nandakumar, Akhil S, Chandra Shekhar Tiwari

The Kučera--Gács theorem is a fundamental result in algorithmic randomness. It states that every infinite sequence $X$ is Turing reducible to a Martin-Löf random $R$. This paper studies resource-bounded analogues of the Kučera-Gács Theorem, at the resource bounds of polynomial-time and finite-state computation. We prove a {quasi-polynomial-time}{ Kučera-Gács Theorem}, showing that every infinite sequence $X$ is quasi-polynomial-time reducible to a \emph{polynomial-time random} sequence $R$. We also show that for any $X$, the oracle use of $R$ is $n+o(n)$ bits for obtaining the first $n$ bits of $X$. We then study the relationship between compressibility and Turing reductions, in the polynomial-time setting. We establish that $ρ^-_{\mathsf{poly}}(X) = K_{poly}(X)$, demonstrating that the lower polynomial-time Turing decompression ratio is precisely characterized by the polynomial-time Kolmogorov complexity rate. We note that this characterization fails for the polynomial-time dimension if one-way functions exist, resolving an open problem from Doty's work. We use these results to strengthen the {quasi-polynomial-time}{ Kučera-Gács Theorem}. We show that every infinite sequence $X$ is quasi-polynomial-time reducible to a {polynomial-time random} sequence $R$, where the lower oracle use rate of the reduction is less than ${K}_{poly}(X)$. We also show that any sequence extracted from the (even larger) set of \emph{normal sequences} by a finite-state reduction must have a convergent asymptotic frequency for its symbols. Since sequences lacking this invariant property exist, they cannot be finite-state reduced from any normal sequence. Hence we show that the Kučera-Gács theorem \emph{fails} for finite-state reductions.

Authors: Satyadev Nandakumar, Akhil S, Chandra Shekhar Tiwari

The Kučera--Gács theorem is a fundamental result in algorithmic randomness. It states that every infinite sequence $X$ is Turing reducible to a Martin-Löf random $R$. This paper studies resource-bounded analogues of the Kučera-Gács Theorem, at the resource bounds of polynomial-time and finite-state computation. We prove a {quasi-polynomial-time}{ Kučera-Gács Theorem}, showing that every infinite sequence $X$ is quasi-polynomial-time reducible to a \emph{polynomial-time random} sequence $R$. We also show that for any $X$, the oracle use of $R$ is $n+o(n)$ bits for obtaining the first $n$ bits of $X$. We then study the relationship between compressibility and Turing reductions, in the polynomial-time setting. We establish that $ρ^-_{\mathsf{poly}}(X) = K_{poly}(X)$, demonstrating that the lower polynomial-time Turing decompression ratio is precisely characterized by the polynomial-time Kolmogorov complexity rate. We note that this characterization fails for the polynomial-time dimension if one-way functions exist, resolving an open problem from Doty's work. We use these results to strengthen the {quasi-polynomial-time}{ Kučera-Gács Theorem}. We show that every infinite sequence $X$ is quasi-polynomial-time reducible to a {polynomial-time random} sequence $R$, where the lower oracle use rate of the reduction is less than ${K}_{poly}(X)$. We also show that any sequence extracted from the (even larger) set of \emph{normal sequences} by a finite-state reduction must have a convergent asymptotic frequency for its symbols. Since sequences lacking this invariant property exist, they cannot be finite-state reduced from any normal sequence. Hence we show that the Kučera-Gács theorem \emph{fails} for finite-state reductions.

Thursday, May 21 2026, 00:00

Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals

Authors: Ilias Diakonikolas, Giannis Iakovidis, Mingchen Ma

We study the task of agnostic learning of multiclass linear classifiers under the Gaussian distribution. Given labeled examples $(x, y)$ from a distribution over $\mathbb{R}^d \times [k]$, with Gaussian $x$-marginal, the goal is to output a hypothesis whose error is comparable to that of the best $k$-class linear classifier. While the binary case $k=2$ has a well-developed algorithmic theory, much less is known for $k \ge 3$. Even for $k=3$, prior robust algorithms incur exponential dependence on the inverse of the desired accuracy in both complexity and representation size. In this work, we develop new structural results for multiclass linear classifiers and use them to design fully polynomial-time robust learners with dimension-independent error guarantees. Our first result shows that the standard multiclass perceptron algorithm requires super-polynomially many samples and updates, even with clean labels and Gaussian marginals, revealing a basic obstruction absent in the binary case. Our main positive result is a pairwise improper-learning framework which yields an efficient learner with error $\widetilde O(k^{3/2}\sqrt{\mathrm{opt}})+ε$ for general $k$. Additionally, we develop a sharper localization-based framework which leads to error $O(\mathrm{opt})+ε$ for $k=3$, and error $\mathrm{poly}(k)\mathrm{opt}+ε$ for geometrically regular $k$-class linear classifiers.

Authors: Ilias Diakonikolas, Giannis Iakovidis, Mingchen Ma

We study the task of agnostic learning of multiclass linear classifiers under the Gaussian distribution. Given labeled examples $(x, y)$ from a distribution over $\mathbb{R}^d \times [k]$, with Gaussian $x$-marginal, the goal is to output a hypothesis whose error is comparable to that of the best $k$-class linear classifier. While the binary case $k=2$ has a well-developed algorithmic theory, much less is known for $k \ge 3$. Even for $k=3$, prior robust algorithms incur exponential dependence on the inverse of the desired accuracy in both complexity and representation size. In this work, we develop new structural results for multiclass linear classifiers and use them to design fully polynomial-time robust learners with dimension-independent error guarantees. Our first result shows that the standard multiclass perceptron algorithm requires super-polynomially many samples and updates, even with clean labels and Gaussian marginals, revealing a basic obstruction absent in the binary case. Our main positive result is a pairwise improper-learning framework which yields an efficient learner with error $\widetilde O(k^{3/2}\sqrt{\mathrm{opt}})+ε$ for general $k$. Additionally, we develop a sharper localization-based framework which leads to error $O(\mathrm{opt})+ε$ for $k=3$, and error $\mathrm{poly}(k)\mathrm{opt}+ε$ for geometrically regular $k$-class linear classifiers.

Thursday, May 21 2026, 00:00

Distributed Stochastic Graph Algorithms

Authors: Keren Censor-Hillel, Aditi Dudeja, George Giakkoupis

We study stochastic graph optimization problems in a novel distributed setting. As in the standard centralized setting, a random subgraph $G^*$ of a known base graph $G$ is realized by including each edge $e$ independently with a known probability $p_e$, and we must solve an optimization problem on $G^*$ despite uncertainty about its edges. In the standard setting, to cope with this uncertainty, the algorithm can query any edge of $G$ to learn if the edge exists in $G^*$, and its complexity is the number of queried edges. The distributed setting incorporates uncertainty in a natural manner, by having each vertex know only about its own edges in $G^*$ (and only communicate over them), and the complexity is measured by the number of synchronous communication rounds. We establish that distributed stochastic algorithms can be drastically faster than their non-stochastic counterparts and overcome known lower bounds, by showing fast distributed approximation algorithms for maximum matching, minimum vertex cover, and minimum dominating set.

Authors: Keren Censor-Hillel, Aditi Dudeja, George Giakkoupis

We study stochastic graph optimization problems in a novel distributed setting. As in the standard centralized setting, a random subgraph $G^*$ of a known base graph $G$ is realized by including each edge $e$ independently with a known probability $p_e$, and we must solve an optimization problem on $G^*$ despite uncertainty about its edges. In the standard setting, to cope with this uncertainty, the algorithm can query any edge of $G$ to learn if the edge exists in $G^*$, and its complexity is the number of queried edges. The distributed setting incorporates uncertainty in a natural manner, by having each vertex know only about its own edges in $G^*$ (and only communicate over them), and the complexity is measured by the number of synchronous communication rounds. We establish that distributed stochastic algorithms can be drastically faster than their non-stochastic counterparts and overcome known lower bounds, by showing fast distributed approximation algorithms for maximum matching, minimum vertex cover, and minimum dominating set.

Thursday, May 21 2026, 00:00

Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification

Authors: Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis

Data valuation, the task of quantifying the contribution of individual data points to model performance, has emerged as a fundamental challenge in machine learning. Game-theoretic approaches, such as the Banzhaf value, offer principled frameworks for fair data valuation; however, they suffer from exponential computational complexity. We address this challenge by developing efficient algorithms specifically tailored for computing Banzhaf values in $k$-nearest neighbor ($k$NN) classifiers. We first establish the theoretical hardness of the problem by proving that it is \#P-hard. Despite this intractability, we exploit the locality properties of $k$NN classifiers to develop practical exact algorithms. Our main contribution is a dynamic programming framework that achieves significant computational improvements: we present a pseudo-polynomial algorithm with $O(Wkn^2)$ time complexity for weighted $k$NN classifiers, where $W$ is the maximum sum of top-$k$ weights, and a specialized algorithm for unweighted $k$NN that achieves $O(nk^2)$ time complexity, that is, linear in the number of data points. We also offer efficient Monte Carlo estimation methods. Extensive experiments on real-world datasets demonstrate the practical efficiency of our approach and its effectiveness in data valuation applications.

Authors: Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis

Data valuation, the task of quantifying the contribution of individual data points to model performance, has emerged as a fundamental challenge in machine learning. Game-theoretic approaches, such as the Banzhaf value, offer principled frameworks for fair data valuation; however, they suffer from exponential computational complexity. We address this challenge by developing efficient algorithms specifically tailored for computing Banzhaf values in $k$-nearest neighbor ($k$NN) classifiers. We first establish the theoretical hardness of the problem by proving that it is \#P-hard. Despite this intractability, we exploit the locality properties of $k$NN classifiers to develop practical exact algorithms. Our main contribution is a dynamic programming framework that achieves significant computational improvements: we present a pseudo-polynomial algorithm with $O(Wkn^2)$ time complexity for weighted $k$NN classifiers, where $W$ is the maximum sum of top-$k$ weights, and a specialized algorithm for unweighted $k$NN that achieves $O(nk^2)$ time complexity, that is, linear in the number of data points. We also offer efficient Monte Carlo estimation methods. Extensive experiments on real-world datasets demonstrate the practical efficiency of our approach and its effectiveness in data valuation applications.

Thursday, May 21 2026, 00:00

Treewidth of the $n \times n$ toroidal grid

Authors: Tatsuya Gima, Hiraku Morimoto, Yuto Okada, Yota Otachi

In this paper, we show that the treewidth of the $n \times n$ toroidal grid is $2n-1$ for all $n \ge 5$. This closes the gap between the previously known upper bound of $2n-1$ (Ellis and Warren, DAM 2008) and the lower bound of $2n-2$ (Kiyomi, Okamoto, and Otachi, DAM 2016). To establish the matching lower bound, we construct a bramble of maximum order by utilizing maximum components obtained after removing $2n-1$ vertices. Our construction relies on the vertex-isoperimetric properties of the infinite grid to establish tight lower bounds on neighborhood sizes, combined with a careful analysis of balls of radius $n/2-1$ and their boundaries to overcome structural obstructions when $n$ is even.

Authors: Tatsuya Gima, Hiraku Morimoto, Yuto Okada, Yota Otachi

In this paper, we show that the treewidth of the $n \times n$ toroidal grid is $2n-1$ for all $n \ge 5$. This closes the gap between the previously known upper bound of $2n-1$ (Ellis and Warren, DAM 2008) and the lower bound of $2n-2$ (Kiyomi, Okamoto, and Otachi, DAM 2016). To establish the matching lower bound, we construct a bramble of maximum order by utilizing maximum components obtained after removing $2n-1$ vertices. Our construction relies on the vertex-isoperimetric properties of the infinite grid to establish tight lower bounds on neighborhood sizes, combined with a careful analysis of balls of radius $n/2-1$ and their boundaries to overcome structural obstructions when $n$ is even.

Thursday, May 21 2026, 00:00

Creating Robust and Fair Graph Structures for Connectivity and Clustering

Authors: Kushagra Chatterjee

Graph algorithms are central to large-scale applications such as navigation systems, social networks, and data analysis platforms. This thesis studies two important challenges in such systems: robustness to failures and fairness in clustering outcomes. In the first part, we investigate fault-tolerant reachability preservers in directed graphs. We present the first non-trivial constructions of dual fault-tolerant pairwise reachability preservers that remain resilient to two edge or vertex failures, achieving a sparse construction of size $O(n^{4/3}|\mathcal{P}|^{1/3})$. In the second part, we study fair clustering algorithms that ensure balanced representation of protected groups. We develop approximation algorithms for fair consensus clustering and introduce the framework of closest fair clustering, establishing hardness results and efficient algorithms for multi-group settings. Building on this framework, we obtain improved guarantees for fair correlation clustering and design the first streaming algorithm for fair consensus clustering using only logarithmic memory. Together, these results contribute toward the design of graph algorithms that are both robust and socially responsible.

Authors: Kushagra Chatterjee

Graph algorithms are central to large-scale applications such as navigation systems, social networks, and data analysis platforms. This thesis studies two important challenges in such systems: robustness to failures and fairness in clustering outcomes. In the first part, we investigate fault-tolerant reachability preservers in directed graphs. We present the first non-trivial constructions of dual fault-tolerant pairwise reachability preservers that remain resilient to two edge or vertex failures, achieving a sparse construction of size $O(n^{4/3}|\mathcal{P}|^{1/3})$. In the second part, we study fair clustering algorithms that ensure balanced representation of protected groups. We develop approximation algorithms for fair consensus clustering and introduce the framework of closest fair clustering, establishing hardness results and efficient algorithms for multi-group settings. Building on this framework, we obtain improved guarantees for fair correlation clustering and design the first streaming algorithm for fair consensus clustering using only logarithmic memory. Together, these results contribute toward the design of graph algorithms that are both robust and socially responsible.

Thursday, May 21 2026, 00:00

Circuits of Quantum Hashing and Quantum Fourier Transform for a Cactus as a Qubit Connectivity Graph

Authors: Kamil Khadiev, Ilnur Valeev

We present a quantum circuit implementation of the quantum hashing algorithm (quantum fingerprinting) for a quantum device with restrictions on the application of two-qubit gates by a qubit connectivity graph. We present an optimization technique for the shallow circuit for quantum hashing in the case of a cactus as a qubit connectivity graph. The algorithm has $O(n^3)$ complexity to build the circuit, where $n$ is the number of qubits and $m$ is the number of connections (edges) in the graph. It is improvement compared to the existing exponential-time algorithm in the case of arbitrary graphs. The algorithm uses solution for the shortest non-simple 1-covering path problem as a subroutine. We present an $O(n^3)$-time solution for this graph-theory problem in the case of a cactus. This result can be interesting independently. The algorithm also used for improving of the quantum circuit for Quantum Fourier Transform.

Authors: Kamil Khadiev, Ilnur Valeev

We present a quantum circuit implementation of the quantum hashing algorithm (quantum fingerprinting) for a quantum device with restrictions on the application of two-qubit gates by a qubit connectivity graph. We present an optimization technique for the shallow circuit for quantum hashing in the case of a cactus as a qubit connectivity graph. The algorithm has $O(n^3)$ complexity to build the circuit, where $n$ is the number of qubits and $m$ is the number of connections (edges) in the graph. It is improvement compared to the existing exponential-time algorithm in the case of arbitrary graphs. The algorithm uses solution for the shortest non-simple 1-covering path problem as a subroutine. We present an $O(n^3)$-time solution for this graph-theory problem in the case of a cactus. This result can be interesting independently. The algorithm also used for improving of the quantum circuit for Quantum Fourier Transform.

Thursday, May 21 2026, 00:00

An $O(n^5)$-Time Algorithm for Optimal Broadcast Domination

Authors: Kleitos Papadopoulos

Broadcast domination assigns a nonnegative integer power to every vertex of a graph so that every vertex is within the assigned power of some broadcasting vertex, and the objective is to minimize the sum of the powers. Heggernes and Lokshtanov proved that the problem is polynomial-time solvable on arbitrary connected unweighted graphs by showing that some optimal efficient broadcast has a domination graph that is a path or a cycle, and by reducing the general case to an $O(n^6)$-time algorithm. This paper gives an efficient algorithm of the path-case. Instead of building one auxiliary acyclic graph for every possible left endpoint vertex, we build a single directed acyclic graph whose states are oriented broadcast balls together with their two possible residual sides. The resulting path-case algorithm runs in $O(n^3)$ time and $O(n^3)$ space on an $n$-vertex graph. Combining this routine with the same peel-one-ball reduction of Heggernes and Lokshtanov yields an exact $O(n^5)$-time algorithm for optimal broadcast domination on arbitrary connected unweighted graphs. This resolves the quintic-time conjecture for general graphs attributed to Heggernes and Sæther and recorded in subsequent surveys of broadcast domination.

Authors: Kleitos Papadopoulos

Broadcast domination assigns a nonnegative integer power to every vertex of a graph so that every vertex is within the assigned power of some broadcasting vertex, and the objective is to minimize the sum of the powers. Heggernes and Lokshtanov proved that the problem is polynomial-time solvable on arbitrary connected unweighted graphs by showing that some optimal efficient broadcast has a domination graph that is a path or a cycle, and by reducing the general case to an $O(n^6)$-time algorithm. This paper gives an efficient algorithm of the path-case. Instead of building one auxiliary acyclic graph for every possible left endpoint vertex, we build a single directed acyclic graph whose states are oriented broadcast balls together with their two possible residual sides. The resulting path-case algorithm runs in $O(n^3)$ time and $O(n^3)$ space on an $n$-vertex graph. Combining this routine with the same peel-one-ball reduction of Heggernes and Lokshtanov yields an exact $O(n^5)$-time algorithm for optimal broadcast domination on arbitrary connected unweighted graphs. This resolves the quintic-time conjecture for general graphs attributed to Heggernes and Sæther and recorded in subsequent surveys of broadcast domination.

Thursday, May 21 2026, 00:00

Amazing: Erdős’ Unit Distance Problem was Disproved! It was achieved by AI!

from Gil Kalai

Paul Erdős’s, in his 1946 paper published in the American Mathematical Monthly, posed two general questions about the distribution of distances determined by a finite set of points in a metric space. 1. Unit Distance Problem: At most how many … Continue reading →

Paul Erdős’s, in his 1946 paper published in the American Mathematical Monthly, posed two general questions about the distribution of distances determined by a finite set of points in a metric space.

1. Unit Distance Problem: At most how many times can the same distance (say, distance 1) occur among a set of n points?

2. Distinct Distances Problem: What is the minimum number of distinct distances determined by a set of n points?

Erdős conjectured that in the plane the number of unit distances determined by n points is at most $n^{1+c/loglog n}$ , for a positive constant c, but the best known upper bound, due to Spencer, Szemeredi, and Trotter is only $O(n^{4/3})$ .

As for the Distinct Distances Problem, the order of magnitude of the conjectured minimum is $n/\sqrt{log n}$ . In 2010 a sensational paper of Guth and Katz presents a proof of an almost tight lower bound of the order of $n/log n.$ Janos Pach wrote about it in this 2010 post. See also this post from 2008, that explains (among other things) the proof for the upper bound.

I have just learned that an internal model of OpenAI have very recently disproved Erdős’ conjecture for the unit distance problem and found an example with more than $n^{1+\epsilon}$ unit distances. This is truly amazing. The construction relies on algebraic number theory.

Here is Open AI announcement and technical paper.

The proof is presented, explained and discussed in the paper Remarks on the disproof of the unit distance conjecture by Alon, Bloom, Gowers, Litt, Sawin, Shankar,Tsimerman, Wang, and Matchett Wood. (I learned about it from an answer to an MO question on the topic of mathematics and AI.)

Like the computer-based proof of the four color theorem in 1976 by Appel and Haken, this may well be a scientific landmark whose importance goes beyond combinatorics and beyond mathematics. I will add a link to the Open AI document when I will have it. (Done.)

There is also a short Open AI video where the result is presented by Tim Gowers and by four members of the team, Lijie Chen, Mark Sellke, Mehtaab Sawhney, and Sebastien (Seb) Bubeck.

Update: Will Sawin proved a lower bound of $n^{1.014}$

By Gil Kalai

Wednesday, May 20 2026, 23:01

Range Avoidance

from Computational Complexity

Let $f$ be a function mapping binary strings of length $m$ to strings of length $n$ with $n>m$. Since there are more strings of length $n$ than $m$, $f$ is not onto. Can you find a string not in the range? This is known as the range avoidance problems, or AVOID for short

Let's do an example. Consider $f$ that outputs an undirected graph on $n$ nodes and takes as input:

$n$
A set $S$ of $k$ vertices $v_1,\ldots,v_k$
For each $i$ and $j$, $i<j$, where at least one of $i$ and $j$ are not in $S$, whether or not there is an edge between $i$ and $j$.
A bit $b$

If $b=1$ output the graph $G$ which consists of the given edges plus a clique on $S$. If $b=0$ the same but an independent set on $S$.
For an appropriate choice of $k$, about $2 \log n$, the output of $f$ is longer than the input. Any graph not in the range is a Ramsey graph, i.e., no clique or independent set of size $k$.
You can use AVOID to capture other probabilistic method constructions, high time-bounded Kolmogorov strings, Boolean functions with high circuit complexity, two-source extractors, rigid matrices, error-correcting codes and more.
AVOID started as the problem 1-Empty in a paper by Robert Kleinberg, Oliver Korten, Daniel Mitropolsky and Christos Papadimitriou as an example of a total function problem higher up the polynomial-time hierarchy as verifying that a string not in the range is a co-NP question. Korten made the connection to probabilistic constructions. Hanlin Ren, Rahul Santhanam and Zhikun Wang popularized the problem and gave AVOID its current name. I learned about AVOID talking about the problem with Rahul and his students during my time at Oxford.

You can solve AVOID randomly using an NP oracle, at least half the strings are not in the range, and you can check that a string is not in the range in co-NP. Whether you can solve AVOID deterministically with an NP oracle remains open. Korten showed that that problem is equivalent to circuit lower bounds for ENP.

Surendra Ghentiyala, Zeyong Li and Noah Stephens-Davidowitz show that any decision problem that reduces to AVOID sits in AM ∩ co-AM which strongly suggests AVOID is not NP-hard.

See Korten's BEATCS survey for much more on the AVOID problem.

By Lance Fortnow

Let $f$ be a function mapping binary strings of length $m$ to strings of length $n$ with $n>m$. Since there are more strings of length $n$ than $m$, $f$ is not onto. Can you find a string not in the range? This is known as the range avoidance problems, or AVOID for short

Let's do an example. Consider $f$ that outputs an undirected graph on $n$ nodes and takes as input:

$n$
A set $S$ of $k$ vertices $v_1,\ldots,v_k$
For each $i$ and $j$, $i<j$, where at least one of $i$ and $j$ are not in $S$, whether or not there is an edge between $i$ and $j$.
A bit $b$

If $b=1$ output the graph $G$ which consists of the given edges plus a clique on $S$. If $b=0$ the same but an independent set on $S$.

For an appropriate choice of $k$, about $2 \log n$, the output of $f$ is longer than the input. Any graph not in the range is a Ramsey graph, i.e., no clique or independent set of size $k$.

You can use AVOID to capture other probabilistic method constructions, high time-bounded Kolmogorov strings, Boolean functions with high circuit complexity, two-source extractors, rigid matrices, error-correcting codes and more.

AVOID started as the problem 1-Empty in a paper by Robert Kleinberg, Oliver Korten, Daniel Mitropolsky and Christos Papadimitriou as an example of a total function problem higher up the polynomial-time hierarchy as verifying that a string not in the range is a co-NP question. Korten made the connection to probabilistic constructions. Hanlin Ren, Rahul Santhanam and Zhikun Wang popularized the problem and gave AVOID its current name. I learned about AVOID talking about the problem with Rahul and his students during my time at Oxford.

You can solve AVOID randomly using an NP oracle, at least half the strings are not in the range, and you can check that a string is not in the range in co-NP. Whether you can solve AVOID deterministically with an NP oracle remains open. Korten showed that that problem is equivalent to circuit lower bounds for E^NP.

Surendra Ghentiyala, Zeyong Li and Noah Stephens-Davidowitz show that any decision problem that reduces to AVOID sits in AM ∩ co-AM which strongly suggests AVOID is not NP-hard.

See Korten's BEATCS survey for much more on the AVOID problem.

By Lance Fortnow

Wednesday, May 20 2026, 17:49

Individual Experience vs. The Cochrane Review

from Ben Recht

On my decade-long exploration seeking a scientific language for singular evidence.

I had a bit of a throwaway line in the last post about how maximizing the welfare of populations requires the erasure of individuals. You might ask why? Individuals are units in a broader population. A population is a group of individuals. Improving the welfare at scale must improve the welfare of the units.

Except we all know this isn’t true. Maximizing averages doesn’t say anything about the outcomes of any particular individual. In fact, decisions that maximize averages often harm some of the individuals in the total sum. Individuals in a community always have some shared interests, but they have plenty of disparate interests too. Which interests are maximized is a political decision that necessarily leaves other interests neglected. Our metrics and measures can have broad societal value while still making many unhappy.

And how should those individuals make decisions about their own lives? You may be able to convince yourself that Mathematical Rationality makes sense for a bureaucratic state or company. However, it’s much harder to make the case for being a mathematically rational individual.1 Quantification, abstraction, hierarchy, and statistics can help organize and steer decision making at scale. But if one of the core goals of quantification is legibility for intersubjectivity, why do you need numbers to make sense of your personal experience? Why is it useful to see yourself like a state?

Nothing motivates my research more than this tension between the population and the individual. It’s been my main focus since 2020.2 But getting traction on these topics has been an uphill battle. Try telling someone in the human-facing sciences that you want to study the epistemology of case studies. It’s so easy to fall into the cracks of crankhood.

Now, of course, scientists are incapable of seeing the pure irrationality of science. Blindly applying population results to individuals requires a lot of faith. We have formal scientific language to understand population averages. This language is incoherent when directed back towards individuals. Take our gold standard of causal inference, the randomized controlled experiment. These trials can estimate the fraction of people in an experimental cohort who would benefit from taking a drug. But let’s say you do a trial with 600 people and find that 20% of the control group has a bad outcome, and 10% of the treatment group has a bad outcome.3 What does this say about my outcome? Unfortunately, that result alone says nothing. We’d like to argue that the intervention reduces my risk by a factor of 2. But what even is individual risk?

Despite this bizarre inability to really say anything about individual benefit, when you try to come up with a non-statistical, non-quantized language to say precise things about people, you are relegated to the bucket of pseudoscience or, if you can bench enough, bro-science. Anecdotes are not data. Your miracle cure is always a fluke. Your personal experience is trumped by this impenetrable 500-page systematic review. Anyone who disagrees with the consensus of experts is being an irrational contrarian.

However, a lot of practices people find beneficial are immune to the postmodern lens of the randomized trial. It’s really hard to do RCTs on organ transplantation. You can’t do RCTs for physical therapy. You certainly can’t do them for massage or chiropractic. It’s hilarious that we have convinced ourselves that we can do this for psychology, despite decades of embarrassing “scientific” failures. And when you start looking at “sports science,” you realize how silly it is to try to put a scientific corset on all of human experience. No randomized trial explains Victor Wembanyama.

I could pick on more than just the RCT. Individuals don’t exist in the calculus of rationality. None of the pillars of mathematical rationality I talk about in The Irrational Decision make much sense for individual people. I could give similar spiels about game theory, statistical prediction, or optimization.

Optimization, in particular, is tough to grapple with. I got a lot of questions about personal optimization in the conversations about my book. Many people find it useful to think about their lives as a collection of optimization problems. If you want to strive for the best, that means some number must go up, right?

Don’t get me wrong, I love optimizing too! Do I obsess about my home coffee setup, my exercise program, my writing schedule? You bet I do. Is that bad? Does that mean I’m just a cog in the capitalist machine? These questions form the basis of a conversation worth having.

Now, here’s an annoying paradox. If we want a language to talk about individual experience, it has to have some element of intersubjectivity. This is where the quantification trap comes in. The mimetic power of the quantification trap means that a shared language for discussing individual experience is always at risk of being contaminated by scientific quantification. But it doesn’t have to. Most people share their experiences without numbers and charts. We obviously share experience through art, music, and literature. These are all shared languages, too.

For the next bit on this blog, I want to find language to talk to each other about individual experiences. I want to write about this weird tension between the quantification trap and the individual. People figure out how to do amazing things without consulting the scientific literature all the time. How can we talk about commonalities without reducing them to numbers or statistics? I initially thought this would be the topic of the final chapter of The Irrational Decision, but I realized it was far too sprawling and unwieldy to fit. It will have to be its own book. Some day.

In the meantime, I’m going to try to type it out on here.

Subscribe now

1

Unless you drink a lot of slate-star-less-wrong Kool-Aid.

2

What happened in 2020? I don’t remember.

3

(p<0.001)

By Ben Recht

Wednesday, May 20 2026, 14:14

Lutris: Safe Composition of Broadcast and Consensus

from Decentralized Thoughts

TL;DR Lutris is a hybrid distributed system protocol that integrates Byzantine Consistent Broadcast with a BFT consensus DAG to minimize latency of specific types of transactions. Hybrid Consistency: Uses broadcast for single-writer operations and consensus for shared-state contention. Unified State Machine: Maintains linearizability across both paths via versioned object locking. Liveness Recovery: Solves the “eternal lock” problem of previous broadcast protocols using epoch-based reconfiguration. Hybrid Reconfiguration: Leverages the consensus path...

By Lefteris Kokoris Kogias, Alberto Sonnino

TL;DR Lutris is a hybrid distributed system protocol that integrates Byzantine Consistent Broadcast with a BFT consensus DAG to minimize latency of specific types of transactions. Hybrid Consistency: Uses broadcast for single-writer operations and consensus for shared-state contention. Unified State Machine: Maintains linearizability across both paths via versioned object locking. Liveness Recovery: Solves the “eternal lock” problem of previous broadcast protocols using epoch-based reconfiguration. Hybrid Reconfiguration: Leverages the consensus path...

By Lefteris Kokoris Kogias, Alberto Sonnino

Wednesday, May 20 2026, 11:29

From Single-Shot Simplex to Chained Simplex

from Decentralized Thoughts

In this post we construct Chained Simplex from single-shot Simplex. The chained construction is a simple modification of the single-shot protocol and applies to any Simplex variant with the same inner certificate properties and outer proposal structure. See here for more generic constructions. We will use the decomposition from deconstructing Simplex to make the construction explicit. That post separates Simplex into: an inner protocol, which produces value certificates, decision certificates,...

By Ittai Abraham, Joachim Neu

In this post we construct Chained Simplex from single-shot Simplex. The chained construction is a simple modification of the single-shot protocol and applies to any Simplex variant with the same inner certificate properties and outer proposal structure. See here for more generic constructions. We will use the decomposition from deconstructing Simplex to make the construction explicit. That post separates Simplex into: an inner protocol, which produces value certificates, decision certificates,...

By Ittai Abraham, Joachim Neu

Wednesday, May 20 2026, 06:00

TR26-084 | Rank bounds and polynomial-time PIT for $\Sigma^k \Pi \Sigma \Pi^2$ circuits | Abhibhav Garg, Rafael Mendes de Oliveira, Akash Sengupta, Nir Shalmon, Amir Shpilka

from ECCC Papers

A depth-4 algebraic circuit with top fan-in $k$ and bottom fan-in $2$ is a circuit $\Phi$ of the form $\Phi = \sum_{i=1}^k \prod_{j=1}^{m_i} Q_{ij}$, where the polynomials $Q_{ij} \in \mathbb{K}[x_1, \ldots, x_n]$ have degree at most $2$. The class of all such circuits is denoted by $\Sigma^k \Pi \Sigma \Pi^2$. We say that the circuit $\Phi$ is an identity if it formally computes the zero polynomial. An important parameter of $\Sigma^k \Pi \Sigma \Pi^2$ circuits $\Phi$ is their (linear) rank, which is defined as the vector space dimension of the polynomials $\{Q_{ij}\}_{i \in [k], j \in [m_i]}$. We prove that, when the base field $\mathbb{K}$ is of characteristic zero, the rank of any (simple and minimal) $\Sigma^k \Pi \Sigma \Pi^2$ identity is upper bounded by a function which depends only on the top fan-in $k$. This result makes progress on [BMS13, Conjecture 28], being the first work to establish a bound on the rank of such identities that depends only on the top fan-in. Moreover, when combined with [BMS13, Theorem 2], our main result yields the first deterministic, \emph{polynomial time} PIT algorithm for $\Sigma^k \Pi \Sigma \Pi^2$ circuits. One of the key components of our proof of the rank bounds is the derivation of an approximate Hansen-type result, which is interesting in its own right. This result can be seen as an algebraic and higher-dimensional analogue of the approximate Sylvester-Gallai result of [ADSW14], and a distinct approximate fractional Sylvester-Gallai result than the one from [GOPS23]. Additionally, we prove a robust version of it, in the spirit of the generalization of Hansen's theorem by [BDWY13].

Wednesday, May 20 2026, 04:42

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

Authors: Peter Matthew Jacobs, Jeff M. Phillips

Squared Wasserstein distance is a frequently used tool to measure discrepancy between probability distributions. This distance is typically computed between empirical measures of size $n$ from two underlying random samples. Unfortunately, even in lower dimensional Euclidean space problems $\left( d \in \{2,3\} \right)$, algorithms for Wasserstein distance computation with approximate or exact precision guarantees scale poorly in the runtime as a function of $n$ and the desired precision. In response, we consider the computational-statistical runtime, where the goal is to estimate from samples the Wasserstein distance between potentially smooth measures up to $ε$-additive error in expectation with respect to the sampling; we allow $O(1)$ computational cost for collecting a sample. Towards this, we develop a Sample-Sketch-Solve paradigm where we introduce a regular cartesian grid sketch of the samples. We show that (especially under $α$-Hölder smooth distributions) this can compress the data without increasing asymptotic error, and also regularizes the structure which enables faster exact algorithms. Ultimately, we approximate $W_2^2(P,Q)$ within $ε$ error in $ε^{-\max(2,\frac{d+1+o(1)}{1+α})}$ time for $0 < α< 1$ Hölder smooth distributions $P,Q$ on $(0,1)^{d}$; an optimal $Θ(ε^{-2})$ for $α> 1/2$ when $d=2$ and nearly optimal as $α\to 1$ when $d = 3$.

Authors: Peter Matthew Jacobs, Jeff M. Phillips

Squared Wasserstein distance is a frequently used tool to measure discrepancy between probability distributions. This distance is typically computed between empirical measures of size $n$ from two underlying random samples. Unfortunately, even in lower dimensional Euclidean space problems $\left( d \in \{2,3\} \right)$, algorithms for Wasserstein distance computation with approximate or exact precision guarantees scale poorly in the runtime as a function of $n$ and the desired precision. In response, we consider the computational-statistical runtime, where the goal is to estimate from samples the Wasserstein distance between potentially smooth measures up to $ε$-additive error in expectation with respect to the sampling; we allow $O(1)$ computational cost for collecting a sample. Towards this, we develop a Sample-Sketch-Solve paradigm where we introduce a regular cartesian grid sketch of the samples. We show that (especially under $α$-Hölder smooth distributions) this can compress the data without increasing asymptotic error, and also regularizes the structure which enables faster exact algorithms. Ultimately, we approximate $W_2^2(P,Q)$ within $ε$ error in $ε^{-\max(2,\frac{d+1+o(1)}{1+α})}$ time for $0 < α< 1$ Hölder smooth distributions $P,Q$ on $(0,1)^{d}$; an optimal $Θ(ε^{-2})$ for $α> 1/2$ when $d=2$ and nearly optimal as $α\to 1$ when $d = 3$.

Wednesday, May 20 2026, 00:00

A Measure-Theoretic Analysis of Reasoning: Structural Generalization and Approximation Limits

Authors: Yuyang Zhang, Yifu Zhang, Xuehai Zhou, Xiaoyin Chen

While empirical scaling laws for LLM reasoning are well-documented, the theoretical mechanisms governing out-of-distribution (OOD) generalization remain elusive. We formalize reasoning via optimal transport, projecting discrete trajectories into a continuous metric space to quantify domain shifts using the Wasserstein-1 distance. Invoking Kantorovich duality, we bound OOD generalization via architectural Lipschitz continuity and functional approximation limits. This exposes two primary constraints. First, position-dependent attention (e.g., Absolute Positional Encoding) fails to preserve shift invariance, yielding an $Ω(1)$ Lipschitz constant and expected risk, whereas shift-invariant mechanisms (e.g., Rotary Embeddings) preserve equivariance and bound the error. Second, by mapping sequential backtracking to a Dyck-$k$ language, we establish a strict circuit depth lower bound for $\text{TC}^0$ Transformers. Scaling physical layer depth is necessary to avert representation collapse -- a constraint that scaling representation width cannot bypass due to irreducible approximation bounds in Barron spaces. Evaluations across 54 Transformer configurations on combinatorial search corroborate these bounds, demonstrating that generalization risk degrades monotonically with the Wasserstein domain shift.

Authors: Yuyang Zhang, Yifu Zhang, Xuehai Zhou, Xiaoyin Chen

While empirical scaling laws for LLM reasoning are well-documented, the theoretical mechanisms governing out-of-distribution (OOD) generalization remain elusive. We formalize reasoning via optimal transport, projecting discrete trajectories into a continuous metric space to quantify domain shifts using the Wasserstein-1 distance. Invoking Kantorovich duality, we bound OOD generalization via architectural Lipschitz continuity and functional approximation limits. This exposes two primary constraints. First, position-dependent attention (e.g., Absolute Positional Encoding) fails to preserve shift invariance, yielding an $Ω(1)$ Lipschitz constant and expected risk, whereas shift-invariant mechanisms (e.g., Rotary Embeddings) preserve equivariance and bound the error. Second, by mapping sequential backtracking to a Dyck-$k$ language, we establish a strict circuit depth lower bound for $\text{TC}^0$ Transformers. Scaling physical layer depth is necessary to avert representation collapse -- a constraint that scaling representation width cannot bypass due to irreducible approximation bounds in Barron spaces. Evaluations across 54 Transformer configurations on combinatorial search corroborate these bounds, demonstrating that generalization risk degrades monotonically with the Wasserstein domain shift.

Wednesday, May 20 2026, 00:00

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing

Authors: Sutanay Bhattacharjee, Ameya Panse, Jayalal Sarma

Color refinement is an important technique that works very well in practice for the graph isomorphism problem. Tinhofer graphs are the class of graphs for which refinement together with individualization correctly tests graph isomorphism against every other graph, irrespective of the choices of vertices made during individualization. Motivated by the fact that Tinhofer graphs form a natural boundary for efficient graph isomorphism tests based on color refinement, in this paper, we introduce a hierarchy of graph classes within the class of Tinhofer graphs. We call a graph $G$ $k$-Tinhofer if, after $k$ rounds of individualization and refinement, the resulting colored graphs remain isomorphic for every graph $H \cong G$, irrespective of the choices of vertices made during individualization. Arvind et al. (2017) studied a hierarchy of graph classes motivated by color refinement - discrete, amenable, Tinhofer, and refinable graphs. We show that the $k$-Tinhofer hierarchy lies between the class of all graphs and Tinhofer graphs, with refinable graphs coinciding with the first level of the hierarchy. We obtain two characterizations of $k$-Tinhofer graphs: an algebraic characterization in terms of orbit partitions induced by pointwise stabilizers of automorphism groups, and a combinatorial characterization in terms of individualization-refinement trees and quotient graphs. For every fixed integer $k \ge 0$, there exist vertex-colored graphs that are $k$-Tinhofer but not $(k + 1)$-Tinhofer. For every fixed integer $k \ge 0$, the problem of deciding whether a given $k$-Tinhofer graph is ($k + 1$)-Tinhofer is $P$-hard under uniform $\mathsf{AC^0}$ many-one reductions. We show that testing isomorphism between an $(n - k)$-Tinhofer graph $G$ and an arbitrary graph $H$ is fixed-parameter tractable with respect to the parameter $k$.

Authors: Sutanay Bhattacharjee, Ameya Panse, Jayalal Sarma

Color refinement is an important technique that works very well in practice for the graph isomorphism problem. Tinhofer graphs are the class of graphs for which refinement together with individualization correctly tests graph isomorphism against every other graph, irrespective of the choices of vertices made during individualization. Motivated by the fact that Tinhofer graphs form a natural boundary for efficient graph isomorphism tests based on color refinement, in this paper, we introduce a hierarchy of graph classes within the class of Tinhofer graphs. We call a graph $G$ $k$-Tinhofer if, after $k$ rounds of individualization and refinement, the resulting colored graphs remain isomorphic for every graph $H \cong G$, irrespective of the choices of vertices made during individualization. Arvind et al. (2017) studied a hierarchy of graph classes motivated by color refinement - discrete, amenable, Tinhofer, and refinable graphs. We show that the $k$-Tinhofer hierarchy lies between the class of all graphs and Tinhofer graphs, with refinable graphs coinciding with the first level of the hierarchy. We obtain two characterizations of $k$-Tinhofer graphs: an algebraic characterization in terms of orbit partitions induced by pointwise stabilizers of automorphism groups, and a combinatorial characterization in terms of individualization-refinement trees and quotient graphs. For every fixed integer $k \ge 0$, there exist vertex-colored graphs that are $k$-Tinhofer but not $(k + 1)$-Tinhofer. For every fixed integer $k \ge 0$, the problem of deciding whether a given $k$-Tinhofer graph is ($k + 1$)-Tinhofer is $P$-hard under uniform $\mathsf{AC^0}$ many-one reductions. We show that testing isomorphism between an $(n - k)$-Tinhofer graph $G$ and an arbitrary graph $H$ is fixed-parameter tractable with respect to the parameter $k$.

Wednesday, May 20 2026, 00:00

Risk of Bad Tails: CVaR-Aware Pandora's Box and Prophet Inequality

Authors: Jingwei Ji

We study Conditional Value-at-Risk (CVaR) variants of two canonical sequential decision problems: Pandora's box and the prophet inequality. For Pandora's box, the risk-aware problem retains an exact Weitzman-style index solution after a one-dimensional variational reduction. For the prophet inequality, the picture is different: for every CVaR level $α\in(0,1)$, no positive constant approximation guarantee can hold without distributional structure, in sharp contrast with the risk-neutral case $α=1$, and we characterize the tight instance-dependent guarantee. Already in two-item hard instances, the prophet's CVaR benchmark can be made arbitrarily large while every online policy's CVaR remains bounded. This impossibility is due to the nature of CVaR objective: it measures only the worst $α$-fraction of outcomes, so any compromise an online policy makes to preserve the chance of a large payoff in the upper $(1-α)$-fraction does not help its CVaR. It turns out that additional distributional structure restores a uniform result: under continuous reward distributions satisfying a recentered increasing-failure-rate-average (IFRA) condition, a threshold policy achieves an explicit constant bound.

Authors: Jingwei Ji

We study Conditional Value-at-Risk (CVaR) variants of two canonical sequential decision problems: Pandora's box and the prophet inequality. For Pandora's box, the risk-aware problem retains an exact Weitzman-style index solution after a one-dimensional variational reduction. For the prophet inequality, the picture is different: for every CVaR level $α\in(0,1)$, no positive constant approximation guarantee can hold without distributional structure, in sharp contrast with the risk-neutral case $α=1$, and we characterize the tight instance-dependent guarantee. Already in two-item hard instances, the prophet's CVaR benchmark can be made arbitrarily large while every online policy's CVaR remains bounded. This impossibility is due to the nature of CVaR objective: it measures only the worst $α$-fraction of outcomes, so any compromise an online policy makes to preserve the chance of a large payoff in the upper $(1-α)$-fraction does not help its CVaR. It turns out that additional distributional structure restores a uniform result: under continuous reward distributions satisfying a recentered increasing-failure-rate-average (IFRA) condition, a threshold policy achieves an explicit constant bound.

Wednesday, May 20 2026, 00:00

Euclidean Embedding of Data Using Local Distances

Authors: Dimitris Arabadjis

We study the problem of recovering a globally consistent Euclidean embedding of data, given only a local distance graph and propose a method that optimally represents these distances. The method operates solely on a neighborhood graph weighted by pairwise distances, without requiring any prior vector representation of the data. The embedding is obtained by solving a variational problem that matches local, on-graph distances to the Euclidean metric, induced by the differentials of the embedding functions. The resulting Euler-Lagrange equations are derived in a coordinate-free form, enabling direct evaluation of all operators from the distance graph alone. Though non-linear and missing an explicit expression for their non-linearity, these equations are shown to be resolved as an iteratively updated sparse linear problem. The main contributions of the proposed approach are (a) the derivation of the functional equations governing the optimal Euclidean embedding in the continuum, (b) a representation-free formulation that requires only a neighborhood distance graph and no feature vectors and (c) an estimation procedure based exclusively on local graph operations. We experimentally evaluate the resulting non-parametric algorithm on synthetic manifolds and real datasets, demonstrating consistent preservation of local metric structure and neighboring relations, while approximating the global isometric embedding.

Authors: Dimitris Arabadjis

We study the problem of recovering a globally consistent Euclidean embedding of data, given only a local distance graph and propose a method that optimally represents these distances. The method operates solely on a neighborhood graph weighted by pairwise distances, without requiring any prior vector representation of the data. The embedding is obtained by solving a variational problem that matches local, on-graph distances to the Euclidean metric, induced by the differentials of the embedding functions. The resulting Euler-Lagrange equations are derived in a coordinate-free form, enabling direct evaluation of all operators from the distance graph alone. Though non-linear and missing an explicit expression for their non-linearity, these equations are shown to be resolved as an iteratively updated sparse linear problem. The main contributions of the proposed approach are (a) the derivation of the functional equations governing the optimal Euclidean embedding in the continuum, (b) a representation-free formulation that requires only a neighborhood distance graph and no feature vectors and (c) an estimation procedure based exclusively on local graph operations. We experimentally evaluate the resulting non-parametric algorithm on synthetic manifolds and real datasets, demonstrating consistent preservation of local metric structure and neighboring relations, while approximating the global isometric embedding.

Wednesday, May 20 2026, 00:00

Spatially Accelerated Winding Numbers for Curved Geometry

Authors: Jacob Spainhour, Brad Whitlock, Kenneth Weiss

The generalized winding number (GWN) is a scalar field that supports robust containment queries on curved geometry, including non-watertight, overlapping, and nested boundary representations. While queries can be easily parallelized over samples, direct evaluation on parametric curves and surfaces remains costly for large and complex models. Fast, state-of-the-art GWN approaches leverage a spatial index to approximate the GWN, typically coupled with a Taylor expansion which approximates the GWN contribution for far clusters of geometric primitives. However, such methods operate only on discrete inputs such as triangle meshes and point clouds, and would introduce containment errors near boundaries if applied to curved input. We extend support for fast GWN evaluation over arbitrary collections of NURBS curves in 2D and trimmed NURBS patches in 3D via a Bounding Volume Hierarchy that stores efficiently precomputed moment data in the hierarchy nodes. When querying the hierarchy, approximations for far clusters are used alongside direct evaluation for nearby NURBS primitives, achieving sub-linear complexity while preserving the geometric features in the vicinity of the query point. Central to our performance improvements is an adaptive subdivision strategy for NURBS primitives during a preprocessing phase, creating better spatial partitions while retaining the same accuracy for containment decisions as a direct evaluation. We demonstrate the performance and accuracy of our approach across a large collection of 2D and 3D datasets.

Authors: Jacob Spainhour, Brad Whitlock, Kenneth Weiss

The generalized winding number (GWN) is a scalar field that supports robust containment queries on curved geometry, including non-watertight, overlapping, and nested boundary representations. While queries can be easily parallelized over samples, direct evaluation on parametric curves and surfaces remains costly for large and complex models. Fast, state-of-the-art GWN approaches leverage a spatial index to approximate the GWN, typically coupled with a Taylor expansion which approximates the GWN contribution for far clusters of geometric primitives. However, such methods operate only on discrete inputs such as triangle meshes and point clouds, and would introduce containment errors near boundaries if applied to curved input. We extend support for fast GWN evaluation over arbitrary collections of NURBS curves in 2D and trimmed NURBS patches in 3D via a Bounding Volume Hierarchy that stores efficiently precomputed moment data in the hierarchy nodes. When querying the hierarchy, approximations for far clusters are used alongside direct evaluation for nearby NURBS primitives, achieving sub-linear complexity while preserving the geometric features in the vicinity of the query point. Central to our performance improvements is an adaptive subdivision strategy for NURBS primitives during a preprocessing phase, creating better spatial partitions while retaining the same accuracy for containment decisions as a direct evaluation. We demonstrate the performance and accuracy of our approach across a large collection of 2D and 3D datasets.

Wednesday, May 20 2026, 00:00

A Scaling-Parameter Framework for Perimeter and Area in Self-Similar Planar Fractals

Authors: Pedro Marotta

The Koch snowflake is a classical example of a planar curve with infinite perimeter enclosing a finite, positive area. Although such examples are well known individually, classical treatments typically analyze each construction in isolation and classify them by similarity dimension. This paper develops a unified parameter-space representation for a class of self-similar planar constructions, organized by two integers -- the number of self-similar pieces $N$ and the inverse linear scale factor $r$ -- together with two derived growth ratios $α= N/r$ and $β= N/r^2$, governing perimeter and area scaling respectively. The $(N,r)$ parameter space is partitioned into three regimes -- $N \le r$, $r < N < r^2$, and $N \ge r^2$ -- corresponding to qualitatively distinct asymptotic behaviors of perimeter and area jointly. Within the intermediate regime $r < N < r^2$, a construction-class refinement distinguishes additive constructions (region bounded by the iterated curve), which yield positive finite asymptotic area under a stated non-overlap assumption, from subtractive constructions (iterated set itself), which yield zero asymptotic area. This records a structural non-equivalence inside the same dimension class that is not visible from $D = \log N / \log r$ alone. Four worked examples illustrate the framework -- the Sierpinski triangle, Sierpinski carpet, Koch snowflake, and a Koch-style construction on a square invented by the author -- and four further constructions are analyzed predictively to demonstrate that diagnostic outputs follow from $(N, r, \text{construction class})$ without re-derivation. The contribution lies in formulation and synthesis: the paper consolidates several classical results into a single diagnostic representation in which, given $(N, r)$ and construction class, the asymptotic behavior of perimeter and area can be inferred directly.

Authors: Pedro Marotta

The Koch snowflake is a classical example of a planar curve with infinite perimeter enclosing a finite, positive area. Although such examples are well known individually, classical treatments typically analyze each construction in isolation and classify them by similarity dimension. This paper develops a unified parameter-space representation for a class of self-similar planar constructions, organized by two integers -- the number of self-similar pieces $N$ and the inverse linear scale factor $r$ -- together with two derived growth ratios $α= N/r$ and $β= N/r^2$, governing perimeter and area scaling respectively. The $(N,r)$ parameter space is partitioned into three regimes -- $N \le r$, $r < N < r^2$, and $N \ge r^2$ -- corresponding to qualitatively distinct asymptotic behaviors of perimeter and area jointly. Within the intermediate regime $r < N < r^2$, a construction-class refinement distinguishes additive constructions (region bounded by the iterated curve), which yield positive finite asymptotic area under a stated non-overlap assumption, from subtractive constructions (iterated set itself), which yield zero asymptotic area. This records a structural non-equivalence inside the same dimension class that is not visible from $D = \log N / \log r$ alone. Four worked examples illustrate the framework -- the Sierpinski triangle, Sierpinski carpet, Koch snowflake, and a Koch-style construction on a square invented by the author -- and four further constructions are analyzed predictively to demonstrate that diagnostic outputs follow from $(N, r, \text{construction class})$ without re-derivation. The contribution lies in formulation and synthesis: the paper consolidates several classical results into a single diagnostic representation in which, given $(N, r)$ and construction class, the asymptotic behavior of perimeter and area can be inferred directly.

Wednesday, May 20 2026, 00:00

Deterministic Volume Estimation of Truncated Hypercubes

Authors: Kyra Gunluk

We present a deterministic polynomial-time algorithm for estimating the volume of a hypercube intersected by a fixed number of constraints of the type $f(x) \leq b$, where $f$ is the sum of univariate functions that are each nonnegative, monotone, and convex. Such constraints include knapsack and norm-ball constraints. The case of the unit hypercube truncated by a single linear constraint (halfspace) is already #P-hard. Given $k$ such constraints in dimension $n$, with total input length of at most $L$ bits, total output length of at most $L_o$ bits, and an error parameter $\varepsilon > 0$, our algorithm computes a $(1 + \varepsilon)$-multiplicative approximation of the volume of their intersection with the unit hypercube $[0,1]^n$ in time poly$_k(n, 1/\varepsilon, L,L_o)$.

Authors: Kyra Gunluk

We present a deterministic polynomial-time algorithm for estimating the volume of a hypercube intersected by a fixed number of constraints of the type $f(x) \leq b$, where $f$ is the sum of univariate functions that are each nonnegative, monotone, and convex. Such constraints include knapsack and norm-ball constraints. The case of the unit hypercube truncated by a single linear constraint (halfspace) is already #P-hard. Given $k$ such constraints in dimension $n$, with total input length of at most $L$ bits, total output length of at most $L_o$ bits, and an error parameter $\varepsilon > 0$, our algorithm computes a $(1 + \varepsilon)$-multiplicative approximation of the volume of their intersection with the unit hypercube $[0,1]^n$ in time poly$_k(n, 1/\varepsilon, L,L_o)$.

Wednesday, May 20 2026, 00:00

Optimizing for Fairness in Generalized Kidney Exchange: Theory and Computations

Authors: Claire Chang, Arin Khare, David Shmoys

The seminal work of Roth, Sönmez, & Ünver shows that the Edmonds-Gallai structure theorem for non-bipartite matching can be leveraged to yield a randomized algorithm to match patient-donor pairs in kidney exchange with extraordinarily strong properties. This breakthrough led to randomized polynomial-time algorithms to find a maximum-cardinality matching maximizing individual fairness objectives--measured by the probability that nodes are matched--such as Nash social welfare. But the exchanges allowed in practice go beyond cardinality matching, generalizing to weighted variants and allowing structures such as paths and 3-cycles. We show that strongly polynomial algorithms guaranteeing the same fairness properties can be obtained in weighted settings for matching and 2-paths. While even maximum cardinality coverage with cycles and paths of length at least three is NP-hard, we provide a general result showing that any optimization subroutine (for whichever structure is allowed) can be bootstrapped using a polynomial number of calls to yield a mechanism that has analogous fairness properties to those obtained for matching. We complement these theoretical results with computational results, both on well-studied synthetic data-sets and on samples drawn from real data, that demonstrate the striking advantages of adding fairness considerations to more general kidney-exchange mechanisms.

Authors: Claire Chang, Arin Khare, David Shmoys

The seminal work of Roth, Sönmez, & Ünver shows that the Edmonds-Gallai structure theorem for non-bipartite matching can be leveraged to yield a randomized algorithm to match patient-donor pairs in kidney exchange with extraordinarily strong properties. This breakthrough led to randomized polynomial-time algorithms to find a maximum-cardinality matching maximizing individual fairness objectives--measured by the probability that nodes are matched--such as Nash social welfare. But the exchanges allowed in practice go beyond cardinality matching, generalizing to weighted variants and allowing structures such as paths and 3-cycles. We show that strongly polynomial algorithms guaranteeing the same fairness properties can be obtained in weighted settings for matching and 2-paths. While even maximum cardinality coverage with cycles and paths of length at least three is NP-hard, we provide a general result showing that any optimization subroutine (for whichever structure is allowed) can be bootstrapped using a polynomial number of calls to yield a mechanism that has analogous fairness properties to those obtained for matching. We complement these theoretical results with computational results, both on well-studied synthetic data-sets and on samples drawn from real data, that demonstrate the striking advantages of adding fairness considerations to more general kidney-exchange mechanisms.

Wednesday, May 20 2026, 00:00

Block-Sphere Vector Quantization

Authors: Heesang Ann, Joongkyu Lee, Min-hwan Oh

Vector quantization is a fundamental primitive for scalable machine learning systems, enabling memory-efficient storage, fast retrieval, and compressed inference. Recent rotation-based quantizers such as EDEN, RabitQ, and TurboQuant have introduced strong guarantees and empirical performance, but the surrounding comparisons have been difficult to interpret because they rely on different distortion criteria, probability regimes, and implementation assumptions. As our first contribution, we provide a unified theoretical comparison of these methods and show that their relative advantages are criterion-dependent rather than absolute: EDEN and TurboQuant are favorable for MSE distortion, EDEN is also effective for expected inner-product distortion, and RabitQ provides strong high-probability control. This comparison further clarifies that EDEN provides particularly strong guarantees for expected distortion measures. As our second contribution, we introduce Block-Sphere Quantization (BlockQuant), a new rotation-based block quantization algorithm designed around the spherical geometry of randomly rotated vectors. Unlike coordinate-wise quantizers, BlockQuant quantizes blocks on the sphere, preserving the geometry of rotated embeddings more faithfully. We prove that this block-spherical design theoretically improves over the baselines considered in this paper for both reconstruction MSE and expected inner-product distortion. Our experiments on real embedding datasets and long-context LLM inference tasks show practical gains that are consistent with our theoretical improvements.

Authors: Heesang Ann, Joongkyu Lee, Min-hwan Oh

Vector quantization is a fundamental primitive for scalable machine learning systems, enabling memory-efficient storage, fast retrieval, and compressed inference. Recent rotation-based quantizers such as EDEN, RabitQ, and TurboQuant have introduced strong guarantees and empirical performance, but the surrounding comparisons have been difficult to interpret because they rely on different distortion criteria, probability regimes, and implementation assumptions. As our first contribution, we provide a unified theoretical comparison of these methods and show that their relative advantages are criterion-dependent rather than absolute: EDEN and TurboQuant are favorable for MSE distortion, EDEN is also effective for expected inner-product distortion, and RabitQ provides strong high-probability control. This comparison further clarifies that EDEN provides particularly strong guarantees for expected distortion measures. As our second contribution, we introduce Block-Sphere Quantization (BlockQuant), a new rotation-based block quantization algorithm designed around the spherical geometry of randomly rotated vectors. Unlike coordinate-wise quantizers, BlockQuant quantizes blocks on the sphere, preserving the geometry of rotated embeddings more faithfully. We prove that this block-spherical design theoretically improves over the baselines considered in this paper for both reconstruction MSE and expected inner-product distortion. Our experiments on real embedding datasets and long-context LLM inference tasks show practical gains that are consistent with our theoretical improvements.

Wednesday, May 20 2026, 00:00

Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth

Authors: Yuxi Liu, Kangyi Tian, Mingyu Xiao

The \textsc{Co-Path Packing} (resp., \textsc{Co-Path Set}) problem asks whether a given graph can be edited to a collection of induced paths by deleting at most $k$ vertices (resp., $k$ edges). Both are fundamental problems with significant applications in bioinformatics and have been extensively studied within the framework of exact and parameterized algorithms. Currently, the state-of-the-art approach utilizes the randomized ``Cut \& Count'' technique, which solves \textsc{Co-Path Set} in $O^*(4^{\mathbf{tw}})$ time and \textsc{Co-Path Packing} in $O^*(5^{\mathbf{pw}})$ time, where $\mathbf{tw}$ is treewidth and $\mathbf{pw}$ is pathwidth. However, as there is no known method to derandomize the ``Cut \& Count'' technique, the existence of deterministic single exponential time algorithms for these problems parameterized by treewidth has remained an open question. In this paper, we resolve this gap by providing deterministic single exponential time algorithms for both problems when parameterized by treewidth.

Authors: Yuxi Liu, Kangyi Tian, Mingyu Xiao

The \textsc{Co-Path Packing} (resp., \textsc{Co-Path Set}) problem asks whether a given graph can be edited to a collection of induced paths by deleting at most $k$ vertices (resp., $k$ edges). Both are fundamental problems with significant applications in bioinformatics and have been extensively studied within the framework of exact and parameterized algorithms. Currently, the state-of-the-art approach utilizes the randomized ``Cut \& Count'' technique, which solves \textsc{Co-Path Set} in $O^*(4^{\mathbf{tw}})$ time and \textsc{Co-Path Packing} in $O^*(5^{\mathbf{pw}})$ time, where $\mathbf{tw}$ is treewidth and $\mathbf{pw}$ is pathwidth. However, as there is no known method to derandomize the ``Cut \& Count'' technique, the existence of deterministic single exponential time algorithms for these problems parameterized by treewidth has remained an open question. In this paper, we resolve this gap by providing deterministic single exponential time algorithms for both problems when parameterized by treewidth.

Wednesday, May 20 2026, 00:00

Linear Kernels for $l$-Exact Component Order Connectivity

Authors: Yuxi Liu, Mingyu Xiao

The \textsc{$l$-Exact Component Order Connectivity} problem asks whether, given an input graph $G$ and an integer $k$, there exists a vertex subset $S\subseteq V(G)$ of size at most $k$ such that every connected component in $G - S$ has exactly $l$ vertices. In this paper, we present an $O(kl)$-vertex kernel for this problem, computable in $|V(G)|^{O(l)}$ time. This is the first known linear kernel for each fixed $l\geq 3$. For $l=1$, this problem reduces to the classical \textsc{Vertex Cover}, and our result matches the best-known $2k$-vertex kernel. For $l=2$ (known as \textsc{Deletion to Induced Matching}), we can get a $(3k + 1)$-vertex kernel, improving the previously known result of $6k$ vertices. Our kernelization algorithm is built upon on an extended crown decomposition combined with linear programming and other techniques.

Authors: Yuxi Liu, Mingyu Xiao

The \textsc{$l$-Exact Component Order Connectivity} problem asks whether, given an input graph $G$ and an integer $k$, there exists a vertex subset $S\subseteq V(G)$ of size at most $k$ such that every connected component in $G - S$ has exactly $l$ vertices. In this paper, we present an $O(kl)$-vertex kernel for this problem, computable in $|V(G)|^{O(l)}$ time. This is the first known linear kernel for each fixed $l\geq 3$. For $l=1$, this problem reduces to the classical \textsc{Vertex Cover}, and our result matches the best-known $2k$-vertex kernel. For $l=2$ (known as \textsc{Deletion to Induced Matching}), we can get a $(3k + 1)$-vertex kernel, improving the previously known result of $6k$ vertices. Our kernelization algorithm is built upon on an extended crown decomposition combined with linear programming and other techniques.

Wednesday, May 20 2026, 00:00

Hardness and Approximation for Coloring Digraphs

Authors: Parinya Chalermsook, Harmender Gahlawat, Felix Klingelhoefer, Alantha Newman, Chaoliang Tang

The dichromatic number $\vecχ(D)$ of a digraph is the minimum number $k$ such that $V(D)$ can be partitioned into $k$ subsets, each inducing an acyclic digraph. The acyclic number $\vecα(D)$ is the cardinality of a largest induced acyclic subdigraph of $D$. We study these problems from an approximation point of view. We begin with establishing that even when restricted to tournaments, approximating $\vecχ$ and $\vecα$ remain as challenging as their undirected counterparts on general graphs. Specifically, we establish that for every $ε>0$, it is hard to approximate both $\vecα$ and $\vecχ$ up to a factor of $n^{1-ε}$ even when restricted to tournaments. We next consider approximate coloring of digraphs in special cases. We begin with establishing that we can color $\ell$-dicolorable digraphs using at most $\ell \cdot n^{1-\frac{1}{\ell}}$ colors in time $O(n^{2\ell})$; in particular, we can color $2$-dicolorable digraphs with $2\sqrt{n}$ colors in polynomial time. We then focus on bounding the dichromatic number of dense digraphs as a function of the independence number $α$ of the underlying graph. We consider two special cases in this regard: digraphs with $\vecχ(D)\leq 2$ and digraphs that do not contain any directed triangle. For these cases, we present algorithms which generalize and improve existing tools and results.

Authors: Parinya Chalermsook, Harmender Gahlawat, Felix Klingelhoefer, Alantha Newman, Chaoliang Tang

The dichromatic number $\vecχ(D)$ of a digraph is the minimum number $k$ such that $V(D)$ can be partitioned into $k$ subsets, each inducing an acyclic digraph. The acyclic number $\vecα(D)$ is the cardinality of a largest induced acyclic subdigraph of $D$. We study these problems from an approximation point of view. We begin with establishing that even when restricted to tournaments, approximating $\vecχ$ and $\vecα$ remain as challenging as their undirected counterparts on general graphs. Specifically, we establish that for every $ε>0$, it is hard to approximate both $\vecα$ and $\vecχ$ up to a factor of $n^{1-ε}$ even when restricted to tournaments. We next consider approximate coloring of digraphs in special cases. We begin with establishing that we can color $\ell$-dicolorable digraphs using at most $\ell \cdot n^{1-\frac{1}{\ell}}$ colors in time $O(n^{2\ell})$; in particular, we can color $2$-dicolorable digraphs with $2\sqrt{n}$ colors in polynomial time. We then focus on bounding the dichromatic number of dense digraphs as a function of the independence number $α$ of the underlying graph. We consider two special cases in this regard: digraphs with $\vecχ(D)\leq 2$ and digraphs that do not contain any directed triangle. For these cases, we present algorithms which generalize and improve existing tools and results.

Wednesday, May 20 2026, 00:00

Meta-Theorems for Cuttable Distributed Problems