Theory of Computing Report

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

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

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

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

Monday, July 20 2026, 00:00

Arithmetic circuit lower bounds from sumset expansion

Authors: Anand Kumar Narayanan

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

Authors: Anand Kumar Narayanan

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

Monday, July 20 2026, 00:00

Improved Almost laws for $SO(3)$

Authors: Gal Yehuda

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

Authors: Gal Yehuda

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

Monday, July 20 2026, 00:00

Updating zigzag representatives efficiently

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

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

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

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

Monday, July 20 2026, 00:00

On the Stability of Minimum-Weight Perfect Matching on the Line

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

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

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

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

Monday, July 20 2026, 00:00

trueform: Fast And Robust Mesh CSG Via Topological Aggregation

Authors: Žiga Sajovic, Dejan Knez

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

Authors: Žiga Sajovic, Dejan Knez

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

Monday, July 20 2026, 00:00

Contextual Fraction on Permutation Gain Graphs: Exact Algorithms, Query Lower Bounds, and Dynamic Maintenance

Authors: Ronald Katende

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

Authors: Ronald Katende

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

Monday, July 20 2026, 00:00

NP-Hardness of Connected Components Reconfiguration under Component Jumping on Caterpillar Graphs

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

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

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

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

Monday, July 20 2026, 00:00

Testing Distributions Against Bounded Distinguishers

Authors: Mark Bun, Rathin Desai, Renato Ferreira Pinto

Motivated by the challenge of testing distributions over high-dimensional or continuous domains, we study distribution testing with respect to bounded classes of distinguishers. A representative task is to use samples from an unknown distribution $P$ over a very large domain to decide between two cases: $P = P_{\mathsf{ref}}$ for a fixed reference distribution $P_{\mathsf{ref}}$, or there exists a distinguisher $f$ in a bounded class $\mathcal{F}$ which witnesses the separation $|\mathbf{E}_P[f] - \mathbf{E}_{P_{\mathsf{ref}}}[f]| > ε$. This is the task of identity testing with respect to fooling distance, a name inspired by the conceptual connection with pseudorandomness. (Formally, our model instantiates integral probability metrics from Boolean classes of bounded expressivity.) We show that testing with respect to fooling distance is not only a natural computational problem that admits sample-efficient algorithms even in high-dimensional settings, but also one that reveals and underlies connections between three seemingly unrelated areas of study: testable learning, verification of learning algorithms, and testing of structured distributions (whose "$\mathcal{A}_k$-testing" model our framework extends). These connections yield new results for all of these models, including: 1. Testable proper learners using membership queries for halfspaces and decision trees. 2. A lower bound for testable PAC verification in terms of Rademacher complexity, and a distribution-free verification protocol for disjoint unions of $k$ multidimensional rectangles. 3. Identity testers (with respect to total variation distance) for decision tree distributions and distributions with low-degree polynomial densities, over Boolean and continuous hypercube domains.

Authors: Mark Bun, Rathin Desai, Renato Ferreira Pinto

Motivated by the challenge of testing distributions over high-dimensional or continuous domains, we study distribution testing with respect to bounded classes of distinguishers. A representative task is to use samples from an unknown distribution $P$ over a very large domain to decide between two cases: $P = P_{\mathsf{ref}}$ for a fixed reference distribution $P_{\mathsf{ref}}$, or there exists a distinguisher $f$ in a bounded class $\mathcal{F}$ which witnesses the separation $|\mathbf{E}_P[f] - \mathbf{E}_{P_{\mathsf{ref}}}[f]| > ε$. This is the task of identity testing with respect to fooling distance, a name inspired by the conceptual connection with pseudorandomness. (Formally, our model instantiates integral probability metrics from Boolean classes of bounded expressivity.) We show that testing with respect to fooling distance is not only a natural computational problem that admits sample-efficient algorithms even in high-dimensional settings, but also one that reveals and underlies connections between three seemingly unrelated areas of study: testable learning, verification of learning algorithms, and testing of structured distributions (whose "$\mathcal{A}_k$-testing" model our framework extends). These connections yield new results for all of these models, including: 1. Testable proper learners using membership queries for halfspaces and decision trees. 2. A lower bound for testable PAC verification in terms of Rademacher complexity, and a distribution-free verification protocol for disjoint unions of $k$ multidimensional rectangles. 3. Identity testers (with respect to total variation distance) for decision tree distributions and distributions with low-degree polynomial densities, over Boolean and continuous hypercube domains.

Monday, July 20 2026, 00:00

On the CGGRT Criterion for Detecting Bipartite Perfect Matchings in NC

Authors: Swastik Kopparty, Shubhangi Saraf

The recent breakthrough work of Chatterjee, Ghosh, Gurjar, Raj and Thierauf [CGGRT26] gives the first deterministic NC algorithm for the bipartite matching problem. They show how to detect as well as find perfect matchings in bipartite graphs in NC. In this note we present an arguably simpler-to-state variation of the NC detection criterion of [CGGRT26], with improved parameters.

Authors: Swastik Kopparty, Shubhangi Saraf

The recent breakthrough work of Chatterjee, Ghosh, Gurjar, Raj and Thierauf [CGGRT26] gives the first deterministic NC algorithm for the bipartite matching problem. They show how to detect as well as find perfect matchings in bipartite graphs in NC. In this note we present an arguably simpler-to-state variation of the NC detection criterion of [CGGRT26], with improved parameters.

Monday, July 20 2026, 00:00

Revisiting Real-Time Interval and Throughput Maximization

Authors: Allan Borodin, Changdao He, Nadim Mottu

Job throughput maximization is the central maximization problem in scheduling. Interval scheduling is the special case of throughput maximization when jobs are intervals and therefore there is no slack available in which to schedule a job. It is interesting to know to what extent results for interval scheduling can be extended to the more general throughput problem in the real-time model. For the unweighted and proportionally weighted throughput problem (where the weight or value $w_i$ of a job $J_i$ is its processing time $p_i$), there are constant competitive real-time scheduling algorithms using preemption with restarting. More generally, the result for proportionally weighted interval scheduling can be extended to C-Benevolent weight functions. We also introduce a new real-time model in which jobs are announced before the actual release time of a job. We show that with sufficient advance notice, we can obtain a constant competitive ratio for proportionally weighted throughput {\it without any preemption}. However, this advance notice result does not extend to arbitrary C-Benevolent and D-Benevolent weight functions. Finally, we show that unlike interval scheduling, unweighted throughput using preemption with revoking admits no constant competitive ratio when the number of distinct processing times is unrestricted. More precisely, for instances with at most $k$ distinct processing times, we give a lower bound of $1/(k+1)$ and a deterministic $1/(2k)$-competitive algorithm.

Authors: Allan Borodin, Changdao He, Nadim Mottu

Job throughput maximization is the central maximization problem in scheduling. Interval scheduling is the special case of throughput maximization when jobs are intervals and therefore there is no slack available in which to schedule a job. It is interesting to know to what extent results for interval scheduling can be extended to the more general throughput problem in the real-time model. For the unweighted and proportionally weighted throughput problem (where the weight or value $w_i$ of a job $J_i$ is its processing time $p_i$), there are constant competitive real-time scheduling algorithms using preemption with restarting. More generally, the result for proportionally weighted interval scheduling can be extended to C-Benevolent weight functions. We also introduce a new real-time model in which jobs are announced before the actual release time of a job. We show that with sufficient advance notice, we can obtain a constant competitive ratio for proportionally weighted throughput {\it without any preemption}. However, this advance notice result does not extend to arbitrary C-Benevolent and D-Benevolent weight functions. Finally, we show that unlike interval scheduling, unweighted throughput using preemption with revoking admits no constant competitive ratio when the number of distinct processing times is unrestricted. More precisely, for instances with at most $k$ distinct processing times, we give a lower bound of $1/(k+1)$ and a deterministic $1/(2k)$-competitive algorithm.

Monday, July 20 2026, 00:00

Improving Improved Kernel PLS

Authors: Ole-Christian Galbo Engstrøm

Improved Kernel Partial Least Squares (IKPLS) algorithms 1 and 2 are among the fastest PLS calibration algorithms. This article focuses on two shared steps, the computation of the $\mathbf{X}$ rotations, $\mathbf{R}$, and the $\mathbf{Y}$ loadings, $\mathbf{Q}$, and accelerates both. For $\mathbf{R}$, term-by-term accumulation is replaced by a direct evaluation strategy that requires the same number of multiplications but parallelizes better on modern hardware. For $\mathbf{Q}$, I identify - to the best of my knowledge, for the first time - equivalences showing that each $\mathbf{Y}$ loading is obtainable, up to explicitly derived constants, from quantities already computed earlier in the same iteration, and I exploit them in IKPLS to reduce the cost of each loading from $Θ\left(KM\right)$ to $Θ\left(M\right)$ operations whenever $M = 1$ or $2 \leq M < K$, with $K$ predictor variables (number of columns in $\mathbf{X}$) and $M$ response variables (number of columns in $\mathbf{Y}$). Both improvements provably yield exactly the same $\mathbf{W}$, $\mathbf{P}$, $\mathbf{Q}$, $\mathbf{R}$, and $\mathbf{T}$ as the original algorithms. Benchmarks with NumPy (CPU) and JAX (GPU) show speedups of up to two orders of magnitude for the isolated steps and of approximately $2\times$ (CPU) and $6\times$ (GPU) for entire fits. Both improvements are implemented in the free, open-source Python package \texttt{ikpls}.

Authors: Ole-Christian Galbo Engstrøm

Improved Kernel Partial Least Squares (IKPLS) algorithms 1 and 2 are among the fastest PLS calibration algorithms. This article focuses on two shared steps, the computation of the $\mathbf{X}$ rotations, $\mathbf{R}$, and the $\mathbf{Y}$ loadings, $\mathbf{Q}$, and accelerates both. For $\mathbf{R}$, term-by-term accumulation is replaced by a direct evaluation strategy that requires the same number of multiplications but parallelizes better on modern hardware. For $\mathbf{Q}$, I identify - to the best of my knowledge, for the first time - equivalences showing that each $\mathbf{Y}$ loading is obtainable, up to explicitly derived constants, from quantities already computed earlier in the same iteration, and I exploit them in IKPLS to reduce the cost of each loading from $Θ\left(KM\right)$ to $Θ\left(M\right)$ operations whenever $M = 1$ or $2 \leq M < K$, with $K$ predictor variables (number of columns in $\mathbf{X}$) and $M$ response variables (number of columns in $\mathbf{Y}$). Both improvements provably yield exactly the same $\mathbf{W}$, $\mathbf{P}$, $\mathbf{Q}$, $\mathbf{R}$, and $\mathbf{T}$ as the original algorithms. Benchmarks with NumPy (CPU) and JAX (GPU) show speedups of up to two orders of magnitude for the isolated steps and of approximately $2\times$ (CPU) and $6\times$ (GPU) for entire fits. Both improvements are implemented in the free, open-source Python package \texttt{ikpls}.

Monday, July 20 2026, 00:00

A Unified Theory of Sparsification

Authors: Sanjeev Khanna, Aaron Putterman, Madhu Sudan

We study the sparsifiability of \emph{real-valued codes}, a unifying abstraction that generalizes both combinatorial and continuous notions of sparsification, including spectral sparsification. In our setting, a code $C \subseteq \mathbb{R}_{\geq 0}^m$ is simply a collection of nonnegative real-valued vectors, and for a parameter $ε> 0$, a \emph{$(1 \pm ε)$-sparsifier} of $C$ is a subset $T \subseteq [m]$, together with weights $w \in \mathbb{R}_{\geq 0}^T$, such that, for every $c \in C$, $\sum_{i \in T} w_i c_i \in (1 \pm ε)\sum_{i=1}^m c_i$. When $C \subseteq \{0,1\}^m$, this specializes to code sparsification, and hence captures CSP sparsification, as studied by Khanna--Putterman--Sudan (SODA 2024, STOC 2025) and Brakensiek--Guruswami (STOC 2025). Similarly, for a graph $G=(V,E)$, if one defines $C=\{c^{(x)}:x\in\mathbb R^V\}\subseteq\mathbb R_{\geq 0}^E$ by $c^{(x)}_{(u,v)}=(x_u-x_v)^2$, then sparsifying $C$ is exactly spectral graph sparsification, as studied by Spielman--Teng (SICOMP 2011). Although the techniques driving combinatorial and continuous sparsification have traditionally been largely disjoint, our main result is a single structural theorem governing the sparsifiability of arbitrary real-valued codes $C\subseteq\mathbb{R}_{\geq 0}^m$. The central parameter is \emph{continuous-valued non-redundancy} ($\mathrm{CVNRD}$), a real-valued analogue of non-redundancy that captures the largest approximately block-diagonal obstruction contained in $C$. Our theorem gives sparsifiers of size nearly-linear in $\mathrm{CVNRD}$, and shows that $\mathrm{CVNRD}$ is also a lower-bound obstruction for the broad class of coordinate-wise unbiased randomized sparsification schemes.

Authors: Sanjeev Khanna, Aaron Putterman, Madhu Sudan

We study the sparsifiability of \emph{real-valued codes}, a unifying abstraction that generalizes both combinatorial and continuous notions of sparsification, including spectral sparsification. In our setting, a code $C \subseteq \mathbb{R}_{\geq 0}^m$ is simply a collection of nonnegative real-valued vectors, and for a parameter $ε> 0$, a \emph{$(1 \pm ε)$-sparsifier} of $C$ is a subset $T \subseteq [m]$, together with weights $w \in \mathbb{R}_{\geq 0}^T$, such that, for every $c \in C$, $\sum_{i \in T} w_i c_i \in (1 \pm ε)\sum_{i=1}^m c_i$. When $C \subseteq \{0,1\}^m$, this specializes to code sparsification, and hence captures CSP sparsification, as studied by Khanna--Putterman--Sudan (SODA 2024, STOC 2025) and Brakensiek--Guruswami (STOC 2025). Similarly, for a graph $G=(V,E)$, if one defines $C=\{c^{(x)}:x\in\mathbb R^V\}\subseteq\mathbb R_{\geq 0}^E$ by $c^{(x)}_{(u,v)}=(x_u-x_v)^2$, then sparsifying $C$ is exactly spectral graph sparsification, as studied by Spielman--Teng (SICOMP 2011). Although the techniques driving combinatorial and continuous sparsification have traditionally been largely disjoint, our main result is a single structural theorem governing the sparsifiability of arbitrary real-valued codes $C\subseteq\mathbb{R}_{\geq 0}^m$. The central parameter is \emph{continuous-valued non-redundancy} ($\mathrm{CVNRD}$), a real-valued analogue of non-redundancy that captures the largest approximately block-diagonal obstruction contained in $C$. Our theorem gives sparsifiers of size nearly-linear in $\mathrm{CVNRD}$, and shows that $\mathrm{CVNRD}$ is also a lower-bound obstruction for the broad class of coordinate-wise unbiased randomized sparsification schemes.

Monday, July 20 2026, 00:00

Solving Stackelberg Vertex Cover on trees using split and join

Authors: Dominik Scheder, Johannes Tantow

The Stackelberg Vertex Cover problem is a bilevel optimization problem with two players on a graph $G = (F \cup P, E)$ where each vertex from $F$ has a weight and the first player selects a price for each vertex in $P$. Afterwards, the second player finds a minimum vertex cover $X$ and the first player receives the set price for each vertex from $X \cap P$. The goal is to maximize the revenue of the first player. This problem was recently shown to be NP-complete for bipartite graphs while being solvable in linear time on paths. We present three new algorithms for solving Stackelberg Vertex Cover on certain kinds of trees: (1) a pseudo-polynomial algorithm working on general trees when all weights are integer, i.e., it is FPT with the maximum weight as a parameter; (2) a strongly polynomial algorithm for trees having the property that the least common ancestor of any two vertices from $P$ is again in $P$ (this case includes paths); and (3) an FPT-algorithm for trees, where the parameter is the maximum number $P$-vertices $v_i$ that an $F$-vertex $u$ can reach while using no other $P$-vertices. These algorithms are based on a lemma that allows us to split instances at a vertex $u$ into multiple sub-instances, which follows from LP duality and integrality of the vertex cover LP on bipartite graphs. The lemma requires that the minimum vertex covers of the sub-instances agree on $u$ (either all include $u$ or all don't). For this we introduce the concept of commitments. Finally, we show that the Stackelberg Vertex Cover problem with commitments is weakly NP-complete.

Authors: Dominik Scheder, Johannes Tantow

The Stackelberg Vertex Cover problem is a bilevel optimization problem with two players on a graph $G = (F \cup P, E)$ where each vertex from $F$ has a weight and the first player selects a price for each vertex in $P$. Afterwards, the second player finds a minimum vertex cover $X$ and the first player receives the set price for each vertex from $X \cap P$. The goal is to maximize the revenue of the first player. This problem was recently shown to be NP-complete for bipartite graphs while being solvable in linear time on paths. We present three new algorithms for solving Stackelberg Vertex Cover on certain kinds of trees: (1) a pseudo-polynomial algorithm working on general trees when all weights are integer, i.e., it is FPT with the maximum weight as a parameter; (2) a strongly polynomial algorithm for trees having the property that the least common ancestor of any two vertices from $P$ is again in $P$ (this case includes paths); and (3) an FPT-algorithm for trees, where the parameter is the maximum number $P$-vertices $v_i$ that an $F$-vertex $u$ can reach while using no other $P$-vertices. These algorithms are based on a lemma that allows us to split instances at a vertex $u$ into multiple sub-instances, which follows from LP duality and integrality of the vertex cover LP on bipartite graphs. The lemma requires that the minimum vertex covers of the sub-instances agree on $u$ (either all include $u$ or all don't). For this we introduce the concept of commitments. Finally, we show that the Stackelberg Vertex Cover problem with commitments is weakly NP-complete.

Monday, July 20 2026, 00:00

On the Role of Normalization in Binary Iterative Hard Thresholding for 1-bit Compressed Sensing

Authors: Arya Mazumdar, Prateeti Mukherjee

Binary Iterative Hard Thresholding (BIHT) is a simple, yet effective, greedy method for recovering a sparse vector from one-bit sign measurements. In its original form, BIHT performs a ``gradient-descent'' step, followed by hard thresholding. A convergence analysis of this algorithm was left open in the introductory work of [Jac+11] and has remained unresolved for over a decade, with subsequent sharp analyses studying a normalized variant instead, that additionally projects every iterate onto the unit sphere. This paper resolves that gap and characterizes when per-iteration normalization is algorithmically necessary. In the noiseless setting, we prove a universal, sample-optimal convergence theorem for the original BIHT algorithm. Specifically, with $\widetilde O(s/ε)$ measurements, a deterministic finite-time iterate has directional error at most $ε$, simultaneously for every $s$-sparse unit vector. This matches the optimal sample dependence achieved by normalized BIHT in prior work. Thus, in the noiseless regime, per-iterate normalization is unnecessary for optimal recovery. Under sign corruptions, we prove a sharp separation. If at most a $τ$ fraction of signs are flipped adversarially, then BIHT, without per-iterate normalization, still reaches the robust error floor at an early iterate with a matching $\widetilde O(s/ε)$ sample complexity rate as its normalized variant. This recovery, however, is not stable. We prove a scalar lower bound showing that any nontrivial corruption pattern, even one that involves only one flipped sign together with one clean sign, forces the iterates to oscillate indefinitely. Consequently, no general last-iterate convergence theorem can hold for BIHT under sign corruptions, while its normalized surrogate provably escapes this instance.

Authors: Arya Mazumdar, Prateeti Mukherjee

Binary Iterative Hard Thresholding (BIHT) is a simple, yet effective, greedy method for recovering a sparse vector from one-bit sign measurements. In its original form, BIHT performs a ``gradient-descent'' step, followed by hard thresholding. A convergence analysis of this algorithm was left open in the introductory work of [Jac+11] and has remained unresolved for over a decade, with subsequent sharp analyses studying a normalized variant instead, that additionally projects every iterate onto the unit sphere. This paper resolves that gap and characterizes when per-iteration normalization is algorithmically necessary. In the noiseless setting, we prove a universal, sample-optimal convergence theorem for the original BIHT algorithm. Specifically, with $\widetilde O(s/ε)$ measurements, a deterministic finite-time iterate has directional error at most $ε$, simultaneously for every $s$-sparse unit vector. This matches the optimal sample dependence achieved by normalized BIHT in prior work. Thus, in the noiseless regime, per-iterate normalization is unnecessary for optimal recovery. Under sign corruptions, we prove a sharp separation. If at most a $τ$ fraction of signs are flipped adversarially, then BIHT, without per-iterate normalization, still reaches the robust error floor at an early iterate with a matching $\widetilde O(s/ε)$ sample complexity rate as its normalized variant. This recovery, however, is not stable. We prove a scalar lower bound showing that any nontrivial corruption pattern, even one that involves only one flipped sign together with one clean sign, forces the iterates to oscillate indefinitely. Consequently, no general last-iterate convergence theorem can hold for BIHT under sign corruptions, while its normalized surrogate provably escapes this instance.

Monday, July 20 2026, 00:00

Publicly-Verifiable Certificates for Statistical Algorithms

Authors: Michael Ngo, Michael P. Kim

Following Goldwasser, Rothblum, Shafer, and Yehudayoff, who defined a framework for interactive proofs of learning [ITCS'21], we initiate the study of non-interactive proofs of learning. We define and study a new notion: Publicly-Verifiable Certificates of Statistical Validity (pvCSVs), which allow for public, distributionally-robust certification that the result of a learning algorithm is valid. In a pvCSV, a learner publishes a hypothesis $h$ and corresponding certificate $π$; then, any user, who holds a user-specific distribution, can read the pair $(h,π)$ and determine efficiently whether the hypothesis is valid according to the user-specific distribution. We construct pvCSVs in the context of Adaptive Statistical Query (SQ) Algorithms. To certify SQ algorithms that makes $k$ adaptive queries, we construct pvCSVs where the sample complexity scales with $O(\log k)$, whereas the sample complexity of the best learning algorithms scale with $\tilde{O}(\sqrt{k})$. More generally, we study proof systems for learning in the SQ model, demonstrating the model's strengths as well as its limitations.

Authors: Michael Ngo, Michael P. Kim

Following Goldwasser, Rothblum, Shafer, and Yehudayoff, who defined a framework for interactive proofs of learning [ITCS'21], we initiate the study of non-interactive proofs of learning. We define and study a new notion: Publicly-Verifiable Certificates of Statistical Validity (pvCSVs), which allow for public, distributionally-robust certification that the result of a learning algorithm is valid. In a pvCSV, a learner publishes a hypothesis $h$ and corresponding certificate $π$; then, any user, who holds a user-specific distribution, can read the pair $(h,π)$ and determine efficiently whether the hypothesis is valid according to the user-specific distribution. We construct pvCSVs in the context of Adaptive Statistical Query (SQ) Algorithms. To certify SQ algorithms that makes $k$ adaptive queries, we construct pvCSVs where the sample complexity scales with $O(\log k)$, whereas the sample complexity of the best learning algorithms scale with $\tilde{O}(\sqrt{k})$. More generally, we study proof systems for learning in the SQ model, demonstrating the model's strengths as well as its limitations.

Monday, July 20 2026, 00:00

Computing markings for fuzzy minimax nets over the Gödel structure

Authors: Linh Anh Nguyen

Fuzzy minimax nets were recently introduced as a tool for computing the greatest fuzzy bisimulation and simulation between two finite fuzzy graph-based structures. In this work, we provide an efficient algorithm for computing the greatest correct marking of a finite fuzzy minimax net over the Gödel structure. Its time complexity is linear in the number of nodes and positive edges in the input net. Building on this result, we derive the first algorithm with time complexity $O((m+n)n)$ for computing the greatest fuzzy directed simulation between two finite fuzzy graphs over the Gödel structure, where $n$ and $m$ denote the total numbers of vertices and positive edges, respectively, in the input graphs.

Authors: Linh Anh Nguyen

Fuzzy minimax nets were recently introduced as a tool for computing the greatest fuzzy bisimulation and simulation between two finite fuzzy graph-based structures. In this work, we provide an efficient algorithm for computing the greatest correct marking of a finite fuzzy minimax net over the Gödel structure. Its time complexity is linear in the number of nodes and positive edges in the input net. Building on this result, we derive the first algorithm with time complexity $O((m+n)n)$ for computing the greatest fuzzy directed simulation between two finite fuzzy graphs over the Gödel structure, where $n$ and $m$ denote the total numbers of vertices and positive edges, respectively, in the input graphs.

Monday, July 20 2026, 00:00

A Study of Parallelizable Alternatives to Dynamic Time Warping for Aligning Long Sequences

Authors: Daniel Yang, Thaxter Shaw, TJ Tsai

This article investigates several parallelizable alternatives to DTW for estimating the alignment between two long sequences. Whereas most previous work has focused on reducing the total computation and/or memory costs of DTW, our focus is instead on reducing wall clock time by utilizing common hardware like GPUs that are optimized for parallel processing. We propose and study four different parallelizable alignment algorithms: the first three algorithms compute approximations of DTW by breaking the pairwise cost matrix into rectangular regions and processing the regions in parallel, and the fourth algorithm computes an exact DTW alignment by processing the cost matrix along diagonals rather than rows or columns. We characterize the performance of our proposed alignment algorithms on an audio-audio alignment task, and we develop GPU-based implementations for the two best-performing algorithms, which we call weakly-ordered Segmental DTW (WSDTW) and Parallelized Diagonal DTW (ParDTW). Our experiments indicate that ParDTW is the most practical and useful of the four algorithms: it computes an exact DTW alignment and reduces runtime by 1.5 to 2 orders of magnitude on long sequences compared to current alternatives. We present a comprehensive evaluation and study of the alignment accuracy, runtime, and practical limitations of the proposed alignment algorithms.

Authors: Daniel Yang, Thaxter Shaw, TJ Tsai

This article investigates several parallelizable alternatives to DTW for estimating the alignment between two long sequences. Whereas most previous work has focused on reducing the total computation and/or memory costs of DTW, our focus is instead on reducing wall clock time by utilizing common hardware like GPUs that are optimized for parallel processing. We propose and study four different parallelizable alignment algorithms: the first three algorithms compute approximations of DTW by breaking the pairwise cost matrix into rectangular regions and processing the regions in parallel, and the fourth algorithm computes an exact DTW alignment by processing the cost matrix along diagonals rather than rows or columns. We characterize the performance of our proposed alignment algorithms on an audio-audio alignment task, and we develop GPU-based implementations for the two best-performing algorithms, which we call weakly-ordered Segmental DTW (WSDTW) and Parallelized Diagonal DTW (ParDTW). Our experiments indicate that ParDTW is the most practical and useful of the four algorithms: it computes an exact DTW alignment and reduces runtime by 1.5 to 2 orders of magnitude on long sequences compared to current alternatives. We present a comprehensive evaluation and study of the alignment accuracy, runtime, and practical limitations of the proposed alignment algorithms.

Monday, July 20 2026, 00:00

The k-Sum Lateness Problem on a Single Machine

Authors: Ricardo Arancibia-Castillo, José A. Soto

We study a single-machine scheduling problem in which each job $j$ has a nonnegative processing time $p_j\ge 0$ and a due date $d_j\in\mathbb{R}$. For a non-idling schedule $S$, let $C_j(S)$ be the completion time and let $L_j(S)=C_j(S)-d_j$ be the (possibly negative) lateness. The objective is to minimize the sum of the $k$ largest lateness values, interpolating between maximum lateness ($k=1$) and total lateness ($k=n$). We prove that the decision version is weakly NP-complete when $k$ is part of the input. For fixed $k$, we give an $O(k^2 n^{k+2})$ algorithm. As a consequence, we resolve a conjecture of Woeginger on the top-$k$ tardiness problem and obtain an $O(n^{k+2})$ algorithm for every fixed $k$. Our main structural result shows that there exists an optimal schedule that admits a block-island decomposition. Outside a suitable top-$k$ set, jobs form due-date blocks ordered by due date. Within each due-date class, the top-$k$ jobs form a suffix in lexicographic shortest-processing-time (SPT) order. This structure also yields an FPT algorithm parameterized by $D+k$, where $D$ is the number of distinct due dates. Independently, a standard dual representation of the top-$k$ objective reduces the problem to a family of total-tardiness instances with uniformly shifted due dates. For integral data, this gives a pseudopolynomial algorithm and a fully polynomial additive approximation scheme with error at most $\varepsilon M$, where $M=\max\{1,\max_j p_j,\max_j |d_j|\}$. The same route also gives XP algorithms for fixed $P$ and fixed $D$, where $P$ is the number of distinct processing times.

Authors: Ricardo Arancibia-Castillo, José A. Soto

We study a single-machine scheduling problem in which each job $j$ has a nonnegative processing time $p_j\ge 0$ and a due date $d_j\in\mathbb{R}$. For a non-idling schedule $S$, let $C_j(S)$ be the completion time and let $L_j(S)=C_j(S)-d_j$ be the (possibly negative) lateness. The objective is to minimize the sum of the $k$ largest lateness values, interpolating between maximum lateness ($k=1$) and total lateness ($k=n$). We prove that the decision version is weakly NP-complete when $k$ is part of the input. For fixed $k$, we give an $O(k^2 n^{k+2})$ algorithm. As a consequence, we resolve a conjecture of Woeginger on the top-$k$ tardiness problem and obtain an $O(n^{k+2})$ algorithm for every fixed $k$. Our main structural result shows that there exists an optimal schedule that admits a block-island decomposition. Outside a suitable top-$k$ set, jobs form due-date blocks ordered by due date. Within each due-date class, the top-$k$ jobs form a suffix in lexicographic shortest-processing-time (SPT) order. This structure also yields an FPT algorithm parameterized by $D+k$, where $D$ is the number of distinct due dates. Independently, a standard dual representation of the top-$k$ objective reduces the problem to a family of total-tardiness instances with uniformly shifted due dates. For integral data, this gives a pseudopolynomial algorithm and a fully polynomial additive approximation scheme with error at most $\varepsilon M$, where $M=\max\{1,\max_j p_j,\max_j |d_j|\}$. The same route also gives XP algorithms for fixed $P$ and fixed $D$, where $P$ is the number of distinct processing times.

Monday, July 20 2026, 00:00

The Multiple-Choice Matroid Secretary Problem

Authors: Matías Ortiz-Angel, José A. Soto

We introduce and study the multiple-choice matroid secretary problem, denoted $(J,κ)$-MSP. For rank-one matroids and $κ=\infty$, it reduces to the classical secretary problem with $J$ choices. Elements arrive in uniformly random order. Algorithms may keep a candidate pool $\mathrm{AUX}$ feasible in the $J$-fold union matroid $\mathcal{M}^{(J)}$ satisfying $|\mathrm{AUX}|\le κ\cdot\mathrm{rank}(\mathcal{M})$. Finally, one extracts the maximum-weight independent subset of $\mathrm{AUX}$ in $\mathcal{M}$. This model separates online storage from the final feasible solution. We study two multiple-choice implementations: multi-track algorithms (maintaining $J$ independent sets of $\mathcal{M}$) and union-based algorithms (maintaining the pool directly in $\mathcal{M}^{(J)}$). Our main result is an exact optimal algorithm for transversal matroids in the uncapacitated $(J,\infty)$ setting. For fixed $J$, its probability-competitive ratio equals the optimal success probability of the classical $J$-choice secretary problem. Thus, rank-one instances are the worst case for the whole transversal class, and the optimal guarantee converges exponentially fast to $1$ as $J$ grows. We also analyze a simple single-threshold routing algorithm for capacitated transversal matroids with local capacities $b$ and global capacity $κ\cdot\mathrm{rank}(\mathcal{M})$. Its analysis provides explicit finite-parameter bounds and asymptotic formulas, showing how finite-rank loss caused by global capacity decays, and how $b$, $J$, and $κ$ interact. Finally, we instantiate the multi-track approach for $k$-column-sparse matroids (guarantee $1-O(e^{-J/(ke)})$) and the union-based approach for laminar matroids (guarantee $1-O(e^{-J/e})$).

Authors: Matías Ortiz-Angel, José A. Soto

We introduce and study the multiple-choice matroid secretary problem, denoted $(J,κ)$-MSP. For rank-one matroids and $κ=\infty$, it reduces to the classical secretary problem with $J$ choices. Elements arrive in uniformly random order. Algorithms may keep a candidate pool $\mathrm{AUX}$ feasible in the $J$-fold union matroid $\mathcal{M}^{(J)}$ satisfying $|\mathrm{AUX}|\le κ\cdot\mathrm{rank}(\mathcal{M})$. Finally, one extracts the maximum-weight independent subset of $\mathrm{AUX}$ in $\mathcal{M}$. This model separates online storage from the final feasible solution. We study two multiple-choice implementations: multi-track algorithms (maintaining $J$ independent sets of $\mathcal{M}$) and union-based algorithms (maintaining the pool directly in $\mathcal{M}^{(J)}$). Our main result is an exact optimal algorithm for transversal matroids in the uncapacitated $(J,\infty)$ setting. For fixed $J$, its probability-competitive ratio equals the optimal success probability of the classical $J$-choice secretary problem. Thus, rank-one instances are the worst case for the whole transversal class, and the optimal guarantee converges exponentially fast to $1$ as $J$ grows. We also analyze a simple single-threshold routing algorithm for capacitated transversal matroids with local capacities $b$ and global capacity $κ\cdot\mathrm{rank}(\mathcal{M})$. Its analysis provides explicit finite-parameter bounds and asymptotic formulas, showing how finite-rank loss caused by global capacity decays, and how $b$, $J$, and $κ$ interact. Finally, we instantiate the multi-track approach for $k$-column-sparse matroids (guarantee $1-O(e^{-J/(ke)})$) and the union-based approach for laminar matroids (guarantee $1-O(e^{-J/e})$).

Monday, July 20 2026, 00:00

Bipartite Perfect Matching in Deterministic NC

from Computational Complexity

Nutan Limaye and Thore Husfeldt guest post on the new deterministic parallel algorithm for bipartite perfect matching by Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj and Thomas Thierauf.
The post will try to explain three main things about the result. What is the result? Why is it important? And finally, how did the authors prove it?

We will assume that the reader is an undergraduate student in CS (i.e., the reader knows basics of discrete mathematics, linear algebra, and algorithm design).
What? The main result can be stated in just one line! Bipartite Perfect Matching can be solved in NC. Let's now understand what each of these terms means.

Bipartite Perfect Matching. A bipartite graph has two disjoint sets of vertices, say $L, R$, and any edge connects one vertex of $L$ and one vertex of $R$. A matching in a graph is a subset of edges such that no two edges have a vertex in common. A perfect matching is a matching in which each vertex of the graph appears exactly once. Let's take the following example. Here is a bipartite graph.
♦It has two perfect matchings. One is $\{(v_1, w_1), (v_2, w_3), (v_3, w_2)\}$ and the other is $\{(v_1, w_2), (v_2, w_1), (v_3, w_3)\}$.

We will assume that the graph is given as a matrix, known as the bi-adjacency matrix. The bi-adjacency matrix of a bipartite graph has $A_{ij} = 1$ whenever $(i,j)\in E(G)$. For our running example, here is how we will receive the input: \[ A_G = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}\,. \] Now, we are ready to define the Bipartite Perfect Matching (BPM for short) problem. Given a bipartite graph as a bi-adjacency matrix, check whether there is a perfect matching in the graph or not.

NC. The next term we need to explain is NC. It is a complexity class named after Nick Pippenger, which consists of a class of problems solvable by parallel algorithms that use polynomially many processors and have parallel running time that is considerably smaller than polynomial. More specifically, the parallel running time is polylogarithmic. You can simply think of this as a class of problems that have efficient parallel algorithms.

Let us begin with a simple example. Suppose we want to multiply $n$ numbers, $x_1,\ldots,x_n$. One approach is to first multiply $x_1$ and $x_2$, then multiply the result by $x_3$, and continue in this way until we reach $x_n$. This is a sequential algorithm.

A parallel algorithm proceeds differently. It first pairs up the numbers and multiplies all pairs simultaneously. This produces $n/2$ numbers, giving a new instance of the same problem with only half as many inputs. We then repeat the process: pair up the remaining numbers, multiply each pair in parallel, and continue until only one number remains.♦ Consider another example. Given an integer matrix $A$, suppose we wish to compute its determinant; we refer to this as the DET problem. Sequentially, the determinant can be computed efficiently using Gaussian elimination. More surprisingly—and this is far from obvious—the problem also admits an efficient parallel algorithm (DET $\in$ NC). (Here are some references: Csanky's paper, Berkowitz' paper.) We will use this statement as a black box many times below.
So, overall the new result states that given a bi-adjacency matrix of a graph, checking whether it has a perfect matching or not can be solved efficiently by a parallel algorithm. Why it matters: TL;DR

BPM is an extremely well-studied graph problem because it arises naturally in many practical scenarios. The problem has been a focus of intense research for more than 5 decades. (See an excellent introduction to matching and related problems here and here.)
Derandomization is a central problem in theoretical computer science. (For a deep dive into derandomization see this or this survey.) It asks whether randomness truly adds computational power or merely provides a convenient shortcut. Bipartite Perfect Matching has long been known to admit a randomized NC algorithm. Finding a deterministic NC algorithm for the problem therefore fits naturally into the broader derandomization program. In fact, bipartite perfect matching is one of the most natural and simply stated problems in this setting. Its resolution provides a particularly striking example of randomness being removed from an efficient parallel algorithm.

How did the authors solve the problem? Polynomial-time algorithms for this problem---Kuhn's algorithm, Hopcroft--Karp, or matching-via-max-flow with Ford--Fulkerson---are a staple of undergraduate algorithms courses and have been known since the 1960s. They work by repeatedly finding an augmenting path: a path between two unmatched vertices that alternates between edges outside and inside the current matching; augmenting along it grows the matching by one edge (Berge's theorem)---an inherently sequential process. The matching that admits an augmenting path at step $k$ depends on exactly which edges were chosen at steps $1$ through $k-1$; there's no obvious way to precompute or guess ahead of time which augmentations will happen. Thus, the classical algorithms for the problem are sequential.

The randomized NC algorithm for BPM. As a warm up, let us see the randomized NC algorithm for BPM. The algorithm is as follows.

Start with the given bi-adjacency matrix $A_G$ of the bipartite graph $G$.
Replace each $1$ entry by a random number from the range $[1, 100n]$, where $n$ is the number of vertices in $G$. This creates a new matrix $A_G'$.
Compute DET of $A_G'$.
If it is non-zero, then accept else reject.

Using the fact that DET $\in$ NC as a black box, it is straightforward to see that the algorithm above runs in randomized NC. But why is it correct? Establishing correctness requires a connection between determinants and perfect matchings. At a very high level, the terms of the determinant of $A_G'$ are in one-to-one correspondence with the perfect matchings of $G$. Thus computing the determinant leads to checking the existence of a matching. For more rigorous details about this connection, we refer the reader to Lovász' paper.

The next question is whether the randomness can be removed. Informally, the randomization is needed to prevent cancellations in the determinant. Recall that computing a determinant involves both additions and subtractions. Thus, even if the graph has a perfect matching, different terms in the determinant expansion may cancel, causing the determinant to vanish. This would make the algorithm incorrect.

To avoid this, each nonzero entry is replaced by a random value. With high probability, the resulting determinant is nonzero whenever a perfect matching exists. The challenge, then, is to achieve the same effect deterministically: how can we prevent these cancellations without relying on randomness?

The first major breakthrough came about a decade ago, in work by Fenner, Gurjar, and Thierauf -- notice the overlap with the authors of the new result. Their approach traded randomness for parallel resources: they showed that the algorithm could indeed be derandomized, but only by allowing many more processors. Specifically, their algorithm required quasi-polynomially many processors. Recall that a polynomial function grows as $n^c$ for some constant $c$, whereas a quasi-polynomial function may grow as $n^{\log n}$. In the latter case, the exponent of $n$ is itself a growing function of $n$, rather than a fixed constant.
The new approach Let us reiterate the question we posed after reviewing the randomized NC algorithm.

How can we prevent these cancellations without relying on randomness?

The authors say, the answer lies in coding theory! At a very high level, the algorithm can be described as follows.

Start with the given bi-adjacency matrix $A_G$ of the bipartite graph $G$.
Replace each $1$ entry in location $(i,j)$ with a fixed thin and tall matrix $V_{ij}$ to produce a new matrix $A_G'$.
Compute DET of $A_G'$.
If it is non-zero, then accept else reject.

If you feed this algorithm to a computer, it will complain: Cannot compute DET because AG' is not a square matrix. But this is not a big deal. One could simply say, check whether it has full rank (either row-rank or column rank, whichever is smaller). This problem is also solvable in NC.

However, instead of replacing the original adjacency matrix, they first create an intermediate matrix $\widehat{A_G'}$ from $A_G$ by padding $A_G$ with $n(n-1)$ columns of unit vectors. For our example, \[ \widehat{A_G'} = \begin{bmatrix} 1 & 1 & 0 \quad & 1 & 1 \,& 0 & 0\, & 0& 0\\ 1 & 0 & 1 \quad & 0 & 0 \,& 1 & 1\, & 0& 0\\ 0 & 1 & 1 \quad & 0 & 0 \,& 0 & 0\, & 1& 1\\ \end{bmatrix} \] Now, in $\widehat{A_G'}$, replace each non-zero entry $(i,j)$ with a thin and tall matrix $V_{ij}$ to obtain $\widehat{A_G}$. The matrix dimension and the padding length are chosen such that the overall matrix $\widehat{A_G}$ becomes almost square. It now has slightly fewer rows than columns.

Note that the entire algorithm is deterministic. The main work is to show that this deterministic replacement works. Specifically, the authors show that
$G$ has a perfect matching if and only if $\widehat{A_G}$ has full row rank.
While we don't plan to present the proof here, the goal is to give you a high-level outline of the approach. In order to do that, let us first see what these matrices $V_{ij}$ look like. This is exactly where the connection to coding theory comes up! Each matrix is indeed a Folded Vandermonde matrix, which comes up in folded Reed-Solomon codes and subspace designs.

Fix $\gamma\in \mathbb{F}$ that has a large order, i.e. it needs to be raised to a very large power before it circles back to itself. (This is relevant when we are over finite fields.) For parameters $r,D\in \mathbb{N}$, the folded Vandermonde matrix is the $D\times r$ matrix whose $ij$th entry is $\left(\alpha\gamma^{(j-1)}\right)^{i-1}$: \[ V(\alpha_{}, \gamma) = \begin{bmatrix} 1 & 1 & \cdots & 1 \\ \alpha_{} & \alpha_{}\gamma & \cdots & \alpha_{}\gamma^{r-1} \\ \alpha_{}^2 & (\alpha_{}\gamma)^2 & \cdots & (\alpha_{}\gamma^{r-1})^2 \\ \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ \alpha_{}^{D-1} & (\alpha_{}\gamma)^{D-1} & \cdots & (\alpha_{}\gamma^{r-1})^{D-1} \\ \end{bmatrix} \] The parameters $r,D$ are chosen such that the matrix is thin and tall. For our example $G$ with $n=3$, the matrix ends up as having $D=n(n^3+1-n)=75$ rows and $r=n^3+1=28$ columns. To obtain $\widehat{A_G}$ from $\widehat{A_G'}$, replace all the $1$ entries from each column $j$ of $\widehat{A_G'}$ by $V(\alpha_j, \gamma)$, where all $\alpha$s are distinct.
Swastik Kopparty and Shubhangi Saraf recently announced a variation of this approach.

How does the proof proceed from here? One direction of the proof is quite easy. When there is no perfect matching, it is quite easy to see that the matrix cannot achieve full row rank. This is because, when there is no perfect matching, then by Hall's Theorem we know that there is a Hall blocker. That is, there is a set $S \subseteq L$ such that if you look at the neighbours of $S$, denoted as $N(S) \subseteq R$, then $|S| > |N(S)|$. This deficit in the size of the neighbour set for one of the subsets in $L$ suffices to observe that the number of columns with nonzero entries is strictly less than the number of rows. Thus, one cannot have full row rank.

For the other direction, things are more intricate. The proof proceeds by proving the contrapositive. They show that if the row rank of the matrix is not full, then there will be a subset $S \subseteq L$ such that $|S| > |N(S)|$.

To prove this, they start with a vector $v$ that certifies the linear dependence between the rows of $\widehat{A_G}$. This vector is viewed as a tuple of $n$ vectors of dimension $D$ each. Now, they prove two things about it.

First, they show that the non-zero elements of the tuple, say $\mathcal{P}$, are linearly independent vectors.
Second, they view these vectors as polynomials and consider the span of these linearly independent polynomials. They count the folded roots of the span of $\mathcal{P}$ in two ways to derive the fact that $|S| > |N(S)|$.

Both the parts above invoke a Lemma due to Guruswami and Kopparty which proves an upper bound on the number of folded roots of a linear space of polynomials.Conclusion Here are some final thoughts.

The paper proves many more results. The proofs are self-contained and well-written. So, I highly encourage you to read it.
Venkat Guruswami gave a keynote at ICALP 2026, where he explained how one can view the idea of subspace designs as a derandomization tool. He explained subspace designs by analogy with the more familiar notion of hash functions: subspace designs play for linear spaces a role similar to that played by hash functions for sets. He then sketched the BPM in NC proof from this perspective.
One big open problem is resolved by humans. Going forward, will we have such only-human proofs? In fact, the authors first developed an algorithm for the problem, then used AI to help adapt the underlying idea to a broader setting. That is, they used AI to extend human ideas. Currently, this seems to be a trend in TCS. What can we expect going forward?

By Lance Fortnow

Nutan Limaye and Thore Husfeldt guest post on the new deterministic parallel algorithm for bipartite perfect matching by Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj and Thomas Thierauf.

The post will try to explain three main things about the result. What is the result? Why is it important? And finally, how did the authors prove it?

We will assume that the reader is an undergraduate student in CS (i.e., the reader knows basics of discrete mathematics, linear algebra, and algorithm design).
What? The main result can be stated in just one line! Bipartite Perfect Matching can be solved in NC. Let's now understand what each of these terms means.

Bipartite Perfect Matching. A bipartite graph has two disjoint sets of vertices, say $L, R$, and any edge connects one vertex of $L$ and one vertex of $R$. A matching in a graph is a subset of edges such that no two edges have a vertex in common. A perfect matching is a matching in which each vertex of the graph appears exactly once. Let's take the following example. Here is a bipartite graph.

It has two perfect matchings. One is $\{(v_1, w_1), (v_2, w_3), (v_3, w_2)\}$ and the other is $\{(v_1, w_2), (v_2, w_1), (v_3, w_3)\}$.

We will assume that the graph is given as a matrix, known as the bi-adjacency matrix. The bi-adjacency matrix of a bipartite graph has $A_{ij} = 1$ whenever $(i,j)\in E(G)$. For our running example, here is how we will receive the input: \[ A_G = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}\,. \] Now, we are ready to define the Bipartite Perfect Matching (BPM for short) problem. Given a bipartite graph as a bi-adjacency matrix, check whether there is a perfect matching in the graph or not.

NC. The next term we need to explain is NC. It is a complexity class named after Nick Pippenger, which consists of a class of problems solvable by parallel algorithms that use polynomially many processors and have parallel running time that is considerably smaller than polynomial. More specifically, the parallel running time is polylogarithmic. You can simply think of this as a class of problems that have efficient parallel algorithms.

Let us begin with a simple example. Suppose we want to multiply $n$ numbers, $x_1,\ldots,x_n$. One approach is to first multiply $x_1$ and $x_2$, then multiply the result by $x_3$, and continue in this way until we reach $x_n$. This is a sequential algorithm.

A parallel algorithm proceeds differently. It first pairs up the numbers and multiplies all pairs simultaneously. This produces $n/2$ numbers, giving a new instance of the same problem with only half as many inputs. We then repeat the process: pair up the remaining numbers, multiply each pair in parallel, and continue until only one number remains.

Consider another example. Given an integer matrix $A$, suppose we wish to compute its determinant; we refer to this as the DET problem. Sequentially, the determinant can be computed efficiently using Gaussian elimination. More surprisingly—and this is far from obvious—the problem also admits an efficient parallel algorithm (DET $\in$ NC). (Here are some references: Csanky's paper, Berkowitz' paper.) We will use this statement as a black box many times below.

So, overall the new result states that given a bi-adjacency matrix of a graph, checking whether it has a perfect matching or not can be solved efficiently by a parallel algorithm.

Why it matters: TL;DR

BPM is an extremely well-studied graph problem because it arises naturally in many practical scenarios. The problem has been a focus of intense research for more than 5 decades. (See an excellent introduction to matching and related problems here and here.)
Derandomization is a central problem in theoretical computer science. (For a deep dive into derandomization see this or this survey.) It asks whether randomness truly adds computational power or merely provides a convenient shortcut. Bipartite Perfect Matching has long been known to admit a randomized NC algorithm. Finding a deterministic NC algorithm for the problem therefore fits naturally into the broader derandomization program. In fact, bipartite perfect matching is one of the most natural and simply stated problems in this setting. Its resolution provides a particularly striking example of randomness being removed from an efficient parallel algorithm.

How did the authors solve the problem? Polynomial-time algorithms for this problem---Kuhn's algorithm, Hopcroft--Karp, or matching-via-max-flow with Ford--Fulkerson---are a staple of undergraduate algorithms courses and have been known since the 1960s. They work by repeatedly finding an augmenting path: a path between two unmatched vertices that alternates between edges outside and inside the current matching; augmenting along it grows the matching by one edge (Berge's theorem)---an inherently sequential process. The matching that admits an augmenting path at step $k$ depends on exactly which edges were chosen at steps $1$ through $k-1$; there's no obvious way to precompute or guess ahead of time which augmentations will happen. Thus, the classical algorithms for the problem are sequential.

The randomized NC algorithm for BPM. As a warm up, let us see the randomized NC algorithm for BPM. The algorithm is as follows.

Start with the given bi-adjacency matrix $A_G$ of the bipartite graph $G$.
Replace each $1$ entry by a random number from the range $[1, 100n]$, where $n$ is the number of vertices in $G$. This creates a new matrix $A_G'$.
Compute DET of $A_G'$.
If it is non-zero, then accept else reject.

Using the fact that DET $\in$ NC as a black box, it is straightforward to see that the algorithm above runs in randomized NC. But why is it correct? Establishing correctness requires a connection between determinants and perfect matchings. At a very high level, the terms of the determinant of $A_G'$ are in one-to-one correspondence with the perfect matchings of $G$. Thus computing the determinant leads to checking the existence of a matching. For more rigorous details about this connection, we refer the reader to Lovász' paper.

The next question is whether the randomness can be removed. Informally, the randomization is needed to prevent cancellations in the determinant. Recall that computing a determinant involves both additions and subtractions. Thus, even if the graph has a perfect matching, different terms in the determinant expansion may cancel, causing the determinant to vanish. This would make the algorithm incorrect.

To avoid this, each nonzero entry is replaced by a random value. With high probability, the resulting determinant is nonzero whenever a perfect matching exists. The challenge, then, is to achieve the same effect deterministically: how can we prevent these cancellations without relying on randomness?

The first major breakthrough came about a decade ago, in work by Fenner, Gurjar, and Thierauf -- notice the overlap with the authors of the new result. Their approach traded randomness for parallel resources: they showed that the algorithm could indeed be derandomized, but only by allowing many more processors. Specifically, their algorithm required quasi-polynomially many processors. Recall that a polynomial function grows as $n^c$ for some constant $c$, whereas a quasi-polynomial function may grow as $n^{\log n}$. In the latter case, the exponent of $n$ is itself a growing function of $n$, rather than a fixed constant.
The new approach Let us reiterate the question we posed after reviewing the randomized NC algorithm.

How can we prevent these cancellations without relying on randomness?

The authors say, the answer lies in coding theory! At a very high level, the algorithm can be described as follows.

Start with the given bi-adjacency matrix $A_G$ of the bipartite graph $G$.
Replace each $1$ entry in location $(i,j)$ with a fixed thin and tall matrix $V_{ij}$ to produce a new matrix $A_G'$.
Compute DET of $A_G'$.
If it is non-zero, then accept else reject.

If you feed this algorithm to a computer, it will complain: Cannot compute DET because A_G' is not a square matrix. But this is not a big deal. One could simply say, check whether it has full rank (either row-rank or column rank, whichever is smaller). This problem is also solvable in NC.

However, instead of replacing the original adjacency matrix, they first create an intermediate matrix $\widehat{A_G'}$ from $A_G$ by padding $A_G$ with $n(n-1)$ columns of unit vectors. For our example, \[ \widehat{A_G'} = \begin{bmatrix} 1 & 1 & 0 \quad & 1 & 1 \,& 0 & 0\, & 0& 0\\ 1 & 0 & 1 \quad & 0 & 0 \,& 1 & 1\, & 0& 0\\ 0 & 1 & 1 \quad & 0 & 0 \,& 0 & 0\, & 1& 1\\ \end{bmatrix} \] Now, in $\widehat{A_G'}$, replace each non-zero entry $(i,j)$ with a thin and tall matrix $V_{ij}$ to obtain $\widehat{A_G}$. The matrix dimension and the padding length are chosen such that the overall matrix $\widehat{A_G}$ becomes almost square. It now has slightly fewer rows than columns.

Note that the entire algorithm is deterministic. The main work is to show that this deterministic replacement works. Specifically, the authors show that

$G$ has a perfect matching if and only if $\widehat{A_G}$ has full row rank.

While we don't plan to present the proof here, the goal is to give you a high-level outline of the approach. In order to do that, let us first see what these matrices $V_{ij}$ look like. This is exactly where the connection to coding theory comes up! Each matrix is indeed a Folded Vandermonde matrix, which comes up in folded Reed-Solomon codes and subspace designs.

Fix $\gamma\in \mathbb{F}$ that has a large order, i.e. it needs to be raised to a very large power before it circles back to itself. (This is relevant when we are over finite fields.) For parameters $r,D\in \mathbb{N}$, the folded Vandermonde matrix is the $D\times r$ matrix whose $ij$th entry is $\left(\alpha\gamma^{(j-1)}\right)^{i-1}$: \[ V(\alpha_{}, \gamma) = \begin{bmatrix} 1 & 1 & \cdots & 1 \\ \alpha_{} & \alpha_{}\gamma & \cdots & \alpha_{}\gamma^{r-1} \\ \alpha_{}^2 & (\alpha_{}\gamma)^2 & \cdots & (\alpha_{}\gamma^{r-1})^2 \\ \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ \alpha_{}^{D-1} & (\alpha_{}\gamma)^{D-1} & \cdots & (\alpha_{}\gamma^{r-1})^{D-1} \\ \end{bmatrix} \] The parameters $r,D$ are chosen such that the matrix is thin and tall. For our example $G$ with $n=3$, the matrix ends up as having $D=n(n^3+1-n)=75$ rows and $r=n^3+1=28$ columns. To obtain $\widehat{A_G}$ from $\widehat{A_G'}$, replace all the $1$ entries from each column $j$ of $\widehat{A_G'}$ by $V(\alpha_j, \gamma)$, where all $\alpha$s are distinct.

Swastik Kopparty and Shubhangi Saraf recently announced a variation of this approach.

How does the proof proceed from here? One direction of the proof is quite easy. When there is no perfect matching, it is quite easy to see that the matrix cannot achieve full row rank. This is because, when there is no perfect matching, then by Hall's Theorem we know that there is a Hall blocker. That is, there is a set $S \subseteq L$ such that if you look at the neighbours of $S$, denoted as $N(S) \subseteq R$, then $|S| > |N(S)|$. This deficit in the size of the neighbour set for one of the subsets in $L$ suffices to observe that the number of columns with nonzero entries is strictly less than the number of rows. Thus, one cannot have full row rank.

For the other direction, things are more intricate. The proof proceeds by proving the contrapositive. They show that if the row rank of the matrix is not full, then there will be a subset $S \subseteq L$ such that $|S| > |N(S)|$.

To prove this, they start with a vector $v$ that certifies the linear dependence between the rows of $\widehat{A_G}$. This vector is viewed as a tuple of $n$ vectors of dimension $D$ each. Now, they prove two things about it.

First, they show that the non-zero elements of the tuple, say $\mathcal{P}$, are linearly independent vectors.
Second, they view these vectors as polynomials and consider the span of these linearly independent polynomials. They count the folded roots of the span of $\mathcal{P}$ in two ways to derive the fact that $|S| > |N(S)|$.

Both the parts above invoke a Lemma due to Guruswami and Kopparty which proves an upper bound on the number of folded roots of a linear space of polynomials.

Conclusion Here are some final thoughts.

The paper proves many more results. The proofs are self-contained and well-written. So, I highly encourage you to read it.
Venkat Guruswami gave a keynote at ICALP 2026, where he explained how one can view the idea of subspace designs as a derandomization tool. He explained subspace designs by analogy with the more familiar notion of hash functions: subspace designs play for linear spaces a role similar to that played by hash functions for sets. He then sketched the BPM in NC proof from this perspective.
One big open problem is resolved by humans. Going forward, will we have such only-human proofs? In fact, the authors first developed an algorithm for the problem, then used AI to help adapt the underlying idea to a broader setting. That is, they used AI to extend human ideas. Currently, this seems to be a trend in TCS. What can we expect going forward?

By Lance Fortnow

Sunday, July 19 2026, 14:27

Integer complexity and cographs

from David Eppstein

The integer complexity of a number $n$ is the minimum number of ones needed to express $n$ as a parenthesized combination of sums and products of ones. For instance, 10 has complexity 7 as it can be expressed using seven ones, but not fewer:

\[10 = (1+1+1)(1+1+1)+1.\]

The largest number with complexity $k$ can be obtained by breaking up the sequence of $k$ ones into subsequences of two and three ones (with as many threes as possible) and multiplying. For instance, for ten ones, you can’t do this with three groups of three (because you get an ungrouped one left over) but you can with two, giving

\[(1+1+1)(1+1+1)(1+1)(1+1)=36.\]

While looking at the integer complexity article on Wikipedia today, it occurred to me that I had seen the same formula for the maximum complexity before. It is the upper bound on the number of maximal cliques in an $n$-vertex graph. This upper bound was proven in 1965 by Moon and Moser, and in fact the OEIS sequence for the largest number with complexity $k$ cites Moon & Moser but without an explanation.

It turns out there’s a stronger connection, obtained through a class of graphs called cographs. These are the graphs that can be obtained from a single-vertex graph by operations that take the disjoint union of two smaller cographs, or that complement another cograph (replacing edges by non-edges and vice versa). The resulting structure can be represented by a “cotree”, a rooted tree with its leaves labeled by vertices and its interior nodes labeled by 0 or 1, with 0 meaning to take the disjoint union of the subtree graphs and 1 meaning to complement the disjoint union. Adjacent interior nodes with the same label can be merged, giving a unique cotree representation for which the labels alternate on root-to-leaf paths.

A cotree and the corresponding cograph

Every maximal clique in a cograph can be obtained recursively through its cotree. At a 1-node, choose a maximal clique in each child, recursively. And at a 0-node, choose a maximal clique in exactly one child, recursively. It follows that the number of maximal cliques is obtained by reinterpreting the cotree as an expression tree, multiplying the numbers of maximal cliques at the children of a 1-node, or by summing the numbers of maximal cliques at a 0-node. Each leaf node has only one maximal clique, itself. So for instance if I take the cotree above and interpret it as an expression tree with a sum for each 0-node and a product for each 1-node I get the expression

\[(a+bc+de)(f+g)\]

which (substituting one for each variable) evaluates to six. Through this correspondence, the integer complexity of $n$ is exactly the minimum number of vertices of a cograph that has $n$ maximal cliques.

This naturally raises the question: what is the minimum number of vertices in a graph that has $n$ maximal cliques, without requiring it to be a cograph? Is it ever smaller than the integer complexity? Yes! According to OEIS, the integer complexity of 23 is 11, as obtained for instance through the expression

\[\bigl((1+1+1+1+1)(1+1)+1\bigr)(1+1)+1.\]

But there is a 10-vertex graph with 23 maximal cliques: Just remove any two edges from the complete bipartite graph $K_{5,5}$. So the largest numbers with given integer complexity can be obtained by clique-counting in arbitrary graphs, and the integer complexity can always be obtained by clique-counting in cographs, but some integer complexities are not the same as what you get by clique-counting in arbitrary graphs.

(Discuss on Mastodon)

By David Eppstein

Sunday, July 19 2026, 12:38

TR26-122 | Complexity of the Graph Homomorphism Problem w.r.t. Degeneracy | Nikolai Chukhin, Grigorii Braulov, Alexander Kulikov, Ivan Mihajlin

from ECCC Papers

The graph homomorphism problem HOM is: given an $n$-vertex source graph $G$ and an $h$-vertex target graph $H$, is there a mapping from $V(G)$ to $V(H)$ that preserves edges? A straightforward brute-force algorithm for HOM has running time $O(2^{n \log h})$ and it is known that, under ETH, there are no $2^{o(n \log h)}$ algorithms. In recent years, less restrictive graph parameters $p$ have been identified that allow one to solve HOM in time $p(H)^{O(n)}$. Examples include treewidth, maximum degree, and track number. On the other hand, it is known that the chromatic number parameter is too small: under ETH, HOM cannot be solved in time $\chi(H)^{O(n)}$. We study the complexity of HOM in terms of the degeneracy of $H$. This is perhaps the most natural unresolved graph parameter between the known algorithmic and hardness regimes: on the one hand, each of bounded treewidth, bounded maximum degree, and bounded track number implies bounded degeneracy; on the other hand, bounded degeneracy implies bounded chromatic number. Our results show that, at the same time, the influence of degeneracy of $H$ on the complexity of HOM differs significantly from that of the previously studied parameters. We show that, under ETH, there is no $2^{o(degen(H) n)}$ algorithm for any value of $degen(H)$ as a function of $n$. We also show that bounded degeneracy alone does not make target size benign: even targets with $degen(H)$ at most $2$ and quasi-polynomial size force $n^{\Omega(n)}$-scale hardness. Finally, we introduce a no-compression barrier that explains why the known fine-grained lower bounds for sparse $2$-CSP are not tight under ETH. Moreover, it shows that substantially stronger lower bounds for polynomial-target degeneracy are unlikely to follow from standard reductions from sparse $3$-SAT.

Sunday, July 19 2026, 04:25

TR26-121 | New and Improved Concrete Lower Bounds for Orthogonal Vectors | Tameem Choudhury, Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan

from ECCC Papers

The Orthogonal Vectors Problem (OV$_{n,d}$) takes as input two sets $A,B$ each containing $n$ $d$-dimensional Boolean vectors, and outputs $1$ if and only if there exists $a \in A$ and $b \in B$ such that $a$ and $b$ are orthogonal. The OV conjecture states that for every $\varepsilon > 0$, there exists a constant $c \geq 1$ such that there is no algorithm deciding OV$_{n,d}$ for $d = c \log n$ with running time $O(n^{2-\varepsilon})$. The analogous $k$-OV conjecture hypothesizes a lower bound of $n^{k-\epsilon}$ for the same problem with $k$ sets. We prove these results and variants unconditionally in concrete computational models. We study a natural monotone version of the $k$-OV conjecture and show that it holds for monotone circuits and constant-depth (not necessarily monotone) circuits when $d = n^{\Omega(1)}.$ We show that the monotone version of the OV conjecture holds for monotone circuits. More formally, we show that for every $\epsilon > 0$, there exists $c$ such that any monotone circuit family computing the negation of OV$_{n,d}$ with $d=c\log n$ must have size $\Omega(n^{2-\epsilon})$. We also prove stronger Boolean formula and branching program lower bounds for OV$_{n,d}$, strengthening a previous result of Kane and Williams (ITCS 2019). In particular, our Boolean formula lower bound of $\Omega(n^2 d)$ is tight up to constant factors.

Sunday, July 19 2026, 04:24

NISQ and quantum supremacy did not fail

from Scott Aaronson

A week ago, a philosopher named Amit Hagar put out a preprint entitled The NISQ Trap: Eight Years of Demonstrations the Hardware was Built to Lose. Here’s the abstract: With a single clear exception, every NISQ-era flagship demonstration of ‘quantum advantage’ has, within eighteen months of its announcement, been classically reproduced, shown to rest on […]

A week ago, a philosopher named Amit Hagar put out a preprint entitled The NISQ Trap: Eight Years of Demonstrations the Hardware was Built to Lose. Here’s the abstract:

With a single clear exception, every NISQ-era flagship demonstration of ‘quantum advantage’ has, within eighteen months of its announcement, been classically reproduced, shown to rest on classically tractable structure, or closed by a simulability theorem. Six theoretical results from 2024 through April 2026 explain the pattern: the regions of circuit-space NISQ hardware can run with sufficient fidelity coincide with the regions classical algorithms compress efficiently, because the features that admit one (low effective depth, strong algebraic structure, geometric locality) are the features that admit the other. This reading dates the NISQ programme from its 2018 articulation as an interim retreat from the unmet conditions of the 1996 threshold theorems, characterises the eight years that followed as a closed loop in which the demonstrations the hardware could run were drawn from regions classical methods could already reach, and locates the exit from the loop where the threshold theorems originally located it: in fault tolerance. The empirical pattern could in principle break with a demonstration that escapes the current simulability results. After eight years and more than thirty advantage-class announcements, the burden of producing such a demonstration falls to the defenders of NISQ.

You can also read some debates about the paper on SciRate here. I think it’s fair to say that the paper is purely polemical, without new ideas, and Pangram agrees with my suspicion (and that of a SciRate commenter) that significant portions of it are AI-generated.

Nevertheless, the basic thesis—that quantum supremacy in the NISQ (Noisy Intermediate Scale Quantum computing) era has been a failure, or even an example of pathological science—seems surprisingly widely shared, along with the opposite thesis that quantum computing already gives oodles of useful advantages for optimization and finance.

So it seems worth stating for the record that I have an extremely different view. I would say:

Sampling-based quantum supremacy experiments, including those based on Random Circuit Sampling and BosonSampling, passed the point about two years ago where, absent a breakthrough in classical algorithms, they quite clearly are beating what can easily be simulated on any existing classical computer. Hagar seems to claim that these experiments have been killed by the October 2025 paper Classical simulation of noisy random circuits from exponential decay of correlation, but he ignores that the algorithm from that paper still needs time that’s exponential in the circuit depth (see Theorem 2).
Indeed, simulating deep ~100-qubit random circuits, like those that Google and Quantinuum have now demonstrated experimentally, still seems pretty hopeless with any current classical method. This is particularly true for Quantinuum’s experiments, which had high enough gate fidelity to maintain a Linear Cross-Entropy score of order 1 (i.e., they’re no longer all that “noisy”). The central drawback of these experiments is no longer lack of confidence about quantum advantage; rather, it’s just that we only get samples as output, and directly verifying the quality of the samples seems just as intractable for a classical computer as spoofing the samples.
As of this past year, however, we have some strong candidates for verifiable quantum advantage. One is the Google OTOC experiment, as even Hagar himself acknowledges (that’s his “single clear exception”). A second is the simulations of the 2D Fermi-Hubbard model on Quantinuum and Google machines, like this one. The 1D Fermi-Hubbard model can be classically simulated pretty easily (see here for example), but the 2D one still presents challenges, meaning that in some regimes, the best available estimates of certain observables apparently now come from quantum computers. I wish I could write about other examples that will be public shortly.
Yes, the “real” goal remains, as it’s been since the 1990s, to build a scalable fault-tolerant quantum computer—and I’m glad that Hagar (unlike, say, Gil Kalai) never suggests that we’ve learned anything to rule that goal out. In the meantime, an intermediate goal would be to use NISQ devices to do physics and chemistry simulations that are commercially useful, or that help solve important scientific problems. The point of quantum supremacy experiments, you might say, is that by demonstrating the reality of quantum speedup about as clearly as it can be demonstrated with current hardware, they let us cleanly turn our attention to those more ambitious goals.

Anyway, my son and I need to catch a plane to Utah now, for the next iteration of the wonderful Epsilon Camp, where I’ll again be teaching theoretical computer science to 11- and 12-year-olds. But feel free to discuss in the comments! Nothing about world affairs in this thread please, just quantum supremacy.

Update (July 19): Not unrelated to the subject of this post, here’s a podcast I did with Gill Eapen of “Scientific Sense” about the current situation in quantum computing including recent experimental victories.

By Scott

Saturday, July 18 2026, 20:38

TR26-120 | Hitting point for sparse noncommutative polynomials | Foram Lakhani, Partha Mukhopadhyay

from ECCC Papers

For every $n,s \geq 1$, we construct a matrix tuple $(A_1,\ldots,A_n) \in \mathrm{M}_s(\mathbb{Z})^n$ in deterministic $\mathrm{poly}(n,s)$ time such that every noncommutative polynomial $$f \in \mathbb{C}\langle x_1,x_2,\ldots,x_n\rangle$$ of sparsity at most $s$ satisfies $f = 0$ if and only if $f(A_1,A_2,\ldots,A_n) = 0$. The bit complexity of the entries in the matrices $A_1, \ldots, A_n$ is $O(s\log n)$. This immediately gives a deterministic one-query black-box identity testing algorithm for these polynomials. This is done under the standard assumption that the black-box can be queried over matrix algebras. In particular, a black-box randomized polynomial-time algorithm was known for sparse noncommutative polynomials of exponential degree [Arvind, Joglekar, Mukhopadhyay, and Raja, 19], but (to the best of our knowledge) no deterministic polynomial-time algorithm was known. Interestingly, in the commutative case, deterministic polynomial-time black-box algorithm for sparse high-degree polynomials is well known [Saxena, 09].

Saturday, July 18 2026, 20:36

Methods to Madness

from Ben Recht

Reading Greg Nuckols and thinking about what it means to get stronger by science.

In the noisy chaos of science-based wellness on social media, there are a few reasonable voices. One of my favorites1 is Greg Nuckols, a champion powerlifter who has been blogging about the science of strength training for well over a decade. Over the weekend, I read his 2015 books The Art of Lifting and The Science of Lifting, and they hammer home how a simple topic can be made overly complicated when we decide to write scientific papers about it.

Nuckols’ two-volume series is less than two hundred pages long and written in an engaging, bloggy voice. Though the books link out to systematic reviews and randomized trial reports, he doesn’t get bogged down in that material. Instead, he focuses on one simple modeling principle and its consequences: adaptation.

Though the human body is impossibly complex, its many interconnected systems deal with stressors in a surprisingly uniform way. Stressor here means all sorts of things: wounds, infections, temperature changes, environmental changes, activity changes. Something out of the ordinary. The model of homeostasis posits that bodies actively work to stay the same as much as possible. Most of our daily activities don’t stress the body, and we remain in a pleasant, steady state. However, the body changes and adapts if it gets pushed far enough out of its comfort zone. If you apply enough stress, the body initiates a response to prevent harm or death. There are limits to this response, and too much stress will cause injury or death. But in the right Goldilocks range, the body will reconfigure itself to resist the stress next time it sees it.

Exercise can be modeled as a stressor. It’s certainly stressful. It increases muscle tension and body temperature. It increases demand for oxygen and nutrients. It lights up your sympathetic nervous system and triggers the release of adrenaline. Your body responds to exercise similarly to how it fights off other stressors like injuries and infections. It panics and then marshals resources to make sure it sucks less the next time you go to the gym.

There are many models for the temporal behavior of the stress reaction. The most common mathematical model is the fitness fatigue model developed by Tom Calvert, Eric Banister, and collaborators in the 1970s. Notably, Calvert was an electrical engineer who introduced his physiology colleagues to cybernetics and impulse responses. The fitness-fatigue model is a parametric model of adaptation: stressors introduce bad effects (fatigue) from which the body works hard to recover quickly. It also introduces positive training effects, the adaptations you were chasing. The fitness-fatigue model posits that the positive effects decay more slowly than the negative ones. For the dynamical systems nerds out there: they model this with a simple second-order linear system. Hence, if you repeat this process of enough but not too much stress over time, you nudge your body to handle more and more stress.

This feels science-y, no? The general adaptation syndrome is a well-tested, clean model that certainly helps guide how to train athletes and implement physical therapy. This model hasn’t changed since 1980. It prescribes working hard and continuing to do so over time to increase adaptation. It predicts that training harder than last time is beneficial. These two together form the principle of progressive overload, a very simple concept that influencers try to make absurdly complicated. Moreover, this model of adaptation tells you that you need to recover to hasten the elimination of fatigue. It even suggests implementing tapering periods before competition, a common practice.

OK great, now let’s try to apply this model to practice. What is the right shape of the actual stress to give you the results you want? If you want to get stronger, which exercises should you do? How frequently should you do them? What weights should you use? How many repetitions should you do for each exercise?

Unlike most of the charlatans in the science-based fitness space, Nuckols is brutally honest about this: the answer to all of these questions is that we don’t really know. Or at least, we at best only have partial answers. You probably need to go above some nominal effort to induce adaptation. Because there is so much intersubject variability, the exact perfect amount is hard to pin down. But if you work hard and make sure to rest and eat, you’ll get stronger over time.

Nuckols thinks the broader scientific research on sports training tells us more than I think it does. From my reading of too many studies in this space, the ns are always really small, the data are always poor, and the assessments are always ill defined. Do we need thousands of studies to tell us that we should “keep it simple, stupid?” People obviously can go to the gym and get stronger.

But what’s interesting to me about how Nuckols writes is that he doesn’t consider “science” to be some combination of biomolecular pathways and randomized trials. Instead, his scientific view is one of simple predictive models and their limitations. For an athlete like Nuckols, the scientific view helps systematize what matters in training. Working hard matters. Working harder over time matters. But resting and recovery are also critical to good performance. The right balance might not be easy to quantify, but the qualitative arc and predictions based on principles of adaptation are helpful. The general adaptation model for training tells us that training isn’t that complicated if you think carefully about what you are going to measure, and how you are going to track progress. This cybernetic view of biomedical science—one closer to what I would call engineering—feels like a promising path for many other aspects of medicine.

Subscribe now

1

Maybe for kicks one day, I’ll write about the rest of my favorites.

By Ben Recht

Friday, July 17 2026, 14:37

Circuit complexity lower bounds for quantum spin glasses

Authors: Omar Al-Ghattas, David Gamarnik

A central question in quantum information theory is the circuit complexity of states arising from standard many-body models. We study this question for quantum $p$-spin glasses, random Hamiltonians whose interactions act on $p$-tuples of qubits through Pauli strings. Anschuetz, Gamarnik, and Kiani (arXiv:2404.07231) showed that the optimum energy is separated from the best energy achievable by product states. This leaves open whether shallow circuits can close the gap, since even depth-one circuits can generate entanglement. We show that the entanglement needed to close the product-state gap cannot be generated at shallow depth. When the average interaction degree grows with $n$, we prove that, for all sufficiently large fixed $p$, any circuit preparing an $n$-qubit state whose normalized energy is within a fixed positive constant of the optimum must have depth $Ω_p(\log n)$. In the bounded-average-degree regime, we prove a fixed-depth obstruction: for every fixed $D$, a sufficiently large degree prefactor rules out depth-$D$ preparation of near-ground states. Both results hold uniformly over circuits with an arbitrary number of ancilla qubits. Our results give an obstruction in the spirit of the No Low-Energy Trivial States problem of Freedman and Hastings (arXiv:1301.1363), but for random quantum spin glasses rather than code-based Hamiltonians such as those of Anshu, Breuckmann, and Nirkhe (arXiv:2206.13228), whose ground states admit polynomial-size preparation circuits. This setting opens a probabilistic route to NLTS-like questions: we recast state-preparation lower bounds for random quantum Hamiltonians as uniform control of Gaussian processes indexed by shallow circuits.

Authors: Omar Al-Ghattas, David Gamarnik

A central question in quantum information theory is the circuit complexity of states arising from standard many-body models. We study this question for quantum $p$-spin glasses, random Hamiltonians whose interactions act on $p$-tuples of qubits through Pauli strings. Anschuetz, Gamarnik, and Kiani (arXiv:2404.07231) showed that the optimum energy is separated from the best energy achievable by product states. This leaves open whether shallow circuits can close the gap, since even depth-one circuits can generate entanglement. We show that the entanglement needed to close the product-state gap cannot be generated at shallow depth. When the average interaction degree grows with $n$, we prove that, for all sufficiently large fixed $p$, any circuit preparing an $n$-qubit state whose normalized energy is within a fixed positive constant of the optimum must have depth $Ω_p(\log n)$. In the bounded-average-degree regime, we prove a fixed-depth obstruction: for every fixed $D$, a sufficiently large degree prefactor rules out depth-$D$ preparation of near-ground states. Both results hold uniformly over circuits with an arbitrary number of ancilla qubits. Our results give an obstruction in the spirit of the No Low-Energy Trivial States problem of Freedman and Hastings (arXiv:1301.1363), but for random quantum spin glasses rather than code-based Hamiltonians such as those of Anshu, Breuckmann, and Nirkhe (arXiv:2206.13228), whose ground states admit polynomial-size preparation circuits. This setting opens a probabilistic route to NLTS-like questions: we recast state-preparation lower bounds for random quantum Hamiltonians as uniform control of Gaussian processes indexed by shallow circuits.

Friday, July 17 2026, 00:00

Random Parameter Noise Does Not Make Exact ReLU Verification Easy

Authors: Mojtaba Soltanalian

We study exact verification of ReLU networks in an adversarial smoothed model. Every network weight and bias is independently perturbed by Gaussian noise, clipped to $[-2,2]$, and rounded to the exact dyadic grid determined by the input bit complexity. We show that, under the standard assumption $\mathrm{NP}\not\subseteq\mathrm{BPP}$, there is no sound and complete verifier whose expected running time is polynomial in network size, bit complexity, and inverse noise level for every base instance. The conclusion already holds at the fixed noise level $σ_\star=2^{-11}$ for one-hidden-layer networks over a unit box, with hidden fan-in at most three and base coefficients in $[-1,1]$. The proof combines an exact gap embedding with a quantitative robustness argument. For every E3SAT formula $Φ$ with $m$ clauses, a four-ReLU-per-clause construction satisfies $\max_{x\in[0,1]^n} g_Φ(x)=(m-\operatorname{unsat}(Φ))/3$, and coordinatewise threshold rounding never decreases the objective. A weighted parameter-sensitivity inequality and Gaussian concentration then show that a verification gap linear in $m$ survives the aggregate perturbation of all coefficients with probability at least $1-e^{-m/8}$. The proof includes clipping, exact dyadic rounding, output-layer perturbations, polynomial-bit sampling of the rounded Gaussian law, and the conversion from expected smoothed running time to a BPP algorithm. Computational checks test the exact identity and illustrate the different scaling of extensive and constant gaps; they are diagnostics rather than evidence for the complexity theorem. The result concerns worst-case base networks in the stated absolute-noise model, but it shows that parameter nondegeneracy alone does not yield a universal smoothed-polynomial guarantee for exact verification.

Authors: Mojtaba Soltanalian

We study exact verification of ReLU networks in an adversarial smoothed model. Every network weight and bias is independently perturbed by Gaussian noise, clipped to $[-2,2]$, and rounded to the exact dyadic grid determined by the input bit complexity. We show that, under the standard assumption $\mathrm{NP}\not\subseteq\mathrm{BPP}$, there is no sound and complete verifier whose expected running time is polynomial in network size, bit complexity, and inverse noise level for every base instance. The conclusion already holds at the fixed noise level $σ_\star=2^{-11}$ for one-hidden-layer networks over a unit box, with hidden fan-in at most three and base coefficients in $[-1,1]$. The proof combines an exact gap embedding with a quantitative robustness argument. For every E3SAT formula $Φ$ with $m$ clauses, a four-ReLU-per-clause construction satisfies $\max_{x\in[0,1]^n} g_Φ(x)=(m-\operatorname{unsat}(Φ))/3$, and coordinatewise threshold rounding never decreases the objective. A weighted parameter-sensitivity inequality and Gaussian concentration then show that a verification gap linear in $m$ survives the aggregate perturbation of all coefficients with probability at least $1-e^{-m/8}$. The proof includes clipping, exact dyadic rounding, output-layer perturbations, polynomial-bit sampling of the rounded Gaussian law, and the conversion from expected smoothed running time to a BPP algorithm. Computational checks test the exact identity and illustrate the different scaling of extensive and constant gaps; they are diagnostics rather than evidence for the complexity theorem. The result concerns worst-case base networks in the stated absolute-noise model, but it shows that parameter nondegeneracy alone does not yield a universal smoothed-polynomial guarantee for exact verification.

Friday, July 17 2026, 00:00

Stable Voting is PSPACE-Complete

Authors: Ethan Dickey, Alexandros Psomas, Athina Terzoglou

Stable Voting and Simple Stable Voting, introduced by Holliday and Pacuit, are Condorcet-consistent voting rules defined recursively: a candidate wins if they would win after removing some opponent they beat, taking the pair with the largest margin first. The computational complexity of winner determination under these rules has been an open question. We resolve this problem: winner determination is PSPACE-complete under both Stable Voting and Simple Stable Voting.

Authors: Ethan Dickey, Alexandros Psomas, Athina Terzoglou

Stable Voting and Simple Stable Voting, introduced by Holliday and Pacuit, are Condorcet-consistent voting rules defined recursively: a candidate wins if they would win after removing some opponent they beat, taking the pair with the largest margin first. The computational complexity of winner determination under these rules has been an open question. We resolve this problem: winner determination is PSPACE-complete under both Stable Voting and Simple Stable Voting.

Friday, July 17 2026, 00:00

Towards a characterization of idempotent Schur multipliers

Authors: Marcel K. Goh, Hamed Hatami

It is conjectured that every idempotent Schur multiplier can be written as a finite sum of contractive idempotents. This conjecture is equivalent to the statement that any boolean matrix $A$ with factorization norm $\lVert A\rVert_{γ_2}$ at most $γ$ can be expressed as a signed sum $$A = \sum_{i=1}^L \pm B_i,$$ where, up to permutation of rows and columns, each $B_i$ is a blow-up of an identity matrix, and $L$ depends only on $γ$. In this note we show that if $A$ is an $n\times n$ boolean matrix with $\lVert A\rVert_{γ_2} \le γ$, then it admits such an expression with $L = 2^{O(γ^9) + \log^*\! n}$, where $\log^*$ is the iterated logarithm function. As an application, any sequence of matrices with bounded factorization norm belongs to the complexity class $\mathrm{P}^\mathrm{EQ}$ of communication problems with polylogarithmic equality-oracle complexity.

Authors: Marcel K. Goh, Hamed Hatami

It is conjectured that every idempotent Schur multiplier can be written as a finite sum of contractive idempotents. This conjecture is equivalent to the statement that any boolean matrix $A$ with factorization norm $\lVert A\rVert_{γ_2}$ at most $γ$ can be expressed as a signed sum $$A = \sum_{i=1}^L \pm B_i,$$ where, up to permutation of rows and columns, each $B_i$ is a blow-up of an identity matrix, and $L$ depends only on $γ$. In this note we show that if $A$ is an $n\times n$ boolean matrix with $\lVert A\rVert_{γ_2} \le γ$, then it admits such an expression with $L = 2^{O(γ^9) + \log^*\! n}$, where $\log^*$ is the iterated logarithm function. As an application, any sequence of matrices with bounded factorization norm belongs to the complexity class $\mathrm{P}^\mathrm{EQ}$ of communication problems with polylogarithmic equality-oracle complexity.

Friday, July 17 2026, 00:00

Inferring Non-Normal Amplification Geometry from Multivariate Time Series

Authors: V. R. Saiprasad, V. Troude, D. Sornette

Across hydrodynamics, ecology, neuroscience, network dynamics, non-Hermitian physics, and socio-economic systems, asymptotically stable dynamics can exhibit large transient amplifications that are invisible to eigenvalue-based analyses. The mechanism is geometric rather than spectral: perturbations entering along one direction may be expressed transiently along another, allowing asymptotic decay to coexist with strong transient or noise-driven amplification. We introduce non-normal directional response inference, a data-driven method for detecting this geometry from multivariate time series when the governing operator is unknown. A local linear operator is estimated from sliding windows and projected onto the dominant two-dimensional input-response subspace. The reduced dynamics are summarized by the eigenvalue splitting $Δ$, eigenvector non-orthogonality $K$, and the scale-free ratio $R=K/K_c(Δ)$, where $K_c(Δ)$ is the two-dimensional threshold for transient amplification. Controlled benchmarks show that the reduced geometry, particularly $R$, can be recovered from finite data even when the full high-dimensional operator is poorly estimated. Tests across sample size, dimension, training horizon, spectral structure, and non-stationarity confirm that the relevant response geometry requires far fewer observations than full-matrix recovery. Applied in moving windows to electrohysterogram, seizure EEG, freezing-of-gait, and unstable push-up inertial recordings, the method reveals systematic changes around known physiological or behavioral episodes through shifts in $R$, changes in $Δ$, or stronger projection of fluctuations onto the inferred response direction. It thus exposes interpretable changes in local response geometry without framing the problem as supervised event detection.

Authors: V. R. Saiprasad, V. Troude, D. Sornette

Across hydrodynamics, ecology, neuroscience, network dynamics, non-Hermitian physics, and socio-economic systems, asymptotically stable dynamics can exhibit large transient amplifications that are invisible to eigenvalue-based analyses. The mechanism is geometric rather than spectral: perturbations entering along one direction may be expressed transiently along another, allowing asymptotic decay to coexist with strong transient or noise-driven amplification. We introduce non-normal directional response inference, a data-driven method for detecting this geometry from multivariate time series when the governing operator is unknown. A local linear operator is estimated from sliding windows and projected onto the dominant two-dimensional input-response subspace. The reduced dynamics are summarized by the eigenvalue splitting $Δ$, eigenvector non-orthogonality $K$, and the scale-free ratio $R=K/K_c(Δ)$, where $K_c(Δ)$ is the two-dimensional threshold for transient amplification. Controlled benchmarks show that the reduced geometry, particularly $R$, can be recovered from finite data even when the full high-dimensional operator is poorly estimated. Tests across sample size, dimension, training horizon, spectral structure, and non-stationarity confirm that the relevant response geometry requires far fewer observations than full-matrix recovery. Applied in moving windows to electrohysterogram, seizure EEG, freezing-of-gait, and unstable push-up inertial recordings, the method reveals systematic changes around known physiological or behavioral episodes through shifts in $R$, changes in $Δ$, or stronger projection of fluctuations onto the inferred response direction. It thus exposes interpretable changes in local response geometry without framing the problem as supervised event detection.

Friday, July 17 2026, 00:00

HyperShadow: A Benchmark for Detecting 3D Projections of Higher-Dimensional Spatial Objects

Authors: Akshay Sasi

Machine-learning datasets labelled "4D" universally denote three spatial dimensions plus time. We introduce HyperShadow, the first public benchmark in which the fourth, fifth, and sixth dimensions are spatial: the task is to decide whether a 3D point cloud is a native three-dimensional shape or the projection, the "shadow", of a rigid object living in R^N (N = 4-6). We show this task is fundamentally distinct from intrinsic-dimension estimation: a shadow is still at-most-3-dimensional data, and standard estimators (TwoNN, Levina-Bickel MLE) reach only 71-73% accuracy. Detection instead requires projection signatures, density folds, filled volumes with characteristic radial profiles, and topology changes, which a 190k-parameter point network recovers at 96.6% accuracy across four corruption tiers, generalizing at 79-91% to object families never seen in training. On a temporal track of rigidly rotating objects we introduce a zero-parameter rigidity witness: the residual of the optimal rigid 3D alignment (Kabsch) between consecutive frames, which must vanish for any rigid 3D motion but cannot vanish for the shadow of a rigid rotation in R^N. This single interpretable statistic separates the classes at AUROC 0.982. All data are generated reproducibly from seeds; the dataset, models, and code are released publicly. HyperShadow makes no claim about physical reality; it is a controlled instrument for studying which observable statistics can certify incompatibility with a purely three-dimensional explanation.

Authors: Akshay Sasi

Machine-learning datasets labelled "4D" universally denote three spatial dimensions plus time. We introduce HyperShadow, the first public benchmark in which the fourth, fifth, and sixth dimensions are spatial: the task is to decide whether a 3D point cloud is a native three-dimensional shape or the projection, the "shadow", of a rigid object living in R^N (N = 4-6). We show this task is fundamentally distinct from intrinsic-dimension estimation: a shadow is still at-most-3-dimensional data, and standard estimators (TwoNN, Levina-Bickel MLE) reach only 71-73% accuracy. Detection instead requires projection signatures, density folds, filled volumes with characteristic radial profiles, and topology changes, which a 190k-parameter point network recovers at 96.6% accuracy across four corruption tiers, generalizing at 79-91% to object families never seen in training. On a temporal track of rigidly rotating objects we introduce a zero-parameter rigidity witness: the residual of the optimal rigid 3D alignment (Kabsch) between consecutive frames, which must vanish for any rigid 3D motion but cannot vanish for the shadow of a rigid rotation in R^N. This single interpretable statistic separates the classes at AUROC 0.982. All data are generated reproducibly from seeds; the dataset, models, and code are released publicly. HyperShadow makes no claim about physical reality; it is a controlled instrument for studying which observable statistics can certify incompatibility with a purely three-dimensional explanation.

Friday, July 17 2026, 00:00

Semi-Streaming Matching in a Single Pass II: Greedy is Optimal

Authors: Sepehr Assadi, Max Jiang, Mars Xiang

We prove that no single-pass semi-streaming algorithm (deterministic or randomized) can achieve a better-than-half approximation to the maximum matching problem. This implies the optimality of the naive greedy algorithm, answering an outstanding open question in the graph streaming literature since the introduction of the model over two decades ago. Our proof follows the "blueprint framework" introduced previously by the authors, which reduced proving lower bounds for semi-streaming matching to constructing certain combinatorial objects called blueprints. We present an optimal construction of blueprints that when used in this framework implies our semi-streaming matching lower bound. Our results also imply that the optimal competitive ratio of online matching with preemption is half, again matching the naive greedy algorithm, settling this open question as well.

Authors: Sepehr Assadi, Max Jiang, Mars Xiang

We prove that no single-pass semi-streaming algorithm (deterministic or randomized) can achieve a better-than-half approximation to the maximum matching problem. This implies the optimality of the naive greedy algorithm, answering an outstanding open question in the graph streaming literature since the introduction of the model over two decades ago. Our proof follows the "blueprint framework" introduced previously by the authors, which reduced proving lower bounds for semi-streaming matching to constructing certain combinatorial objects called blueprints. We present an optimal construction of blueprints that when used in this framework implies our semi-streaming matching lower bound. Our results also imply that the optimal competitive ratio of online matching with preemption is half, again matching the naive greedy algorithm, settling this open question as well.

Friday, July 17 2026, 00:00

Semi-Streaming Matching in a Single Pass I: A New Framework for Lower Bounds via Blueprints

Authors: Sepehr Assadi, Max Jiang, Mars Xiang

In the semi-streaming model, we have an $n$-vertex graph $G=(V,E)$ whose edges arrive in an arbitrary order in a stream. The goal is to make one or a few passes over the stream, use a limited memory of $\tilde O(n)$ bits, and output a solution to the problem at hand at the end. A central open question in this area is to determine the best approximation ratio possible for the maximum matching problem via single-pass semi-streaming algorithms. This problem admits a simple $0.5$-approximation algorithm, by maintaining a maximal matching greedily, which, despite extensive efforts, has remained the state of the art. Lower bounds for this problem have also been few and far between with best known bounds ruling out better than $1/(1+\ln{(2)}) \sim 0.590$ approximation, using a highly complicated construction motivated by the literature on RS graphs from extremal graph theory. We develop a new framework for proving lower bounds for the semi-streaming matching problem. Our framework abstracts out the extremal graph theory and information theoretic arguments in the lower bounds, and reduces the problem to constructing certain constant-size graphs, which we call blueprints. Not only existing lower bounds can be captured by these blueprints, leading to far simpler and more concise arguments, but also we can design new blueprints that can be used to rule out $(8-2\sqrt{10})/3 \sim 0.558$-approximation for the semi-streaming matching problem. We believe this approach can be of its own independent interest and lead to further improvements on this tantalizing open question.

Authors: Sepehr Assadi, Max Jiang, Mars Xiang

In the semi-streaming model, we have an $n$-vertex graph $G=(V,E)$ whose edges arrive in an arbitrary order in a stream. The goal is to make one or a few passes over the stream, use a limited memory of $\tilde O(n)$ bits, and output a solution to the problem at hand at the end. A central open question in this area is to determine the best approximation ratio possible for the maximum matching problem via single-pass semi-streaming algorithms. This problem admits a simple $0.5$-approximation algorithm, by maintaining a maximal matching greedily, which, despite extensive efforts, has remained the state of the art. Lower bounds for this problem have also been few and far between with best known bounds ruling out better than $1/(1+\ln{(2)}) \sim 0.590$ approximation, using a highly complicated construction motivated by the literature on RS graphs from extremal graph theory. We develop a new framework for proving lower bounds for the semi-streaming matching problem. Our framework abstracts out the extremal graph theory and information theoretic arguments in the lower bounds, and reduces the problem to constructing certain constant-size graphs, which we call blueprints. Not only existing lower bounds can be captured by these blueprints, leading to far simpler and more concise arguments, but also we can design new blueprints that can be used to rule out $(8-2\sqrt{10})/3 \sim 0.558$-approximation for the semi-streaming matching problem. We believe this approach can be of its own independent interest and lead to further improvements on this tantalizing open question.

Friday, July 17 2026, 00:00

Space-Entropy Lower Bounds for Random Sampling

Authors: Thomas L. Draper, Feras A. Saad

We prove fundamental space lower bounds for exact random sampling using an entropy source of i.i.d. uniform bits. A classic result from information theory shows that generating $n$ discrete random variables $X_1, \dots, X_n$ requires at least $H(X_1, \dots, X_n)$ input random bits on average, where $H$ is the Shannon entropy function. How much space must a random sampling algorithm use in order to approach this information-theoretically optimal entropy bound? We prove that any random sampling algorithm that is exact for arbitrary discrete target distributions and consumes at most $H(X_1,\ldots,X_n)+\varepsilon n+o(n)$ input bits in expectation for every output process must use $Ω(\log(1/\varepsilon))$ bits of space. In fact, i.i.d. sampling from the single distribution $\mathrm{Bernoulli}(1/3)$ already forces at least $(1/{5.116201}-o(1))\log(1/\varepsilon)$ bits of space. If the sampler handles a family of infinitely many Bernoulli distributions, we show a sharper bound of at least $\log(1/\varepsilon)$ bits of space. We also prove lower bounds for general i.i.d. sampling: for almost every distribution on $k$ outcomes, the space is at least $(1/(k+1)-o(1))\log(1/\varepsilon)$ bits. The proof technique is based on a graph-theoretic analysis of the amount of information that any algorithm can store in its state. Finite state spaces force short cycles around the state-transition graph, and the loss around such cycles reduces to Diophantine lower bounds on fractional parts of integer combinations of log-probabilities. To the best of our knowledge, these results comprise the first known space lower bounds for entropy-efficient random sampling.

Authors: Thomas L. Draper, Feras A. Saad

We prove fundamental space lower bounds for exact random sampling using an entropy source of i.i.d. uniform bits. A classic result from information theory shows that generating $n$ discrete random variables $X_1, \dots, X_n$ requires at least $H(X_1, \dots, X_n)$ input random bits on average, where $H$ is the Shannon entropy function. How much space must a random sampling algorithm use in order to approach this information-theoretically optimal entropy bound? We prove that any random sampling algorithm that is exact for arbitrary discrete target distributions and consumes at most $H(X_1,\ldots,X_n)+\varepsilon n+o(n)$ input bits in expectation for every output process must use $Ω(\log(1/\varepsilon))$ bits of space. In fact, i.i.d. sampling from the single distribution $\mathrm{Bernoulli}(1/3)$ already forces at least $(1/{5.116201}-o(1))\log(1/\varepsilon)$ bits of space. If the sampler handles a family of infinitely many Bernoulli distributions, we show a sharper bound of at least $\log(1/\varepsilon)$ bits of space. We also prove lower bounds for general i.i.d. sampling: for almost every distribution on $k$ outcomes, the space is at least $(1/(k+1)-o(1))\log(1/\varepsilon)$ bits. The proof technique is based on a graph-theoretic analysis of the amount of information that any algorithm can store in its state. Finite state spaces force short cycles around the state-transition graph, and the loss around such cycles reduces to Diophantine lower bounds on fractional parts of integer combinations of log-probabilities. To the best of our knowledge, these results comprise the first known space lower bounds for entropy-efficient random sampling.

Friday, July 17 2026, 00:00

The Power of the Score Sequence of a Tournament

Authors: Prantar Ghosh, Sahil Kuchlous, Shravan Mehra, Sagnik Mukhopadhyay

What problems can one solve on a tournament if only its score sequence is known? Tournaments are oriented complete graphs that form an extensively-studied class of directed graphs (digraphs), both from combinatorial and algorithmic perspectives. Over the years, researchers have identified multiple classical digraph problems that can be solved on a tournament from only its score sequence (indegree sequence). These problems include acyclicity testing and topological sorting [Chakrabarti, Ghosh, McGregor, and Vorotnikova; SODA'20], $s,t$-reachability, strong connectivity, and decomposition into strongly connected components (SCC) [Ghosh and Kuchlous; ESA'24], and vertex-ordering problems such as cutwidth and optimal linear arrangement [Barbero, Paul, and Pilipczuk; ICALP'17]. These prior works showed the sufficiency of the score sequence by designing distinct algorithms for the individual problems. In this work, we give a simple unified framework that solves all these problems using only indegrees and, in fact, completely characterises the class of problems that is determined by the indegree information: problems whose answers are invariant under cycle reversals. This characterisation is a special case of a much more general result that we establish: for any arbitrary digraph, the knowledge of its skeleton (underlying undirected graph) and the vertex indegrees completely determines its properties that are invariant under cycle reversal. As a byproduct of our results, we obtain algorithms for a variety of connectivity-based, cut-based, and vertex-ordering problems on tournaments and ``almost tournaments'' in the streaming, the two-player communication, and the cut-query models of computation. Some of these algorithms match existing optimal bounds and others provide bounds improving the state of the art.

Authors: Prantar Ghosh, Sahil Kuchlous, Shravan Mehra, Sagnik Mukhopadhyay

What problems can one solve on a tournament if only its score sequence is known? Tournaments are oriented complete graphs that form an extensively-studied class of directed graphs (digraphs), both from combinatorial and algorithmic perspectives. Over the years, researchers have identified multiple classical digraph problems that can be solved on a tournament from only its score sequence (indegree sequence). These problems include acyclicity testing and topological sorting [Chakrabarti, Ghosh, McGregor, and Vorotnikova; SODA'20], $s,t$-reachability, strong connectivity, and decomposition into strongly connected components (SCC) [Ghosh and Kuchlous; ESA'24], and vertex-ordering problems such as cutwidth and optimal linear arrangement [Barbero, Paul, and Pilipczuk; ICALP'17]. These prior works showed the sufficiency of the score sequence by designing distinct algorithms for the individual problems. In this work, we give a simple unified framework that solves all these problems using only indegrees and, in fact, completely characterises the class of problems that is determined by the indegree information: problems whose answers are invariant under cycle reversals. This characterisation is a special case of a much more general result that we establish: for any arbitrary digraph, the knowledge of its skeleton (underlying undirected graph) and the vertex indegrees completely determines its properties that are invariant under cycle reversal. As a byproduct of our results, we obtain algorithms for a variety of connectivity-based, cut-based, and vertex-ordering problems on tournaments and ``almost tournaments'' in the streaming, the two-player communication, and the cut-query models of computation. Some of these algorithms match existing optimal bounds and others provide bounds improving the state of the art.

Friday, July 17 2026, 00:00

A lower bound of 4 for online graph exploration

Authors: Julia Baligacs

In the online graph exploration problem, a single agent needs to visit every vertex of an initially unknown graph, which is learned over time in an online fashion, and return to its starting position. We prove that the competitive ratio of this problem is at least 4, improving on the previously best known lower bound of 10/3. A key ingredient of our proof is showing that several restrictions can be imposed on the agent's behavior without affecting the competitive ratio. As a byproduct, we also obtain that certain graph properties, such as the triangle inequality or being subcubic, can be assumed without affecting the competitive ratio.

Authors: Julia Baligacs

In the online graph exploration problem, a single agent needs to visit every vertex of an initially unknown graph, which is learned over time in an online fashion, and return to its starting position. We prove that the competitive ratio of this problem is at least 4, improving on the previously best known lower bound of 10/3. A key ingredient of our proof is showing that several restrictions can be imposed on the agent's behavior without affecting the competitive ratio. As a byproduct, we also obtain that certain graph properties, such as the triangle inequality or being subcubic, can be assumed without affecting the competitive ratio.

Friday, July 17 2026, 00:00

A Correlation-Gap Bound for Nonlinear Gaussian PCA

Authors: Minbo Gao, Zhengfeng Ji, Chenghua Liu

Principal component analysis (PCA) is optimal for the linear reconstruction of Gaussian data, a foundational property underlying its central role in algorithms and signal processing. Its nonlinear analogue, however, is notoriously subtle: in 2011, Mallat and Zeitouni conjectured that the Karhunen--Loève (KL) basis remains optimal even when the retained coordinates are chosen adaptively per sample, a property that would theoretically justify the ubiquitous pipeline of PCA followed by sparse thresholding. In this paper, we establish a $1+O(1/\sqrt{d})$-approximate version of the retained-energy form of the Mallat--Zeitouni conjecture, showing that the KL basis is within this factor of the optimal basis. This dimension-free comparison depends only on the number of retained coordinates and shows that the possible advantage of optimizing over all orthonormal bases vanishes as $d$ grows. It complements the universal-constant reconstruction-error comparison of Litvak and Tikhomirov (Ann. Appl. Probab., 2018), while providing a comparison naturally suited for algorithmic analysis. Our proof rests on a clean, conceptual reduction: we relax arbitrary rotations to a deterministic threshold bound via Schur--Horn majorization, and identify the remaining loss with the correlation gap of the rank-$d$ uniform matroid over Gaussian level sets.

Authors: Minbo Gao, Zhengfeng Ji, Chenghua Liu

Principal component analysis (PCA) is optimal for the linear reconstruction of Gaussian data, a foundational property underlying its central role in algorithms and signal processing. Its nonlinear analogue, however, is notoriously subtle: in 2011, Mallat and Zeitouni conjectured that the Karhunen--Loève (KL) basis remains optimal even when the retained coordinates are chosen adaptively per sample, a property that would theoretically justify the ubiquitous pipeline of PCA followed by sparse thresholding. In this paper, we establish a $1+O(1/\sqrt{d})$-approximate version of the retained-energy form of the Mallat--Zeitouni conjecture, showing that the KL basis is within this factor of the optimal basis. This dimension-free comparison depends only on the number of retained coordinates and shows that the possible advantage of optimizing over all orthonormal bases vanishes as $d$ grows. It complements the universal-constant reconstruction-error comparison of Litvak and Tikhomirov (Ann. Appl. Probab., 2018), while providing a comparison naturally suited for algorithmic analysis. Our proof rests on a clean, conceptual reduction: we relax arbitrary rotations to a deterministic threshold bound via Schur--Horn majorization, and identify the remaining loss with the correlation gap of the rank-$d$ uniform matroid over Gaussian level sets.

Friday, July 17 2026, 00:00

Random Access to LZ-End: Faster and Deterministic

Authors: Itai Boneh, Paweł Gawrychowski

The LZ-End parsing of a length-$n$ string is a variation of Lempel-Ziv compression introduced by Kreft and Navarro [DCC 2010], motivated by the lack of a linear-size structure with $O(\log n)$ access time for the classical variant. While the original paper was only able to provide efficient extraction from the phrase boundaries, recently Kempa and Saha [SODA 2022] established that, for a string $S$ whose LZ-End parsing consists of $z$ phrases, there exists a random access data structure that uses $O(z)$ space and guarantees $O(\log^{4}n \cdot \log\log n)$ query time. However, their proof does not yield an efficient construction algorithm, and their data structure is inherently randomized. We resolve both limitations by providing a deterministic, $O(z)$-space data structure that supports random access queries in polylogarithmic time and can be constructed in $O(z\log^{2}(n/z))$ time directly from the LZ-End parsing. In addition to eliminating randomness and providing an efficient construction algorithm, the query time of our data structure is $O(\log^{2}(n/z))$, significantly improving upon the query time of Kempa and Saha. We also show that our techniques can be used to support the more general substring-extraction. Namely, we present a data structure with the same space and the same construction time that given two indices $i$ and $j$, outputs $S[i..j]$ in $O(j-i+\log^2\frac{n}{z})$ time.

Authors: Itai Boneh, Paweł Gawrychowski

The LZ-End parsing of a length-$n$ string is a variation of Lempel-Ziv compression introduced by Kreft and Navarro [DCC 2010], motivated by the lack of a linear-size structure with $O(\log n)$ access time for the classical variant. While the original paper was only able to provide efficient extraction from the phrase boundaries, recently Kempa and Saha [SODA 2022] established that, for a string $S$ whose LZ-End parsing consists of $z$ phrases, there exists a random access data structure that uses $O(z)$ space and guarantees $O(\log^{4}n \cdot \log\log n)$ query time. However, their proof does not yield an efficient construction algorithm, and their data structure is inherently randomized. We resolve both limitations by providing a deterministic, $O(z)$-space data structure that supports random access queries in polylogarithmic time and can be constructed in $O(z\log^{2}(n/z))$ time directly from the LZ-End parsing. In addition to eliminating randomness and providing an efficient construction algorithm, the query time of our data structure is $O(\log^{2}(n/z))$, significantly improving upon the query time of Kempa and Saha. We also show that our techniques can be used to support the more general substring-extraction. Namely, we present a data structure with the same space and the same construction time that given two indices $i$ and $j$, outputs $S[i..j]$ in $O(j-i+\log^2\frac{n}{z})$ time.

Friday, July 17 2026, 00:00

Kernelization for $H$-Packing Revisited

Authors: Tomohiro Koana, Soh Kumabe

\textsc{$H$-Packing} asks whether a graph $G$ contains $k$ vertex-disjoint copies of a fixed pattern graph $H$. Via the standard reduction to \textsc{$d$-Set Packing}, one obtains generic kernels with $O(k^{|V(H)|-1})$ vertices and $O(k^{|V(H)|})$ edges. We revisit the question of beating these bounds for specific patterns $H$. Our main results concern subdivided stars. Let $S_{d_1,d_2}$ denote the subdivided star with $d_1$ branches of length $1$ and $d_2$ branches of length $2$. We obtain kernels with $O(k^2)$ vertices and $O(k^3)$ edges for $P_5=S_{0,2}$, for $S_{1,2}$, and for every $S_{d_1,1}$, kernels with $O(k^4)$ vertices and $O(k^6)$ edges for every fixed $S_{d_1,d_2}$ with $d_1\ge 1$, and a kernel with $O(k^2)$ vertices and $O(k^4)$ edges for the paw. Our proofs proceed in two steps. First, we reduce to instances in which all but a small part of the graph is independent, or in which the graph has a small vertex cover. Second, we reduce the independent side by keeping only a bounded number of witness vertices for each subset of the small part. On the negative side, we prove a lower bound for the line $S_{0,d}$. For every $d\ge 3$ and every $\varepsilon>0$, \textsc{$S_{0,d}$-Packing} does not admit a compression of size $O(k^{d-\varepsilon})$ unless $\NP\subseteq \coNP/\poly$. Thus, deleting a single vertex from the pattern may, surprisingly, make kernelization provably harder, showing that compressibility of \textsc{$H$-Packing} is not monotone under taking induced subgraphs.

Authors: Tomohiro Koana, Soh Kumabe

\textsc{$H$-Packing} asks whether a graph $G$ contains $k$ vertex-disjoint copies of a fixed pattern graph $H$. Via the standard reduction to \textsc{$d$-Set Packing}, one obtains generic kernels with $O(k^{|V(H)|-1})$ vertices and $O(k^{|V(H)|})$ edges. We revisit the question of beating these bounds for specific patterns $H$. Our main results concern subdivided stars. Let $S_{d_1,d_2}$ denote the subdivided star with $d_1$ branches of length $1$ and $d_2$ branches of length $2$. We obtain kernels with $O(k^2)$ vertices and $O(k^3)$ edges for $P_5=S_{0,2}$, for $S_{1,2}$, and for every $S_{d_1,1}$, kernels with $O(k^4)$ vertices and $O(k^6)$ edges for every fixed $S_{d_1,d_2}$ with $d_1\ge 1$, and a kernel with $O(k^2)$ vertices and $O(k^4)$ edges for the paw. Our proofs proceed in two steps. First, we reduce to instances in which all but a small part of the graph is independent, or in which the graph has a small vertex cover. Second, we reduce the independent side by keeping only a bounded number of witness vertices for each subset of the small part. On the negative side, we prove a lower bound for the line $S_{0,d}$. For every $d\ge 3$ and every $\varepsilon>0$, \textsc{$S_{0,d}$-Packing} does not admit a compression of size $O(k^{d-\varepsilon})$ unless $\NP\subseteq \coNP/\poly$. Thus, deleting a single vertex from the pattern may, surprisingly, make kernelization provably harder, showing that compressibility of \textsc{$H$-Packing} is not monotone under taking induced subgraphs.

Friday, July 17 2026, 00:00

Spectral Dual Fitting for $k$-Means

Authors: Aditya Anand, Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, Amatya Sharma, Ernest van Wijland

We give a new dual fitting algorithm which gives improved approximation ratios of $3+\ln 2 + ε (\approx 3.694)$ and $4.9+ε$ for $k$-Means in (high-dimensional) Euclidean and general metrics respectively, improving upon the previously known ratios of $4+ε$ [Charikar, Cohen-Addad, Gao, Grandoni, Lee, and van Wijland STOC'26] and $5+ε$ [Byrka, Guo, Hu, Li, Wan, Wang FOCS'26], resp. In particular, our result for Euclidean $k$-Means breaks the hardness barrier of $1+8/e\approx 3.94$ for Metric $k$-Means. Prior to our work, no such separation between general and Euclidean metrics was known for $k$-Median, $k$-Means, or Facility Location in terms of their approximability. Unlike prior dual fitting approaches for $k$-Means, our new dual fitting algorithm tightly accounts for dual payments while still facilitating an effective dual feasibility analysis. We introduce a new framework that uses spectral analysis for determining the approximation factor of our algorithm.

Authors: Aditya Anand, Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, Amatya Sharma, Ernest van Wijland

We give a new dual fitting algorithm which gives improved approximation ratios of $3+\ln 2 + ε (\approx 3.694)$ and $4.9+ε$ for $k$-Means in (high-dimensional) Euclidean and general metrics respectively, improving upon the previously known ratios of $4+ε$ [Charikar, Cohen-Addad, Gao, Grandoni, Lee, and van Wijland STOC'26] and $5+ε$ [Byrka, Guo, Hu, Li, Wan, Wang FOCS'26], resp. In particular, our result for Euclidean $k$-Means breaks the hardness barrier of $1+8/e\approx 3.94$ for Metric $k$-Means. Prior to our work, no such separation between general and Euclidean metrics was known for $k$-Median, $k$-Means, or Facility Location in terms of their approximability. Unlike prior dual fitting approaches for $k$-Means, our new dual fitting algorithm tightly accounts for dual payments while still facilitating an effective dual feasibility analysis. We introduce a new framework that uses spectral analysis for determining the approximation factor of our algorithm.

Friday, July 17 2026, 00:00

Efficient Pattern Matching for Unordered Term Tree Patterns under Generalized Height-Constrained Bindings

Authors: Shintaro Matsushita, Takayoshi Shoudai, Yusuke Suzuki

Unordered trees are useful for modeling hierarchical structures in which the order among siblings is irrelevant. To represent flexible structural patterns in such data, unordered term tree patterns with height-constrained variables provide a natural framework. In our previous work, we studied the pattern matching problem for rooted unordered term tree patterns with height-constrained variables under the restriction that the child port of each variable must correspond to a leaf of a binding tree. In this paper, we remove this restriction and generalize the binding model so that the child port may correspond to any non-root vertex of a binding tree. Under generalized bindings, we formulate the corresponding membership problem and present a polynomial-time pattern matching algorithm. We also implement the proposed algorithm and conduct computational experiments to evaluate its running time. The experimental results show that the proposed method achieves practical running times.

Authors: Shintaro Matsushita, Takayoshi Shoudai, Yusuke Suzuki

Unordered trees are useful for modeling hierarchical structures in which the order among siblings is irrelevant. To represent flexible structural patterns in such data, unordered term tree patterns with height-constrained variables provide a natural framework. In our previous work, we studied the pattern matching problem for rooted unordered term tree patterns with height-constrained variables under the restriction that the child port of each variable must correspond to a leaf of a binding tree. In this paper, we remove this restriction and generalize the binding model so that the child port may correspond to any non-root vertex of a binding tree. Under generalized bindings, we formulate the corresponding membership problem and present a polynomial-time pattern matching algorithm. We also implement the proposed algorithm and conduct computational experiments to evaluate its running time. The experimental results show that the proposed method achieves practical running times.

Friday, July 17 2026, 00:00

Almost Navigable Graphs

Authors: Pratyush Avi, Christopher Musco

Graph-based methods like HNSW, DiskANN, NSG, and others have become an increasingly popular choice for implementing approximate nearest neighbor search (ANNS) in Vector Databases (VecDBs). The success of these methods has motivated the study of how to best construct a search graph for a given dataset. To that end, \emph{navigability} has been identified as a desirable graph property which ensures good ANNS performance when combined with greedy search. However, for a dataset with $n$ vectors, the sparsest navigable graph requires $O(n\sqrt{n})$ edges in the worst-case, and we show empirically that, for typical billion node datasets, 100s of edges are needed per node. This leads to slow search and high memory requirements. Moreover, under standard complexity theoretical assumptions, it was recently established that constructing a sparse navigable graph requires $Ω(n^{2-ε})$ time, which is prohibitive for large datasets. We address these concerns by introducing a relaxed notation of navigability called ``$γ$-almost navigability'' for any $γ\in [0,1]$, with $γ= 1$ corresponding to full navigability. We prove that any dataset (under any distance) admits a $γ$-almost navigable graph with just $O\left(\frac{n}{1-γ}\right)$ edges, linear in the dataset size. We present a randomized algorithm for constructing such a graph in near-linear time. While we prove that $γ$-almost navigability sacrifices the worst-case search guarantees enjoyed by navigability, we show empirically that greedy beam search still performs well in such graphs when $γ< 1$. Indeed, we obtain improved recall-runtime tradeoffs on a variety of datasets compared to fully navigable graphs. Moreover, our graphs are more space efficient, with degree typically less than half that of a fully navigable graph for comparable performance.

Authors: Pratyush Avi, Christopher Musco

Graph-based methods like HNSW, DiskANN, NSG, and others have become an increasingly popular choice for implementing approximate nearest neighbor search (ANNS) in Vector Databases (VecDBs). The success of these methods has motivated the study of how to best construct a search graph for a given dataset. To that end, \emph{navigability} has been identified as a desirable graph property which ensures good ANNS performance when combined with greedy search. However, for a dataset with $n$ vectors, the sparsest navigable graph requires $O(n\sqrt{n})$ edges in the worst-case, and we show empirically that, for typical billion node datasets, 100s of edges are needed per node. This leads to slow search and high memory requirements. Moreover, under standard complexity theoretical assumptions, it was recently established that constructing a sparse navigable graph requires $Ω(n^{2-ε})$ time, which is prohibitive for large datasets. We address these concerns by introducing a relaxed notation of navigability called ``$γ$-almost navigability'' for any $γ\in [0,1]$, with $γ= 1$ corresponding to full navigability. We prove that any dataset (under any distance) admits a $γ$-almost navigable graph with just $O\left(\frac{n}{1-γ}\right)$ edges, linear in the dataset size. We present a randomized algorithm for constructing such a graph in near-linear time. While we prove that $γ$-almost navigability sacrifices the worst-case search guarantees enjoyed by navigability, we show empirically that greedy beam search still performs well in such graphs when $γ< 1$. Indeed, we obtain improved recall-runtime tradeoffs on a variety of datasets compared to fully navigable graphs. Moreover, our graphs are more space efficient, with degree typically less than half that of a fully navigable graph for comparable performance.

Friday, July 17 2026, 00:00

Semitotal domination in unit disk graphs

Authors: Mingjun Liu, Weiping Shang

A set $S \subseteq V$ is called a {\em semitotal dominating set} of $G=(V,E)$ if every vertex in $V \setminus S$ is adjacent to at least one vertex in $S$, and every vertex in $S$ is within distance 2 of another vertex in $S$. The corresponding decision problem is NP-complete even for unit disk graphs. In this paper, we present a 5-factor approximation algorithm for the Minimum Semitotal Domination problem on unit disk graphs in the graph-based input model. The algorithm processes the layers of a Breadth-First-Search tree and constructs a maximal independent set whose vertices satisfy the semitotal condition. For a graph with $n$ vertices and $m$ edges, the algorithm runs in $O(n + m)$ time, and hence in $O(n^2)$ time in the worst case. This improves the previously known 5.75-approximation algorithm with $O(n^3)$ running time.

Authors: Mingjun Liu, Weiping Shang

A set $S \subseteq V$ is called a {\em semitotal dominating set} of $G=(V,E)$ if every vertex in $V \setminus S$ is adjacent to at least one vertex in $S$, and every vertex in $S$ is within distance 2 of another vertex in $S$. The corresponding decision problem is NP-complete even for unit disk graphs. In this paper, we present a 5-factor approximation algorithm for the Minimum Semitotal Domination problem on unit disk graphs in the graph-based input model. The algorithm processes the layers of a Breadth-First-Search tree and constructs a maximal independent set whose vertices satisfy the semitotal condition. For a graph with $n$ vertices and $m$ edges, the algorithm runs in $O(n + m)$ time, and hence in $O(n^2)$ time in the worst case. This improves the previously known 5.75-approximation algorithm with $O(n^3)$ running time.

Friday, July 17 2026, 00:00

The Adversarial Robustness of Sketching and Streaming Algorithms

Authors: David P. Woodruff, Samson Zhou

Sketching and streaming algorithms are vital for handling massive datasets. While classical methods guarantee correctness on fixed inputs, they often fail with adaptive inputs, where future data depends on past algorithm outputs. This is common in settings such as optimization, databases, finance, and network monitoring. This monograph surveys recent advances in adversarial robustness, including techniques for insertion-only streams, connections to differential privacy, and cryptographic methods that achieve adversarial robustness. We also discuss fundamental limitations, especially for linear sketches and streams with insertions and deletions, where robustness often requires polynomial space or sketching dimension. Throughout, we explore core problems like adaptively answering queries for optimization problems, norm estimation, frequency moments, and heavy hitters, and highlight emerging tools and open challenges at the intersection of streaming, sketching, privacy, and adversarial robustness.

Authors: David P. Woodruff, Samson Zhou

Sketching and streaming algorithms are vital for handling massive datasets. While classical methods guarantee correctness on fixed inputs, they often fail with adaptive inputs, where future data depends on past algorithm outputs. This is common in settings such as optimization, databases, finance, and network monitoring. This monograph surveys recent advances in adversarial robustness, including techniques for insertion-only streams, connections to differential privacy, and cryptographic methods that achieve adversarial robustness. We also discuss fundamental limitations, especially for linear sketches and streams with insertions and deletions, where robustness often requires polynomial space or sketching dimension. Throughout, we explore core problems like adaptively answering queries for optimization problems, norm estimation, frequency moments, and heavy hitters, and highlight emerging tools and open challenges at the intersection of streaming, sketching, privacy, and adversarial robustness.

Friday, July 17 2026, 00:00

Exact Online Rank Recycling in Floyd's Uniform Subset Sampler

Authors: Yingqi Zhang

A uniformly random $m$-subset of $[n]=\{0,\ldots,n-1\}$ has entropy $\log_2\binom{n}{m}$. Standard without-replacement procedures often expose an additional ordering coordinate that is absent from the returned set. We show that Floyd's subset sampler admits an exact round-local factorization of this coordinate. In round $r$, let $S$ be an $(r-1)$-subset of $[j]$, let $T\sim\operatorname{Unif}([j+1])$, and let $S'$ be the result of Floyd's transition. If $D$ is the zero-based rank of the original draw $T$ in $S'$, then $(S,T)\leftrightarrow(S',D)$ is a bijection between $\binom{[j]}{r-1}\times[j+1]$ and $\binom{[j+1]}{r}\times[r]$. Consequently, $S'$ and $D$ are independent and uniform on their respective spaces. The digit $D$ can therefore be merged immediately into a residual uniform random state; an induction shows that the partial subset remains independent of that state after every round. For $k=\min(m,n-m)$, the sampling phase uses $O(k\log k)$ time and $O(k)$ auxiliary space with an order-statistic tree; explicitly materializing a complement incurs the unavoidable output cost. The combinatorial layer avoids binomial-coefficient arithmetic and recovers the complete $k!$ state-space factor exactly. We also give a finite counterexample showing that analogous immediate rank recycling in a partial Fisher-Yates array is invalid because the unselected suffix retains a correlated ordering. A 64-bit Rust implementation is checked by exhaustive state-space enumeration for all $n\leq 8$ and by an entropy-accounting trace for choosing $20{,}000$ of $30{,}000$ items. We make no claim of runtime superiority over existing subset samplers.

Authors: Yingqi Zhang

A uniformly random $m$-subset of $[n]=\{0,\ldots,n-1\}$ has entropy $\log_2\binom{n}{m}$. Standard without-replacement procedures often expose an additional ordering coordinate that is absent from the returned set. We show that Floyd's subset sampler admits an exact round-local factorization of this coordinate. In round $r$, let $S$ be an $(r-1)$-subset of $[j]$, let $T\sim\operatorname{Unif}([j+1])$, and let $S'$ be the result of Floyd's transition. If $D$ is the zero-based rank of the original draw $T$ in $S'$, then $(S,T)\leftrightarrow(S',D)$ is a bijection between $\binom{[j]}{r-1}\times[j+1]$ and $\binom{[j+1]}{r}\times[r]$. Consequently, $S'$ and $D$ are independent and uniform on their respective spaces. The digit $D$ can therefore be merged immediately into a residual uniform random state; an induction shows that the partial subset remains independent of that state after every round. For $k=\min(m,n-m)$, the sampling phase uses $O(k\log k)$ time and $O(k)$ auxiliary space with an order-statistic tree; explicitly materializing a complement incurs the unavoidable output cost. The combinatorial layer avoids binomial-coefficient arithmetic and recovers the complete $k!$ state-space factor exactly. We also give a finite counterexample showing that analogous immediate rank recycling in a partial Fisher-Yates array is invalid because the unselected suffix retains a correlated ordering. A 64-bit Rust implementation is checked by exhaustive state-space enumeration for all $n\leq 8$ and by an entropy-accounting trace for choosing $20{,}000$ of $30{,}000$ items. We make no claim of runtime superiority over existing subset samplers.

Friday, July 17 2026, 00:00

Online Beck--Fiala Down to Logarithmic Sparsity