Theory of Computing Report

The Complexity of Min-Max Optimization for Quadratic Polynomials

Authors: Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alexandros Hollender

We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratic polynomials. This holds even when the polynomials are multilinear, each variable appears in at most three monomials, and the approximation factor is inverse polynomial. As a direct consequence, we obtain the first PPAD-hardness results for two-team zero-sum polymatrix games.

Authors: Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alexandros Hollender

We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratic polynomials. This holds even when the polynomials are multilinear, each variable appears in at most three monomials, and the approximation factor is inverse polynomial. As a direct consequence, we obtain the first PPAD-hardness results for two-team zero-sum polymatrix games.

Tuesday, June 16 2026, 00:00

Worst-case depth hierarchy for shallow quantum circuits

from arXiv: Computational Complexity

Authors: Min-Hsiu Hsieh, Michael de Oliveira, Sathyawageeswar Subramanian, Xingjian Zhang

Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored. We prove an explicit depth hierarchy theorem for $\mathsf{QNC}^0$. For each $d\ge 12$, we construct a family of two-round interactive problems on which no depth-$(d-1)$ quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than $d$ by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every $d$, yielding a hierarchy of problems that show unconditional quantum advantage of $\mathsf{QNC}^0$ over $\mathsf{NC}^0$. A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits. These results show that increasing depth strictly increases computational power within $\mathsf{QNC}^0$, establishing a genuinely quantum hierarchy.

Authors: Min-Hsiu Hsieh, Michael de Oliveira, Sathyawageeswar Subramanian, Xingjian Zhang

Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored. We prove an explicit depth hierarchy theorem for $\mathsf{QNC}^0$. For each $d\ge 12$, we construct a family of two-round interactive problems on which no depth-$(d-1)$ quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than $d$ by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every $d$, yielding a hierarchy of problems that show unconditional quantum advantage of $\mathsf{QNC}^0$ over $\mathsf{NC}^0$. A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits. These results show that increasing depth strictly increases computational power within $\mathsf{QNC}^0$, establishing a genuinely quantum hierarchy.

Tuesday, June 16 2026, 00:00

The Computational Complexity of Team Zero-Sum Games

from arXiv: Computational Complexity

Authors: Ioannis Anagnostides, Ioannis Panageas, Tuomas Sandholm, Jingming Yan

A celebrated consequence of the minimax theorem is that two-player zero-sum games admit a tractable equilibrium characterization. In many central applications, however, each side comprises multiple independent agents who share a common objective but cannot perfectly coordinate their actions. Such settings can be modeled as \emph{team zero-sum games}, a natural generalization of both two-player zero-sum games and potential games -- the two most well-studied classes of games in algorithmic game theory. In this paper, we settle the complexity of team zero-sum games by establishing that computing Nash equilibria is \PPAD-complete. As a result, despite the global adversarial structure, team zero-sum games are as hard as general-sum games. Our hardness result holds even when i) the precision is inverse polynomial, thereby ruling out a fully polynomial-time approximation scheme (unless $¶= \PPAD$); ii) each team consists of only two players; and iii) the underlying class of games is polymatrix. As a byproduct, we resolve the complexity of group-wise zero-sum polymatrix games, a class introduced and examined in the seminal work of Cai and Daskalakis (SODA '11), and more recently highlighted by Hollender, Maystre, and Nagarajan (ICLR '25). Moreover, we show that computing a first-order stationary point in min-max optimization is \PPAD-complete even for quadratic (multilinear) objectives. From a technical standpoint, we develop a series of team zero-sum game gadgets that allow us to simulate the breakthrough reduction of Bernasconi and Castiglioni (STOC '26). Moreover, to obtain hardness results for quadratic objectives, we make use of a general technique based on linear local approximation, which is of independent interest.

Authors: Ioannis Anagnostides, Ioannis Panageas, Tuomas Sandholm, Jingming Yan

A celebrated consequence of the minimax theorem is that two-player zero-sum games admit a tractable equilibrium characterization. In many central applications, however, each side comprises multiple independent agents who share a common objective but cannot perfectly coordinate their actions. Such settings can be modeled as \emph{team zero-sum games}, a natural generalization of both two-player zero-sum games and potential games -- the two most well-studied classes of games in algorithmic game theory. In this paper, we settle the complexity of team zero-sum games by establishing that computing Nash equilibria is \PPAD-complete. As a result, despite the global adversarial structure, team zero-sum games are as hard as general-sum games. Our hardness result holds even when i) the precision is inverse polynomial, thereby ruling out a fully polynomial-time approximation scheme (unless $¶= \PPAD$); ii) each team consists of only two players; and iii) the underlying class of games is polymatrix. As a byproduct, we resolve the complexity of group-wise zero-sum polymatrix games, a class introduced and examined in the seminal work of Cai and Daskalakis (SODA '11), and more recently highlighted by Hollender, Maystre, and Nagarajan (ICLR '25). Moreover, we show that computing a first-order stationary point in min-max optimization is \PPAD-complete even for quadratic (multilinear) objectives. From a technical standpoint, we develop a series of team zero-sum game gadgets that allow us to simulate the breakthrough reduction of Bernasconi and Castiglioni (STOC '26). Moreover, to obtain hardness results for quadratic objectives, we make use of a general technique based on linear local approximation, which is of independent interest.

Tuesday, June 16 2026, 00:00

Revisiting average case complexity of multilevel syllogistic: From the 1995 Courant Technical Report to Lean 4 Formalization

from arXiv: Computational Complexity

Authors: Lars Warren Ericson

We describe a Lean~4 formalization revisiting NYU Courant Technical Report TR1995-711 on the average-case complexity of Multilevel Syllogistic (MLS). The development encodes Reischuk--Schindelhauer average-case classes, an axiomatic MLS/EMLS semantics layer, a partial Ferro--Omodeo--Schwartz decision procedure with proved soundness and partial completeness on a membership-free fragment, serialization and step budgets, and conditional NP-average completeness and non-AvP hardness corollaries modulo explicitly documented structural axioms. Full Lean sources are inlined in the appendix modules.

Authors: Lars Warren Ericson

We describe a Lean~4 formalization revisiting NYU Courant Technical Report TR1995-711 on the average-case complexity of Multilevel Syllogistic (MLS). The development encodes Reischuk--Schindelhauer average-case classes, an axiomatic MLS/EMLS semantics layer, a partial Ferro--Omodeo--Schwartz decision procedure with proved soundness and partial completeness on a membership-free fragment, serialization and step budgets, and conditional NP-average completeness and non-AvP hardness corollaries modulo explicitly documented structural axioms. Full Lean sources are inlined in the appendix modules.

Tuesday, June 16 2026, 00:00

Polynomial-Time Mistake-Bounded Language Generation

from arXiv: Computational Complexity

Authors: Héctor Jimenez, Alexander Kozachinskiy, Vicente Opazo

In this note, we introduce a polynomial-time version of the mistake-bounded language generation (MBLG) framework due to Kleinberg, Peale, and Reingold (2026). We observe that the family of parities of variables, and the family of conjunctions of literals, are polynomial-time MBLG. Our main result states that the family of monotone Boolean functions with polynomially-many maxterms is polynomial-time MBLG. This family includes all monotone Boolean functions, computable by polynomial-size decision trees. Our technique can be presented as a new combinatorial game about writing numbers on a board.

Authors: Héctor Jimenez, Alexander Kozachinskiy, Vicente Opazo

In this note, we introduce a polynomial-time version of the mistake-bounded language generation (MBLG) framework due to Kleinberg, Peale, and Reingold (2026). We observe that the family of parities of variables, and the family of conjunctions of literals, are polynomial-time MBLG. Our main result states that the family of monotone Boolean functions with polynomially-many maxterms is polynomial-time MBLG. This family includes all monotone Boolean functions, computable by polynomial-size decision trees. Our technique can be presented as a new combinatorial game about writing numbers on a board.

Tuesday, June 16 2026, 00:00

Quiet Planting for $k$-SAT, Multiple Solutions of Arbitrary Geometry

from arXiv: Computational Complexity

Authors: Ali Ahmadi, Kiarash Banihashem, Iman Gholami, Mohammad Taghi Hajiaghayi, Jan Olkowski

Recent work on "quiet planting" in combinatorial optimization aims to generate instances with a hidden solution that is hard to recover, typically by making the planted distribution statistically indistinguishable from uniform for specific algorithms, such as statistical queries. A prominent example is planted $k$-SAT, where $O(n^{k/2})$ clauses can be planted while maintaining indistinguishability from uniform instances, evidenced by prior hardness results which also align with findings in SAT refutation. Despite extensive research and practical use in benchmarking SAT solvers, the challenge of quietly planting multiple solutions while preserving hardness has remained an open problem. This work initiates the study of quiet planting with an arbitrary number of solutions, proposing the first method to construct quiet planting distributions for $k$-SAT formulas that accommodate more than one solution. We provide statistical query lower bounds for distinguishing these planted instances from uniform ones, and our method allows for planting solutions with arbitrary geometric relationships, including varying Hamming distances. A key innovation facilitating multiple solutions is the ability to incorporate arbitrary correlations between variable selection in clauses and their negation patterns, departing from prior approaches. We also investigate the worst-case complexity of SAT by showing the difficulty in distinguishing satisfiable instances with numerous solutions from unsatisfiable ones, addressing an open problem of Hsieh, Mohanty, and Xu (CCC'22). Technically, we generalize $(r-1)$-wise uniformness in clause distributions, proving hardness if marginal negation distributions are $(r-1)$-wise uniform. We also reveal a connection to binary linear codes, showing a $[k, t, r]$ code can guide planting up to $2^t - 1$ solutions on $k$ variables.

Authors: Ali Ahmadi, Kiarash Banihashem, Iman Gholami, Mohammad Taghi Hajiaghayi, Jan Olkowski

Recent work on "quiet planting" in combinatorial optimization aims to generate instances with a hidden solution that is hard to recover, typically by making the planted distribution statistically indistinguishable from uniform for specific algorithms, such as statistical queries. A prominent example is planted $k$-SAT, where $O(n^{k/2})$ clauses can be planted while maintaining indistinguishability from uniform instances, evidenced by prior hardness results which also align with findings in SAT refutation. Despite extensive research and practical use in benchmarking SAT solvers, the challenge of quietly planting multiple solutions while preserving hardness has remained an open problem. This work initiates the study of quiet planting with an arbitrary number of solutions, proposing the first method to construct quiet planting distributions for $k$-SAT formulas that accommodate more than one solution. We provide statistical query lower bounds for distinguishing these planted instances from uniform ones, and our method allows for planting solutions with arbitrary geometric relationships, including varying Hamming distances. A key innovation facilitating multiple solutions is the ability to incorporate arbitrary correlations between variable selection in clauses and their negation patterns, departing from prior approaches. We also investigate the worst-case complexity of SAT by showing the difficulty in distinguishing satisfiable instances with numerous solutions from unsatisfiable ones, addressing an open problem of Hsieh, Mohanty, and Xu (CCC'22). Technically, we generalize $(r-1)$-wise uniformness in clause distributions, proving hardness if marginal negation distributions are $(r-1)$-wise uniform. We also reveal a connection to binary linear codes, showing a $[k, t, r]$ code can guide planting up to $2^t - 1$ solutions on $k$ variables.

Tuesday, June 16 2026, 00:00

The Exact Reach of Conormal Invariants in Determinantal Complexity: a Quadratic No-Go Theorem

from arXiv: Computational Complexity

Authors: Karthik Sheshadri

We study the polar (conormal) method for determinantal-complexity lower bounds, including the framework used in the companion bound dc(sum_i x_i^N) >= (1/(4e)-o(1))N^2. We obtain quantitative results on both sides of the method: the intersection-theoretic complexity of kernel-incidence constructions and the size of the characteristic-cycle invariants they can detect. For a size-m determinantal representation in N variables, we identify the corank-one kernel incidence with the conormal variety of the generic determinant. An excess-one degeneracy-locus computation yields a closed formula for the associated polar intersection number T(N,m), together with rational generating functions and explicit evaluations including T(3,m)=m(m-1), T(4,m)=m(m-1)^2, and T(5,5)=220. We also compare these counts with the multihomogeneous Bezout estimates used in the companion work and establish asymptotic sharpness at the per-root scale. For an arbitrary degree-d hypersurface X in P^(N-1), possibly singular and reducible, we prove a uniform bound on the conormal multidegrees appearing in its characteristic cycle: m_S delta_i(Con(S-bar)) <= 8(d-1)^(N-1)+O(N). The proof combines bounds on generic-slice Euler characteristics, an explicit analysis of the transform from Euler-characteristic data to conormal multidegrees, and Kashiwara positivity for characteristic cycles. Similar bounds are obtained for vanishing-cycle and Milnor-class variants. Combining these results yields general upper bounds on determinantal-complexity lower bounds obtainable from characteristic-cycle invariants via kernel-corank incidence constructions. In particular, along the diagonal d=N, the resulting lower bounds are at most quadratic in N. We conclude by discussing possible extensions involving scheme-theoretic conormal information and other geometric invariants.

Authors: Karthik Sheshadri

We study the polar (conormal) method for determinantal-complexity lower bounds, including the framework used in the companion bound dc(sum_i x_i^N) >= (1/(4e)-o(1))N^2. We obtain quantitative results on both sides of the method: the intersection-theoretic complexity of kernel-incidence constructions and the size of the characteristic-cycle invariants they can detect. For a size-m determinantal representation in N variables, we identify the corank-one kernel incidence with the conormal variety of the generic determinant. An excess-one degeneracy-locus computation yields a closed formula for the associated polar intersection number T(N,m), together with rational generating functions and explicit evaluations including T(3,m)=m(m-1), T(4,m)=m(m-1)^2, and T(5,5)=220. We also compare these counts with the multihomogeneous Bezout estimates used in the companion work and establish asymptotic sharpness at the per-root scale. For an arbitrary degree-d hypersurface X in P^(N-1), possibly singular and reducible, we prove a uniform bound on the conormal multidegrees appearing in its characteristic cycle: m_S delta_i(Con(S-bar)) <= 8(d-1)^(N-1)+O(N). The proof combines bounds on generic-slice Euler characteristics, an explicit analysis of the transform from Euler-characteristic data to conormal multidegrees, and Kashiwara positivity for characteristic cycles. Similar bounds are obtained for vanishing-cycle and Milnor-class variants. Combining these results yields general upper bounds on determinantal-complexity lower bounds obtainable from characteristic-cycle invariants via kernel-corank incidence constructions. In particular, along the diagonal d=N, the resulting lower bounds are at most quadratic in N. We conclude by discussing possible extensions involving scheme-theoretic conormal information and other geometric invariants.

Tuesday, June 16 2026, 00:00

Three-Terminal Reachability-Preserving Minimum Node Cut: Planar Hardness and a General-Graph $O(\sqrt n)$-Approximation

from arXiv: Computational Complexity

Authors: Qi Duan

We study the three-terminal reachability-preserving minimum node cut problem (\RPMNC). The input is an undirected graph $G=(V,E)$, nonnegative vertex weights on nonterminal vertices, two protected terminals $s_1,s_2$, and a target terminal $t$. The goal is to delete a minimum-weight set of nonterminal vertices so that $t$ is disconnected from the protected terminals, while $s_1$ and $s_2$ remain connected. This problem captures a basic ``separate while preserve'' requirement that arises in biological intervention design, image analysis with connectivity constraints, and cyber-security attack graph mitigation, where deleting or blocking a node represents preventing the corresponding action, state, or biological entity from participating in a harmful pathway. We prove two results. First, the weighted planar version of three-terminal \RPMNC{} is NP-complete. The reduction is from \textsc{Independent Set} on 3-regular Hamiltonian planar graphs and uses a one-sided blocker construction. Second, we give a polynomial-time $O(\sqrt n)$-approximation algorithm for general graphs. The algorithm is based on an exact path--separator identity, a directed split-graph representation of rooted vertex separators, and a root-linear approximation of a monotone submodular separator function.

Authors: Qi Duan

We study the three-terminal reachability-preserving minimum node cut problem (\RPMNC). The input is an undirected graph $G=(V,E)$, nonnegative vertex weights on nonterminal vertices, two protected terminals $s_1,s_2$, and a target terminal $t$. The goal is to delete a minimum-weight set of nonterminal vertices so that $t$ is disconnected from the protected terminals, while $s_1$ and $s_2$ remain connected. This problem captures a basic ``separate while preserve'' requirement that arises in biological intervention design, image analysis with connectivity constraints, and cyber-security attack graph mitigation, where deleting or blocking a node represents preventing the corresponding action, state, or biological entity from participating in a harmful pathway. We prove two results. First, the weighted planar version of three-terminal \RPMNC{} is NP-complete. The reduction is from \textsc{Independent Set} on 3-regular Hamiltonian planar graphs and uses a one-sided blocker construction. Second, we give a polynomial-time $O(\sqrt n)$-approximation algorithm for general graphs. The algorithm is based on an exact path--separator identity, a directed split-graph representation of rooted vertex separators, and a root-linear approximation of a monotone submodular separator function.

Tuesday, June 16 2026, 00:00

Polynomial-Time Riesz-Energy Subset Selection for Ordered Point Sets on Lines and $\ell_1$-Staircases

from arXiv: Computational Geometry

Authors: Michael T. M. Emmerich

We study the one-dimensional fixed-cardinality minimum Riesz $s$-energy subset problem with fixed exponent $s > 0$: given ordered real points $x_1 < x_2 < \cdots < x_n$, a positive parameter $s>0$, and a cardinality $k$, choose indices $1 \leq i_1 < \cdots < i_k \leq n$ minimizing $E_s(i_1,\ldots,i_k)=\sum_{1\leq p0$; bit-complexity claims require the arithmetic assumptions stated in the complexity section. The same structure also yields an explicit minimum $S$--$T$ cut algorithm with $k(n-k)$ threshold variables and $O(k^2(n-k)^2)$ finite pairwise edges. The resulting graph has $N=k(n-k)$ nodes and $M=O(k^2(n-k)^2)$ arcs after an $O(k^2(n-k)^2)$ coefficient-construction step; an $O(NM)$ max-flow bound gives an $O(k^3(n-k)^3)$ min-cut step, while the conservative $O(N^2M)$ bound gives $O(k^4(n-k)^4)$. Due to isometry, the results apply directly to subset selection on $\ell_1$ staircases, such as choosing diverse and representative Pareto front or skyline approximations in two dimensions. An open-source Python implementation of the min-cut algorithm accompanies the reproducibility material.

Authors: Michael T. M. Emmerich

We study the one-dimensional fixed-cardinality minimum Riesz $s$-energy subset problem with fixed exponent $s > 0$: given ordered real points $x_1 < x_2 < \cdots < x_n$, a positive parameter $s>0$, and a cardinality $k$, choose indices $1 \leq i_1 < \cdots < i_k \leq n$ minimizing $E_s(i_1,\ldots,i_k)=\sum_{1\leq p0$; bit-complexity claims require the arithmetic assumptions stated in the complexity section. The same structure also yields an explicit minimum $S$--$T$ cut algorithm with $k(n-k)$ threshold variables and $O(k^2(n-k)^2)$ finite pairwise edges. The resulting graph has $N=k(n-k)$ nodes and $M=O(k^2(n-k)^2)$ arcs after an $O(k^2(n-k)^2)$ coefficient-construction step; an $O(NM)$ max-flow bound gives an $O(k^3(n-k)^3)$ min-cut step, while the conservative $O(N^2M)$ bound gives $O(k^4(n-k)^4)$. Due to isometry, the results apply directly to subset selection on $\ell_1$ staircases, such as choosing diverse and representative Pareto front or skyline approximations in two dimensions. An open-source Python implementation of the min-cut algorithm accompanies the reproducibility material.

Tuesday, June 16 2026, 00:00

Threshold Minimum Cut with Terminal Quotas: Logarithmic and Planar Approximation Algorithms

from arXiv: Data Structures and Algorithms

Authors: Qi Duan

We study threshold minimum cut problems with a distinguished root vertex, a set of terminals, and a quota. In the threshold minimum edge cut problem (\TMEC), the goal is to find a minimum-cost edge cut that disconnects at least $k$ terminals from the root. In the threshold minimum node cut problem (\TMNC), the goal is to delete a minimum-cost set of nonterminal, nonroot vertices so that at least $k$ terminals become disconnected from the root. We prove three approximation guarantees. First, undirected general-graph \TMEC{} admits a randomized polynomial-time expected $O(\log n)$ approximation via a Räcke-style cut-dominating tree decomposition and an exact dynamic program on trees. A standard repetition argument gives the same asymptotic ratio with high probability. Second, planar \TMEC{} admits a factor-$2$ approximation by reducing the threshold condition to planar weighted balanced cut. Third, bounded-degree planar \TMNC{} admits a $2Δ$-approximation, where $Δ$ is the maximum degree of a deletable vertex, by reducing the node-cost problem to the planar edge-cut problem on the same graph. The results separate exact-quota guarantees from bicriteria small-set-expansion-type guarantees and identify the unbounded-degree planar node-cut case as the main remaining obstacle.

Authors: Qi Duan

We study threshold minimum cut problems with a distinguished root vertex, a set of terminals, and a quota. In the threshold minimum edge cut problem (\TMEC), the goal is to find a minimum-cost edge cut that disconnects at least $k$ terminals from the root. In the threshold minimum node cut problem (\TMNC), the goal is to delete a minimum-cost set of nonterminal, nonroot vertices so that at least $k$ terminals become disconnected from the root. We prove three approximation guarantees. First, undirected general-graph \TMEC{} admits a randomized polynomial-time expected $O(\log n)$ approximation via a Räcke-style cut-dominating tree decomposition and an exact dynamic program on trees. A standard repetition argument gives the same asymptotic ratio with high probability. Second, planar \TMEC{} admits a factor-$2$ approximation by reducing the threshold condition to planar weighted balanced cut. Third, bounded-degree planar \TMNC{} admits a $2Δ$-approximation, where $Δ$ is the maximum degree of a deletable vertex, by reducing the node-cost problem to the planar edge-cut problem on the same graph. The results separate exact-quota guarantees from bicriteria small-set-expansion-type guarantees and identify the unbounded-degree planar node-cut case as the main remaining obstacle.

Tuesday, June 16 2026, 00:00

A constant-factor approximation of the Gromov-Hausdorff distance in the plane

from arXiv: Data Structures and Algorithms

Authors: Sushovan Majhi

We give the first polynomial-time constant-factor approximation of the Gromov--Hausdorff distance $d_{GH}$ between finite point sets in the Euclidean plane; in fixed Euclidean dimension such an approximation was previously known only on the line (Majhi, Vitter, and Wenk, 2024). Its engine is the bijective (bottleneck) Gromov--Hausdorff distance $d_{GH}^{bij}$: for two equal-size sets the least additive distortion $\max_{i,j}|d_X(i,j) - d_Y(σi, σj)|$ of a bijection $σ$ equals $2\,d_{GH}^{bij}$, which we likewise approximate within an absolute constant. Approximating additive distortion goes back to Hall and Papadimitriou (2005), who gave a $2$-approximation on the line and observed approximation within $3$ to be NP-hard in dimension three; the planar case they left open is the one we settle. A fat-or-collinear dichotomy drives both bounds: a fat set is aligned by a single rigid motion, while a near-collinear set is split into clusters matched along their dendrogram in one flat, scale-free pass, with relative orientations and per-node reflection signs -- at every scale of the dendrogram -- recovered by global cuts. Relaxing bijections to correspondences yields $d_{GH}$ itself, which reduces to a lone within-cluster-multiplicity kernel -- the pairs an optimal correspondence collapses -- that the same theory closes. Matching lower bounds -- a dimension drop, a multiplicity gap, and a reflection barrier acting at every scale -- show each ingredient is necessary.

Authors: Sushovan Majhi

We give the first polynomial-time constant-factor approximation of the Gromov--Hausdorff distance $d_{GH}$ between finite point sets in the Euclidean plane; in fixed Euclidean dimension such an approximation was previously known only on the line (Majhi, Vitter, and Wenk, 2024). Its engine is the bijective (bottleneck) Gromov--Hausdorff distance $d_{GH}^{bij}$: for two equal-size sets the least additive distortion $\max_{i,j}|d_X(i,j) - d_Y(σi, σj)|$ of a bijection $σ$ equals $2\,d_{GH}^{bij}$, which we likewise approximate within an absolute constant. Approximating additive distortion goes back to Hall and Papadimitriou (2005), who gave a $2$-approximation on the line and observed approximation within $3$ to be NP-hard in dimension three; the planar case they left open is the one we settle. A fat-or-collinear dichotomy drives both bounds: a fat set is aligned by a single rigid motion, while a near-collinear set is split into clusters matched along their dendrogram in one flat, scale-free pass, with relative orientations and per-node reflection signs -- at every scale of the dendrogram -- recovered by global cuts. Relaxing bijections to correspondences yields $d_{GH}$ itself, which reduces to a lone within-cluster-multiplicity kernel -- the pairs an optimal correspondence collapses -- that the same theory closes. Matching lower bounds -- a dimension drop, a multiplicity gap, and a reflection barrier acting at every scale -- show each ingredient is necessary.

Tuesday, June 16 2026, 00:00

Coresets for Continuous $k$-Center in Hyperbolic Space

from arXiv: Data Structures and Algorithms

Authors: Eunku Park

We construct coresets for the continuous $k$-center problem in fixed-dimensional hyperbolic space $\mathbb H^D$. The input is a set $P$ of $n$ points in $\mathbb H^D$, where $D=O(1)$, and the centers may be placed anywhere in the ambient hyperbolic space. Given $\varepsilon\in(0,1)$, we construct a subset $P_\varepsilon\subseteq P$ such that every optimal continuous $k$-center solution for $P_\varepsilon$ is a $(1+\varepsilon)$-approximation for $P$. The main difficulty is the exponential volume growth of hyperbolic balls, which prevents a direct grid-based coreset from having size independent of the input radius. We overcome this by dividing the construction according to the farthest-first scale. At bounded scales, we use local Euclidean grids in the Poincaré ball model. At intermediate scales, we use an anchor-centered shell--cone decomposition together with exact distance profiles obtained from the hyperbolic law of cosines. At large scales, we avoid discretizing the ambient ball and instead keep input witnesses indexed by coarse profiles of the induced $k$-center distance functions on each shell--cone bucket. The resulting coreset has size $\left(1/\varepsilon\right)^{O(kD)}$ and can be constructed in time $O(nk\left(1/\varepsilon\right)^{O(kD)}).$ Both bounds are independent of the input radius, and the coreset size is also independent of $n$. Consequently, for fixed $D$, $k$, and $\varepsilon$, this gives a linear-time construction of a constant-size coreset for the continuous $k$-center problem in hyperbolic space.

Authors: Eunku Park

We construct coresets for the continuous $k$-center problem in fixed-dimensional hyperbolic space $\mathbb H^D$. The input is a set $P$ of $n$ points in $\mathbb H^D$, where $D=O(1)$, and the centers may be placed anywhere in the ambient hyperbolic space. Given $\varepsilon\in(0,1)$, we construct a subset $P_\varepsilon\subseteq P$ such that every optimal continuous $k$-center solution for $P_\varepsilon$ is a $(1+\varepsilon)$-approximation for $P$. The main difficulty is the exponential volume growth of hyperbolic balls, which prevents a direct grid-based coreset from having size independent of the input radius. We overcome this by dividing the construction according to the farthest-first scale. At bounded scales, we use local Euclidean grids in the Poincaré ball model. At intermediate scales, we use an anchor-centered shell--cone decomposition together with exact distance profiles obtained from the hyperbolic law of cosines. At large scales, we avoid discretizing the ambient ball and instead keep input witnesses indexed by coarse profiles of the induced $k$-center distance functions on each shell--cone bucket. The resulting coreset has size $\left(1/\varepsilon\right)^{O(kD)}$ and can be constructed in time $O(nk\left(1/\varepsilon\right)^{O(kD)}).$ Both bounds are independent of the input radius, and the coreset size is also independent of $n$. Consequently, for fixed $D$, $k$, and $\varepsilon$, this gives a linear-time construction of a constant-size coreset for the continuous $k$-center problem in hyperbolic space.

Tuesday, June 16 2026, 00:00

Online Matching with KIID Edge Arrivals

from arXiv: Data Structures and Algorithms

Authors: Yilong Feng, Haolong Li, Xiaowei Wu

In the classic online stochastic matching proposed by Feldman et al. (FOCS 2009), there is a known bipartite type-graph, where one side of the graph is given offline. Upon the arrival of each online vertex, its type is sampled independently and identically from the other side of the type-graph. This model has been extensively studied over the past decade, yielding a rich body of theoretical results. In this paper, we initiate the study of an edge arrival model for online stochastic matching. In our model, the online edges are sampled independently and identically (KIID) from a known type-graph, which need not be bipartite. We first show that the Greedy algorithm cannot achieve a competitive ratio strictly better than $0.5$ while the Suggested Matching algorithm has a competitive ratio of $1-1/e$ under the assumption of integral arrival rates, matching its performance in the one-sided vertex arrival model. We then propose a two-stage algorithm that combines Greedy and Suggested Matching, and show that its competitive ratio is strictly higher than $1-1/e$ for integral arrival rates. While our algorithm is simple, its analysis is intricate and builds upon the Natural LP, which has been proven very powerful in vertex arrival models. Our result reveals that even in the more challenging edge arrival setting for general graphs, competitive ratios better than $1-1/e$ are still possible, given the known distributions.

Authors: Yilong Feng, Haolong Li, Xiaowei Wu

In the classic online stochastic matching proposed by Feldman et al. (FOCS 2009), there is a known bipartite type-graph, where one side of the graph is given offline. Upon the arrival of each online vertex, its type is sampled independently and identically from the other side of the type-graph. This model has been extensively studied over the past decade, yielding a rich body of theoretical results. In this paper, we initiate the study of an edge arrival model for online stochastic matching. In our model, the online edges are sampled independently and identically (KIID) from a known type-graph, which need not be bipartite. We first show that the Greedy algorithm cannot achieve a competitive ratio strictly better than $0.5$ while the Suggested Matching algorithm has a competitive ratio of $1-1/e$ under the assumption of integral arrival rates, matching its performance in the one-sided vertex arrival model. We then propose a two-stage algorithm that combines Greedy and Suggested Matching, and show that its competitive ratio is strictly higher than $1-1/e$ for integral arrival rates. While our algorithm is simple, its analysis is intricate and builds upon the Natural LP, which has been proven very powerful in vertex arrival models. Our result reveals that even in the more challenging edge arrival setting for general graphs, competitive ratios better than $1-1/e$ are still possible, given the known distributions.

Tuesday, June 16 2026, 00:00

Single-item lot sizing problem under budgeted lead-time uncertainty

from arXiv: Data Structures and Algorithms

Authors: Romain Guillaume, Adam Kasperski, Szymon Wrobel, Pawel Zielinski

In this paper, a single-item lot sizing problem with backordering is discussed. The time horizon is divided into planning periods, characterized by fixed and variable production costs, and future delivery periods with specified demands, where inventory holding and backordering costs may occur. For each planning period, a common nominal lead time is given. The true lead times can deviate to some extent from the nominal one, and their exact values are unknown at the planning step. We assume that lead times take only integer values and splitting production orders is not allowed. Furthermore, order crossovers are prohibited; thus, an order placed earlier cannot arrive after one placed later. A budgeted uncertainty set of possible lead-time scenarios is defined, where a budget allows us to control the amount of uncertainty of lead times. It is shown how to construct a family of production plans varying from the most optimistic (a best lead-time scenario occurs) to the most pessimistic (a worst lead-time scenario occurs). In order to compute these plans the R* criterion is applied which generalizes the conservative robust min-max criterion, commonly used in robust optimization. The computational complexity of the problem is investigated. Polynomial, pseudopolynomial time algorithms, and mixed integer programming formulations are proposed to solve the general problem and its special cases. The results of computational tests are provided that demonstrate that using the R* criterion can significantly enlarge the set of candidate production plans.

Authors: Romain Guillaume, Adam Kasperski, Szymon Wrobel, Pawel Zielinski

In this paper, a single-item lot sizing problem with backordering is discussed. The time horizon is divided into planning periods, characterized by fixed and variable production costs, and future delivery periods with specified demands, where inventory holding and backordering costs may occur. For each planning period, a common nominal lead time is given. The true lead times can deviate to some extent from the nominal one, and their exact values are unknown at the planning step. We assume that lead times take only integer values and splitting production orders is not allowed. Furthermore, order crossovers are prohibited; thus, an order placed earlier cannot arrive after one placed later. A budgeted uncertainty set of possible lead-time scenarios is defined, where a budget allows us to control the amount of uncertainty of lead times. It is shown how to construct a family of production plans varying from the most optimistic (a best lead-time scenario occurs) to the most pessimistic (a worst lead-time scenario occurs). In order to compute these plans the R* criterion is applied which generalizes the conservative robust min-max criterion, commonly used in robust optimization. The computational complexity of the problem is investigated. Polynomial, pseudopolynomial time algorithms, and mixed integer programming formulations are proposed to solve the general problem and its special cases. The results of computational tests are provided that demonstrate that using the R* criterion can significantly enlarge the set of candidate production plans.

Tuesday, June 16 2026, 00:00

C^2: Cache-Conscious Succinct Tries with Adaptive Unary Path Compression

from arXiv: Data Structures and Algorithms

Authors: Kepan Zhang, Tiancheng Zhao, Helen Xu

Succinct tries are powerful string dictionaries because of their low memory footprint and fast query performance. However, existing succinct trie implementations face two key challenges to spatial locality: 1) they incur unnecessary cache misses during queries, especially during trie navigation operations, and 2) they waste significant space when the data contains many unary paths. We propose C^2, a set of two techniques: C_1 introduces a more cache-friendly layout for the \bv underlying succinct tries, and C_2 compresses redundant unary paths. We thoroughly redesign three state-of-the-art succinct tries: FST, CoCo-trie, and Marisa, producing C^2-FST, C^2-CoCo, and C^2-Marisa. Experiments on six diverse datasets show that the C_1 optimization improves query performance by 1.58x, 1.12x, and 1.42x, respectively, compared to the original FST, CoCo-trie, and Marisa. Furthermore, the C_2 optimization achieves a 1.3x smaller memory footprint on average. The succinct tries optimized with both aspects of C^2 achieve better space-time tradeoffs than their original versions and other state-of-the-art succinct tries, while using significantly less space than non-succinct tries like ART and C-ART.

Authors: Kepan Zhang, Tiancheng Zhao, Helen Xu

Succinct tries are powerful string dictionaries because of their low memory footprint and fast query performance. However, existing succinct trie implementations face two key challenges to spatial locality: 1) they incur unnecessary cache misses during queries, especially during trie navigation operations, and 2) they waste significant space when the data contains many unary paths. We propose C^2, a set of two techniques: C_1 introduces a more cache-friendly layout for the \bv underlying succinct tries, and C_2 compresses redundant unary paths. We thoroughly redesign three state-of-the-art succinct tries: FST, CoCo-trie, and Marisa, producing C^2-FST, C^2-CoCo, and C^2-Marisa. Experiments on six diverse datasets show that the C_1 optimization improves query performance by 1.58x, 1.12x, and 1.42x, respectively, compared to the original FST, CoCo-trie, and Marisa. Furthermore, the C_2 optimization achieves a 1.3x smaller memory footprint on average. The succinct tries optimized with both aspects of C^2 achieve better space-time tradeoffs than their original versions and other state-of-the-art succinct tries, while using significantly less space than non-succinct tries like ART and C-ART.

Tuesday, June 16 2026, 00:00

Problems related to strong connectivity and strong biconnectivity

from arXiv: Data Structures and Algorithms

Authors: Raed Jaberi

Let $G=(V,E)$ be a strong biconnected graph and let $B \subseteq V$ such that for each vertex $w \in B$, the subgraph $G \setminus \lbrace w\rbrace$ is strongly connected. In this paper we study the problem of computing a subset $E_β \subseteq E$ of minimum size such that the subgraph $G_β=(V,E_β)$ is strongly biconnected and for each vertex $w \in B$, the subgraph $G_β \setminus \lbrace w\rbrace$ is strongly connected. We prove that there exists a polynomial time $7$-approximation algorithm for this problem.

Authors: Raed Jaberi

Let $G=(V,E)$ be a strong biconnected graph and let $B \subseteq V$ such that for each vertex $w \in B$, the subgraph $G \setminus \lbrace w\rbrace$ is strongly connected. In this paper we study the problem of computing a subset $E_β \subseteq E$ of minimum size such that the subgraph $G_β=(V,E_β)$ is strongly biconnected and for each vertex $w \in B$, the subgraph $G_β \setminus \lbrace w\rbrace$ is strongly connected. We prove that there exists a polynomial time $7$-approximation algorithm for this problem.

Tuesday, June 16 2026, 00:00

Contested Cluster Selectors: Local Ambiguity, Normal Forms, and Backtracking Cost in Random Constraint Satisfaction

from arXiv: Data Structures and Algorithms

Authors: Karthik Sheshadri

We introduce and empirically investigate \emph{contested cluster selectors} (\CCS): variables that are non-backbone, carry information about solution-cluster identity, and are repeatedly but unreliably forced by local propagation during backtracking search. In instrumented \DPLL{} experiments on random 3-\SAT{} near the empirical satisfiability threshold and on near-optimal random \VC{} instances, a small number of such variables accounts for a large fraction of observed backtracking cost. Pinning two or three high-contestedness variables to solution-consistent values reduces backtracking by 70--80\% on the reference instances studied, and a static degree--polarity metric yields a simple $2^k$ enumeration heuristic with a reported $3.7\times$ speedup over baseline \DPLL{} at $n=50$. A polynomial control experiment on random 3-\XORSAT{} sharpens the interpretation. Gaussian elimination exposes the true affine selector coordinates, whereas \DPLL{} churn concentrates on pivot variables chosen in a poor coordinate system. Thus clustering and non-backbone status are not enough: the empirical hardness signal is \emph{local contestation} that remains after available polynomial-time normal forms. We formalize this distinction through safe coordinate exposers and the \emph{unavoidable contested selector cost} (\UCSC). We also prove an ordered single-pass eraser-memory lower bound: any ordered \FERAM{} that recovers a $k$-bit cluster label from a distribution with residual min-entropy $k-η$ using $S$ bits succeeds with probability at most $2^{S+η-k}$. The paper positions \CCS/\UCSC{} as a structural program connecting backdoors, solution-space geometry, low-degree barriers, and Schaefer-style algebraic normal forms. We do not claim a proof of $P\ne NP$; rather, we isolate the normal-form barrier that any such extension would need to overcome.

Authors: Karthik Sheshadri

We introduce and empirically investigate \emph{contested cluster selectors} (\CCS): variables that are non-backbone, carry information about solution-cluster identity, and are repeatedly but unreliably forced by local propagation during backtracking search. In instrumented \DPLL{} experiments on random 3-\SAT{} near the empirical satisfiability threshold and on near-optimal random \VC{} instances, a small number of such variables accounts for a large fraction of observed backtracking cost. Pinning two or three high-contestedness variables to solution-consistent values reduces backtracking by 70--80\% on the reference instances studied, and a static degree--polarity metric yields a simple $2^k$ enumeration heuristic with a reported $3.7\times$ speedup over baseline \DPLL{} at $n=50$. A polynomial control experiment on random 3-\XORSAT{} sharpens the interpretation. Gaussian elimination exposes the true affine selector coordinates, whereas \DPLL{} churn concentrates on pivot variables chosen in a poor coordinate system. Thus clustering and non-backbone status are not enough: the empirical hardness signal is \emph{local contestation} that remains after available polynomial-time normal forms. We formalize this distinction through safe coordinate exposers and the \emph{unavoidable contested selector cost} (\UCSC). We also prove an ordered single-pass eraser-memory lower bound: any ordered \FERAM{} that recovers a $k$-bit cluster label from a distribution with residual min-entropy $k-η$ using $S$ bits succeeds with probability at most $2^{S+η-k}$. The paper positions \CCS/\UCSC{} as a structural program connecting backdoors, solution-space geometry, low-degree barriers, and Schaefer-style algebraic normal forms. We do not claim a proof of $P\ne NP$; rather, we isolate the normal-form barrier that any such extension would need to overcome.

Tuesday, June 16 2026, 00:00

Active Learning with Low-Rank Structure for Data Selection

from arXiv: Data Structures and Algorithms

Authors: Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni, Mahdi Nikdan, David P. Woodruff, Samson Zhou

In the data selection problem, the objective is to choose a small, representative subset of data that can be used to efficiently train a machine learning model. Sener and Savarese [ICLR 2018] showed that, given an embedding representation of the data and suitable geometric assumptions, heuristics based on $k$-center clustering can be used to perform data selection. This perspective was further explored by Axiotis et. al. [ICML 2024], who proposed a data selection approach based on $k$-means clustering and sensitivity sampling. However, these methods rely on the assumption that the dataset exhibits intrinsic geometric structure that can be effectively captured by clustering, whereas many modern datasets instead possess global algebraic structure that is better exploited by low-rank approximation or principal component analysis. In this paper, we introduce a new data selection framework based on low-rank approximation and residual-based sampling, formulated through the lens of row subset selection and loss-preserving coreset construction. Given an embedding representation of the data satisfying mild regularity conditions, which can be interpreted as algebraic or angular notions of Lipschitz continuity, we show that it is possible to select a weighted subset of $\tilde{O}\left(k + \frac{1}{\varepsilon^2}\right)$ data points whose average loss approximates the average loss over the full dataset within a $(1+\varepsilon)$ relative error, up to an additive $\varepsilon Φ_k$ term, where $Φ_k$ denotes the optimal rank-$k$ approximation cost of the embedding matrix. We complement these theoretical guarantees with empirical evaluations, demonstrating that on a range of real-world datasets, our data selection approach achieves improved performance over prior strategies based on uniform sampling or clustering-based sensitivity sampling.

Authors: Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni, Mahdi Nikdan, David P. Woodruff, Samson Zhou

In the data selection problem, the objective is to choose a small, representative subset of data that can be used to efficiently train a machine learning model. Sener and Savarese [ICLR 2018] showed that, given an embedding representation of the data and suitable geometric assumptions, heuristics based on $k$-center clustering can be used to perform data selection. This perspective was further explored by Axiotis et. al. [ICML 2024], who proposed a data selection approach based on $k$-means clustering and sensitivity sampling. However, these methods rely on the assumption that the dataset exhibits intrinsic geometric structure that can be effectively captured by clustering, whereas many modern datasets instead possess global algebraic structure that is better exploited by low-rank approximation or principal component analysis. In this paper, we introduce a new data selection framework based on low-rank approximation and residual-based sampling, formulated through the lens of row subset selection and loss-preserving coreset construction. Given an embedding representation of the data satisfying mild regularity conditions, which can be interpreted as algebraic or angular notions of Lipschitz continuity, we show that it is possible to select a weighted subset of $\tilde{O}\left(k + \frac{1}{\varepsilon^2}\right)$ data points whose average loss approximates the average loss over the full dataset within a $(1+\varepsilon)$ relative error, up to an additive $\varepsilon Φ_k$ term, where $Φ_k$ denotes the optimal rank-$k$ approximation cost of the embedding matrix. We complement these theoretical guarantees with empirical evaluations, demonstrating that on a range of real-world datasets, our data selection approach achieves improved performance over prior strategies based on uniform sampling or clustering-based sensitivity sampling.

Tuesday, June 16 2026, 00:00

Raiders of the Lost Log: Synchronous Parallel In-Place Models and Algorithms

from arXiv: Data Structures and Algorithms

Authors: Michael T. Goodrich, Vinesh Sridhar

Embedded systems and Internet of Things (IoT) applications motivate in-place parallel algorithms, which avoid allocating additional shared memory past the input. Work by Gu, Obeya, and Shun [APOCS '21] defines a family of PIP (parallel in-place) models and parallel algorithms that eschew auxiliary memory at high processor counts while remaining in-situ when run sequentially. However, their models assume asynchronous processing and have no in-place guarantees for intermediate processor counts. We address this gap in the literature by proposing a Synchronous PIP family of models for in-place parallel and distributed computation. We demonstrate the effectiveness of our new model by giving efficient and synchronous parallel algorithms in this model that require no auxiliary shared memory and only constant private memory per processor. Importantly, we show how to leverage a new parallel-augmented sweep technique to ensure that Synchronous PIP algorithms remain efficient and strictly in-place at all processor counts.

Authors: Michael T. Goodrich, Vinesh Sridhar

Embedded systems and Internet of Things (IoT) applications motivate in-place parallel algorithms, which avoid allocating additional shared memory past the input. Work by Gu, Obeya, and Shun [APOCS '21] defines a family of PIP (parallel in-place) models and parallel algorithms that eschew auxiliary memory at high processor counts while remaining in-situ when run sequentially. However, their models assume asynchronous processing and have no in-place guarantees for intermediate processor counts. We address this gap in the literature by proposing a Synchronous PIP family of models for in-place parallel and distributed computation. We demonstrate the effectiveness of our new model by giving efficient and synchronous parallel algorithms in this model that require no auxiliary shared memory and only constant private memory per processor. Importantly, we show how to leverage a new parallel-augmented sweep technique to ensure that Synchronous PIP algorithms remain efficient and strictly in-place at all processor counts.

Tuesday, June 16 2026, 00:00

Resizable Retrieval

from arXiv: Data Structures and Algorithms

Authors: William Kuszmaul, Aaron Putterman, Tingqiang Xu, Hangrui Zhou, Renfei Zhou

A dynamic retrieval data structure encodes a function $f:K \rightarrow [2^v]$ for a set $K \subseteq [U]$, while supporting queries $f(x)$ for $x\in K$, insertions \texttt{Insert}$(x, f(x))$ for $x \notin K$, and deletions \texttt{Delete}$(x)$ for $x \in K$. Given an upper bound $N$ on $|K|$, it is known how to solve the dynamic retrieval problem with $O(1)$-time operations and space $Nv + O(N \log \log (U/N))$ bits. An open question, first posed by Demaine et al. in 2006, is whether a similar bound can be achieved with a resizable data structure, whose space bound is parameterized by the \emph{current} size $n$ of $K$. We answer this question in the affirmative and prove matching lower bounds for the space-time trade-off achieved by our data structure. We also give corollaries for space-efficient memory allocation and dynamic filters.

Authors: William Kuszmaul, Aaron Putterman, Tingqiang Xu, Hangrui Zhou, Renfei Zhou

A dynamic retrieval data structure encodes a function $f:K \rightarrow [2^v]$ for a set $K \subseteq [U]$, while supporting queries $f(x)$ for $x\in K$, insertions \texttt{Insert}$(x, f(x))$ for $x \notin K$, and deletions \texttt{Delete}$(x)$ for $x \in K$. Given an upper bound $N$ on $|K|$, it is known how to solve the dynamic retrieval problem with $O(1)$-time operations and space $Nv + O(N \log \log (U/N))$ bits. An open question, first posed by Demaine et al. in 2006, is whether a similar bound can be achieved with a resizable data structure, whose space bound is parameterized by the \emph{current} size $n$ of $K$. We answer this question in the affirmative and prove matching lower bounds for the space-time trade-off achieved by our data structure. We also give corollaries for space-efficient memory allocation and dynamic filters.

Tuesday, June 16 2026, 00:00

Modern Primal-Dual Frameworks for Prior-Free Online Resource Allocation

from arXiv: Data Structures and Algorithms

Authors: Rad Niazadeh, Rajan Udwani

Linear-programming (LP)-based primal-dual methods are fundamental for designing and analyzing algorithms in adversarial (prior-free) online resource allocation. This chapter provides a tutorial on two modern primal-dual frameworks, emphasizing recent developments and contemporary models in operations research. Part~I develops an LP-based convex-programming framework where solving a regularized convex program at each arrival captures the tradeoff between greediness and hedging, yielding a dual certificate via Karush-Kuhn-Tucker (KKT) conditions. Because standard LP relaxations can be weak or intractable for stochastic outcomes, Part~II introduces a complementary LP-free framework that provides a universal certificate system for evaluating competitive ratios under such uncertainty. Covering a wide array of models -- including online vertex-weighted bipartite matching, edge-weighted online matching with free disposal, online matching with stochastic rewards, reusable resources, two-sided assortment optimization, configuration allocation (whole-page optimization), AdWords, and costly cancellations -- the tutorial equips readers with versatile proof templates to analyze existing algorithms and develop new solutions for emerging applications.

Authors: Rad Niazadeh, Rajan Udwani

Linear-programming (LP)-based primal-dual methods are fundamental for designing and analyzing algorithms in adversarial (prior-free) online resource allocation. This chapter provides a tutorial on two modern primal-dual frameworks, emphasizing recent developments and contemporary models in operations research. Part~I develops an LP-based convex-programming framework where solving a regularized convex program at each arrival captures the tradeoff between greediness and hedging, yielding a dual certificate via Karush-Kuhn-Tucker (KKT) conditions. Because standard LP relaxations can be weak or intractable for stochastic outcomes, Part~II introduces a complementary LP-free framework that provides a universal certificate system for evaluating competitive ratios under such uncertainty. Covering a wide array of models -- including online vertex-weighted bipartite matching, edge-weighted online matching with free disposal, online matching with stochastic rewards, reusable resources, two-sided assortment optimization, configuration allocation (whole-page optimization), AdWords, and costly cancellations -- the tutorial equips readers with versatile proof templates to analyze existing algorithms and develop new solutions for emerging applications.

Tuesday, June 16 2026, 00:00

Distributed Dominating Set With Optimal Rounds and Message Size in Bounded Arboricity Graphs

from arXiv: Data Structures and Algorithms

Authors: Sharareh Alipour, Ermiya Farokhnejad

We study the distributed minimum dominating set problem on graphs of arboricity $α$. Dory, Ghaffari, and Ilchi [PODC'22] showed that any algorithm achieving a constant or poly-logarithmic approximation factor needs at least $Ω(\logΔ/\log\logΔ)$ rounds in graphs of maximum degree $Δ$ and arboricity $α$, even when $α=2$ and even when the message sizes are unbounded. Although there is a variety of algorithms with a near-optimal round complexity of $O(\logΔ)$, it is natural to ask: What is the best approximation factor in the optimal round complexity of $O(\logΔ/\log\logΔ)$? We make progress in answering this question by describing a deterministic algorithm that obtains a $O\left( α\log Δ/ \log\log Δ\right)$ approximation without prior knowledge of $α$ with optimal round complexity of $O\left( \log Δ/ \log\log Δ\right)$ and optimal message size of $1$ bit per round. Among all of the previous results, the only algorithm that achieves the optimal round complexity of $O\left( \log Δ/ \log\log Δ\right)$ without prior knowledge of $α$ is due to Lenzen and Wattenhofer [DISC'10] that obtains a $O(α\log^{1+\varepsilon}Δ/ (\varepsilon\log\log Δ))$ approximation in $O(\logΔ/(\varepsilon\log\logΔ))$ rounds and $O(\log(\varepsilon^{-1}\logΔ))$ message size. Our algorithm simplifies and improves upon this result. The only downside of our algorithm compared to the algorithm of Lenzen and Wattenhofer is that it needs prior knowledge of $Δ$. The previous state-of-the-art algorithm by Dory, Ghaffari, and Ilchi [PODC'22] has a dependency on $\log n$ in the round complexity for unknown $α$, which is far from optimal.

Authors: Sharareh Alipour, Ermiya Farokhnejad

We study the distributed minimum dominating set problem on graphs of arboricity $α$. Dory, Ghaffari, and Ilchi [PODC'22] showed that any algorithm achieving a constant or poly-logarithmic approximation factor needs at least $Ω(\logΔ/\log\logΔ)$ rounds in graphs of maximum degree $Δ$ and arboricity $α$, even when $α=2$ and even when the message sizes are unbounded. Although there is a variety of algorithms with a near-optimal round complexity of $O(\logΔ)$, it is natural to ask: What is the best approximation factor in the optimal round complexity of $O(\logΔ/\log\logΔ)$? We make progress in answering this question by describing a deterministic algorithm that obtains a $O\left( α\log Δ/ \log\log Δ\right)$ approximation without prior knowledge of $α$ with optimal round complexity of $O\left( \log Δ/ \log\log Δ\right)$ and optimal message size of $1$ bit per round. Among all of the previous results, the only algorithm that achieves the optimal round complexity of $O\left( \log Δ/ \log\log Δ\right)$ without prior knowledge of $α$ is due to Lenzen and Wattenhofer [DISC'10] that obtains a $O(α\log^{1+\varepsilon}Δ/ (\varepsilon\log\log Δ))$ approximation in $O(\logΔ/(\varepsilon\log\logΔ))$ rounds and $O(\log(\varepsilon^{-1}\logΔ))$ message size. Our algorithm simplifies and improves upon this result. The only downside of our algorithm compared to the algorithm of Lenzen and Wattenhofer is that it needs prior knowledge of $Δ$. The previous state-of-the-art algorithm by Dory, Ghaffari, and Ilchi [PODC'22] has a dependency on $\log n$ in the round complexity for unknown $α$, which is far from optimal.

Tuesday, June 16 2026, 00:00

Linear algebra at exponential scale via tensor network dimension reduction

from arXiv: Data Structures and Algorithms

Authors: Chris Camaño, Ethan N. Epperly, Raphael A. Meyer, Joel A. Tropp

Many problems in modern scientific computing are challenging because of a \emph{curse of dimension}, where their mathematical formulation involves objects whose dimension is \emph{exponential} in the nominal "size" of the problem. Tensor networks can provide a compact representation for exponentially large vectors and matrices that arise in applications, but these representations do not always lead to reliable algorithms. This paper develops and analyzes techniques for randomized dimension reduction of tensor network data. These techniques support a suite of efficient algorithms for provably solving exponential-scale linear algebra problems, including trace estimation and eigenvalue approximation. The paper includes several stylized illustrations from quantum many-body physics with ambient dimension up to $2^{200}$.

Authors: Chris Camaño, Ethan N. Epperly, Raphael A. Meyer, Joel A. Tropp

Many problems in modern scientific computing are challenging because of a \emph{curse of dimension}, where their mathematical formulation involves objects whose dimension is \emph{exponential} in the nominal "size" of the problem. Tensor networks can provide a compact representation for exponentially large vectors and matrices that arise in applications, but these representations do not always lead to reliable algorithms. This paper develops and analyzes techniques for randomized dimension reduction of tensor network data. These techniques support a suite of efficient algorithms for provably solving exponential-scale linear algebra problems, including trace estimation and eigenvalue approximation. The paper includes several stylized illustrations from quantum many-body physics with ambient dimension up to $2^{200}$.

Tuesday, June 16 2026, 00:00

Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model

from arXiv: Data Structures and Algorithms

Authors: Siyu Chen, Beining Wu, Miao Lu, Zhuoran Yang, Tianhao Wang

In this work, we tackle the following question: Can neural networks trained with gradient-based methods achieve the optimal computational-statistical tradeoff in learning Gaussian single-index models? Prior research has shown that any polynomial-time algorithm under the statistical query (SQ) framework requires $Ω(d^{s^\star/2}\lor d)$ samples, where $s^\star$ is the generative exponent representing the intrinsic difficulty of learning the underlying model. However, it remains unknown whether neural networks can achieve this sample complexity. Inspired by prior techniques such as label transformation and landscape smoothing for learning single-index models, we propose a unified gradient-based algorithm for training a two-layer neural network in polynomial time. Our method is adaptable to a variety of loss and activation functions, covering a broad class of existing approaches. We show that our algorithm learns a feature representation that strongly aligns with the unknown signal $θ^\star$, with sample complexity $\widetilde{O} (d^{s^\star/2} \lor d)$, matching the SQ lower bound up to a polylogarithmic factor for all generative exponents $s^\star\geq 1$. Furthermore, we extend our approach to the setting where $θ^\star$ is $k$-sparse for $k = o(\sqrt{d})$ by introducing a novel weight perturbation technique that leverages the sparsity structure. We derive a corresponding SQ lower bound of order $\widetildeΩ(k^{s^\star})$, matched by our method up to a polylogarithmic factor. Our framework, especially the weight perturbation technique, is of independent interest, and suggests potential gradient-based solutions to other problems such as sparse tensor PCA.

Authors: Siyu Chen, Beining Wu, Miao Lu, Zhuoran Yang, Tianhao Wang

In this work, we tackle the following question: Can neural networks trained with gradient-based methods achieve the optimal computational-statistical tradeoff in learning Gaussian single-index models? Prior research has shown that any polynomial-time algorithm under the statistical query (SQ) framework requires $Ω(d^{s^\star/2}\lor d)$ samples, where $s^\star$ is the generative exponent representing the intrinsic difficulty of learning the underlying model. However, it remains unknown whether neural networks can achieve this sample complexity. Inspired by prior techniques such as label transformation and landscape smoothing for learning single-index models, we propose a unified gradient-based algorithm for training a two-layer neural network in polynomial time. Our method is adaptable to a variety of loss and activation functions, covering a broad class of existing approaches. We show that our algorithm learns a feature representation that strongly aligns with the unknown signal $θ^\star$, with sample complexity $\widetilde{O} (d^{s^\star/2} \lor d)$, matching the SQ lower bound up to a polylogarithmic factor for all generative exponents $s^\star\geq 1$. Furthermore, we extend our approach to the setting where $θ^\star$ is $k$-sparse for $k = o(\sqrt{d})$ by introducing a novel weight perturbation technique that leverages the sparsity structure. We derive a corresponding SQ lower bound of order $\widetildeΩ(k^{s^\star})$, matched by our method up to a polylogarithmic factor. Our framework, especially the weight perturbation technique, is of independent interest, and suggests potential gradient-based solutions to other problems such as sparse tensor PCA.

Tuesday, June 16 2026, 00:00

Comparison Patrols on Drifting Orders: Certified Rank Maintenance, Evolving Planar Maxima, and Selection under Drifting Fitness

from arXiv: Data Structures and Algorithms

Authors: Faruk Alpay, Levent Sarioglu

Rank-based selection in dynamic environments acts on order information that becomes stale while it is being used. Tournaments, elitism, truncation, and Pareto selection may therefore consume rankings that no longer match the current fitness order, while full re-evaluation competes with search for the same budget. This paper formulates the missing information layer as a data-structure problem. A hidden total order on $n$ items drifts by adjacent transpositions, while a maintainer receives one truthful pairwise comparison per step and must answer rank queries continuously. We introduce the comparison patrol, a constant-time maintained-order structure using $3n+O(1)$ words, one comparison per update, deterministic verification-age bounds, and per-item displacement certificates. We prove lower bounds showing that oblivious and location-oblivious maintainers incur expected Kendall error $Ω(\min(α,1)n)$, and show that the patrol operates at the same order. A bump invariant yields exact self-stabilization after drift-free corruption: if the maximum rank overstatement is $L$, recovery takes at most $L$ aligned cycles and cannot finish before $L-1$. This gives a deterministic shock-recovery calculus and a crossover with full rebuild near $L\approx \log_2 n$. The maintained order is then transferred to evolving planar maxima and to evolutionary selection rules, giving deterministic bounds for truncation, tournament, elitist, and two-objective Pareto decisions under drifting fitness. Experiments up to $n=65{,}536$ audit the certificates, recovery laws, equilibrium behavior, and equal-budget dynamic evolutionary loops, identifying when certified local rank maintenance outperforms global re-evaluation and when it should hand over.

Authors: Faruk Alpay, Levent Sarioglu

Rank-based selection in dynamic environments acts on order information that becomes stale while it is being used. Tournaments, elitism, truncation, and Pareto selection may therefore consume rankings that no longer match the current fitness order, while full re-evaluation competes with search for the same budget. This paper formulates the missing information layer as a data-structure problem. A hidden total order on $n$ items drifts by adjacent transpositions, while a maintainer receives one truthful pairwise comparison per step and must answer rank queries continuously. We introduce the comparison patrol, a constant-time maintained-order structure using $3n+O(1)$ words, one comparison per update, deterministic verification-age bounds, and per-item displacement certificates. We prove lower bounds showing that oblivious and location-oblivious maintainers incur expected Kendall error $Ω(\min(α,1)n)$, and show that the patrol operates at the same order. A bump invariant yields exact self-stabilization after drift-free corruption: if the maximum rank overstatement is $L$, recovery takes at most $L$ aligned cycles and cannot finish before $L-1$. This gives a deterministic shock-recovery calculus and a crossover with full rebuild near $L\approx \log_2 n$. The maintained order is then transferred to evolving planar maxima and to evolutionary selection rules, giving deterministic bounds for truncation, tournament, elitist, and two-objective Pareto decisions under drifting fitness. Experiments up to $n=65{,}536$ audit the certificates, recovery laws, equilibrium behavior, and equal-budget dynamic evolutionary loops, identifying when certified local rank maintenance outperforms global re-evaluation and when it should hand over.

Tuesday, June 16 2026, 00:00

Optimality of Random Regular Graphs in Sparse Network Designs

from arXiv: Data Structures and Algorithms

Authors: Weijia Li, Xiaochun Niu, Yehua Wei, Jiaming Xu

The problems of designing sparse networks arise frequently in resource allocation and operations research. In production systems, for example, sparse process flexibility designs are used to handle uncertain demand effectively: the goal is to construct the sparsest bipartite graph between supply and demand that still achieves an expected fulfilled demand comparable to that of a fully flexible system. In middle-mile transportation, sparse delivery-route subgraphs that sustain large matchings after random node deletions help reduce delivery costs; here, the goal is to design the sparsest graph whose maximum matching size remains comparable to that of the fully connected graph under node deletions. The design of sparse networks has been studied extensively, with state-of-the-art results providing order-wise optimal designs for both bipartite and unipartite networks (Chen et al., 2015; Feng et al., 2024). However, identifying designs that achieve the sharp theoretical limit -- where the average degree asymptotically matches the lower bound of any graph to achieve a given loss level, has remained open. In this paper, we prove that the random regular graph achieves this sharp optimal condition in both bipartite and unipartite settings. Numerical experiments further validate this optimality. Our results highlight a practical guideline for sparse flexibility networks: designs that combine degree regularity with low edge correlations can achieve optimal performance under uncertainty.

Authors: Weijia Li, Xiaochun Niu, Yehua Wei, Jiaming Xu

The problems of designing sparse networks arise frequently in resource allocation and operations research. In production systems, for example, sparse process flexibility designs are used to handle uncertain demand effectively: the goal is to construct the sparsest bipartite graph between supply and demand that still achieves an expected fulfilled demand comparable to that of a fully flexible system. In middle-mile transportation, sparse delivery-route subgraphs that sustain large matchings after random node deletions help reduce delivery costs; here, the goal is to design the sparsest graph whose maximum matching size remains comparable to that of the fully connected graph under node deletions. The design of sparse networks has been studied extensively, with state-of-the-art results providing order-wise optimal designs for both bipartite and unipartite networks (Chen et al., 2015; Feng et al., 2024). However, identifying designs that achieve the sharp theoretical limit -- where the average degree asymptotically matches the lower bound of any graph to achieve a given loss level, has remained open. In this paper, we prove that the random regular graph achieves this sharp optimal condition in both bipartite and unipartite settings. Numerical experiments further validate this optimality. Our results highlight a practical guideline for sparse flexibility networks: designs that combine degree regularity with low edge correlations can achieve optimal performance under uncertainty.

Tuesday, June 16 2026, 00:00

Differentially Private Submodular Maximization with a Knapsack Constraint

from arXiv: Data Structures and Algorithms

Authors: Ron Zadicario, Tova Milo

Submodular maximization subject to a knapsack constraint (SMK) is a fundamental problem in discrete optimization, with wide-ranging applications in machine learning and related fields. As these applications increasingly involve sensitive individual data, there is a growing need for high-utility algorithms that provide formal privacy guarantees. In this work, we study the SMK problem under differential privacy, considering both monotone and non-monotone objective functions. For monotone objectives, we propose a differentially private algorithm that achieves the optimal $(1-1/e)$-approximation ratio while significantly improving both additive error and query complexity over prior work. We also present a more efficient algorithm for the same setting, achieving a $1/2$-approximation. For non-monotone objectives, we introduce, to our knowledge, the first differentially private algorithm with provable guarantees, achieving a $1/4$-approximation in expectation and an additive error comparable to the best known for monotone objective functions.

Authors: Ron Zadicario, Tova Milo

Submodular maximization subject to a knapsack constraint (SMK) is a fundamental problem in discrete optimization, with wide-ranging applications in machine learning and related fields. As these applications increasingly involve sensitive individual data, there is a growing need for high-utility algorithms that provide formal privacy guarantees. In this work, we study the SMK problem under differential privacy, considering both monotone and non-monotone objective functions. For monotone objectives, we propose a differentially private algorithm that achieves the optimal $(1-1/e)$-approximation ratio while significantly improving both additive error and query complexity over prior work. We also present a more efficient algorithm for the same setting, achieving a $1/2$-approximation. For non-monotone objectives, we introduce, to our knowledge, the first differentially private algorithm with provable guarantees, achieving a $1/4$-approximation in expectation and an additive error comparable to the best known for monotone objective functions.

Tuesday, June 16 2026, 00:00

Linkage

from David Eppstein

Biomedical papers with fabricated references blew up by more than a factor of ten from 2023 to 2026 ($\mathbb{M}$, via). Relatedly, arXiv has added a new policy banning author of papers with hallucinated citations or other artifacts of unchecked LLM use for a year (and after that permanently requiring publication prior to allowing a preprint, kind of problematic for publication in journals whose submission process depends on having an arXiv preprint. Unfortunately I can’t find a direct reference to this in the actual posted arXiv policies and I’m not going to link to X/twitter where Tom Dietterich posted the only semi-official communication I can find on it.

Biomedical papers with fabricated references blew up by more than a factor of ten from 2023 to 2026 ($\mathbb{M}$, via). Relatedly, arXiv has added a new policy banning author of papers with hallucinated citations or other artifacts of unchecked LLM use for a year (and after that permanently requiring publication prior to allowing a preprint, kind of problematic for publication in journals whose submission process depends on having an arXiv preprint. Unfortunately I can’t find a direct reference to this in the actual posted arXiv policies and I’m not going to link to X/twitter where Tom Dietterich posted the only semi-official communication I can find on it.
Fish curve drawn as an epicycle. See also “Wheels on wheels on wheels” by Frank Farris in Math. Mag. on symmetric doily patterns drawn using epicycles.
I recently learned that the cubic and quartic cases of Fermat’s last theorem (the impossibility of integer solution of $x^3+y^3=z^3$ and $x^4+y^4=z^4$) go back farther than Fermat ($\mathbb{M}$), to medieval Islamic mathematics. Abu-Mahmud Khujandi tried to prove the impossibility of the cubic case (but the proof was faulty) and later Ibn al-Khawwām included both cases in a list of open problems.
The age of an open problem is not a good proxy for its difficulty or importance, notes Lance Fortnow.
Another day, another journal editorial board mass resignation ($\mathbb{M}$, via) this time from Springer’s Natural Language Semantics, over publisher demands to increase article publication charge revenue by increasing their number of acceptances. Instead the same editors are launching a new diamond open-access journal, Semantics of Natural Languages, through the Open Library of Humanities.
The American Diabetes Association has ejected from its annual meeting the editor-in-chief of its journal Diabetes Care, its former president, and three other scientists ($\mathbb{M}$), for handing out reprints of an editorial published in the journal and critical of the US government’s attacks on science. According to video evidence the ejected scientists “were not disruptive or disorderly in their conduct”. Nevertheless, the ADA claims that this behavior constituted a violation of the association’s code of conduct.
On circle packing with more than one size of circle.
Jeremy Kun (1) enjoys a rambly substack post on software developer bros who don’t even know how to find the center of a triangle, and how this somehow portends the obsolescence of software development (2) excuses the bros from their ignorance on the basis that there are “at least 26 different definitions of a triangle’s center”, (3) discovers that the Encyclopedia of Triangle Centers has “actually over 71 thousand definitions”, (4) realizes that his own ignorance has made him become the software bro he was enjoying the substack diss of, and (5) describes the whole saga, as if waking from a dream.
Terry Tao clearly explains why proposed new US funding rules requiring conference travel to be planned years ahead of time as part of grant proposals do not work for the time scales of mathematics research ($\mathbb{M}$). These rules would be even more disastrous for computer science, where conference publication is essential for making one’s research known and where one cannot know which conferences the research will appear in until the conference acceptance and rejections come in, only a few weeks or months before the conference itself.
How to wrap a hat tiling around a cylinder such as, say, a coffee mug, if you had a manufacturing process for them that didn’t involve leaving a seam in the design.
New preprint: “Existence of a periodic orbit for billiards in polygons ($\mathbb{M}$), Giovanni Forni. I think the title is self-explanatory; this claims to solve a major open problem in geometric dynamical systems. (I have too little expertise in this topic to evaluate its correctness.)
My 2024 paper “Non-crossing Hamiltonian paths and cycles in output-polynomial time](https://ics.uci.edu/~eppstein/pubs/p-noncross.html)” has been given the inaugural 2025 Algorithmica Best Paper Award ($\mathbb{M}$) as the most impactful paper in the journal Algorithmica from the past three years. The paper shows that one can list all of the traveling salesperson tours through a set of points in the plane in an amount of time polynomial in the number of tours. This number can be exponential, but the harder part of the problem is finding the tours quickly when there are fewer than exponentially many of them.
Dissident Russian mathematician Mikhail Verbitsky, traveling from Brazil to an award ceremony in Armenia, was arrested there at the request of the Russian government ($\mathbb{M}$). The linked article, in French, is from the French Mathematical Society, which strongly protests this action. As of posting he is said to be freed on a technicality but forbidden from leaving Armenia.
Seventeen camels and where they can take you ($\mathbb{M}$). Jim Propp on how “six seemingly unrelated brain-teasers” including the 17-camel inheritance problem as well as exercises on counting edges in forests can be solved by the same trick for dealing with linear equations with constant offsets.

By David Eppstein

Monday, June 15 2026, 16:56

TR26-101 | On Proof Systems for #QBF | Sravanthi Chede, Leroy Chew, Vaibhav Krishan, Anil Shukla

from ECCC Papers

For a quantified Boolean formula (QBF), the problem of computing the number of winning strategies is known as the #QBF problem. This problem is considered harder than the analogous #SAT problem. Recently, important proof systems for QBFs and #SAT have been studied. By extending the ideas from both fields, we show that it is possible to design proof systems for #QBF. Such proof systems are important not only for advancing the theory of #QBF but also for certifying and designing better #QBF solvers, an area that is still in its early stages. In this paper, we explore #QBF proof systems to count the number of Skolem functions. In addition to a naive system, we study #QBF systems based on the $\forall$-expansion rule of QBFs. We observe that these systems have inherent structural weaknesses that lead to lower bounds. As an alternative, we propose a #QBF proof system that we call Q-MICE, which consists of sound inference rules for computing and certifying the #QBF solution, similar to the line-based #SAT proof system MICE. To demonstrate the strength of Q-MICE, we present various upper bounds, such as the quantified version of the propositional XOR-PAIRS formula, which is known to be hard for MICE. Consequently, we also separate Q-MICE from $\forall$-expansion based #QBF proof systems.

Monday, June 15 2026, 08:11

mnemonic devices and pangrams that could be real sentences

from Computational Complexity

A mnemonic device is a sentence where the first letters of the words are helpful to remember something. My favorite one is

My Very Educated Mother Just Said Uh, No Pluto

You probably know what it's for. If not you can type it into Google and you will find:

Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, Neptune

and of course NOT Pluto anymore.

Consider

Kids Prefer Cheese Over Fried Green Tomatoes

Again, if you just google that sentence you will find that it is a mnemonic for biological taxonomy:

Kingdom, Phylum, Class, Order, Family, Genus, Species

I came across the mnemonic device

Do Men Ever Visit Brighton Beach?

The place I read this did not say what it was a mnemonic device for. So I typed it into Google and found out:

Yes, they do! If you are refereeing to the Metropolitan museum of Art (The Met) staff, researchers or groups from New York, they frequently travel to the seaside city of Brighton, England, or its coastal namesake Brighton Beach, NY, for educational trips, research, and cultural exchange.

(This is word for word--- so any misspelled words odd phrasing is from Google, not from Bill.)

What happened? Most mnemonic devices are not sentences you would say in normal conversation. This one is! So what to do? I Googled

What is ``Do Men Ever Visit Brighton Beach' a mnemonic device for?

It is British nobility:

Duke, Marquess, Earl, Viscount, Baron, Baronet.

1) Are there other mnemonics that are sentences one might actually say? I asked Google and the Google AI overviews gave me the following:

Sam's Horse Must Eat Oats. This is a mnemonic for the great lakes.

A big secret conceal her past. This is a mnemonic for the last names of King Henry the 8th's wives. Not quite last names- Catherine of Aragon is regarded as having Aragon for a last name. Bonus: By looking all this up I found out that 3 of the 6 wives has first names that sounded the same: Catherine of Aragon, Catherine Howard, and Katherine Parr. So, he had a type. He had 2 of his 6 wives killed, so 1/3 and he had 1 of the 3 C/K atherine's killed, also 1/3.

Big gorillas eat hotdogs, not cold pizza. Really? I thought they liked cold pizza. I am more surprised that Google thinks someone might say this sentence in normal conversation, and not just when they are trying to remember the countries of Central America: Belize, Guatemala, El Salvador, Honduras, Nicaragua, Costa Rica, Panama.

2) I would normally see if Chatty or Claude does better, but at this point I'm beating a dead horse (maybe Sam's).

3) My favorite pangram (sentences with every letter) that one might actually say is (or was- you'll see why)

Watch Jeopardy!---Alex Trebek's fun TV quiz game

Maybe put `show' at the end to make it more something someone might say- or would have said before Alex Trebek passed away.

Google AI overview game me those below. Are they sentences people would say? I leave that as an exercise for the reader

Jim quickly realized that those beautiful gowns are expensive

The quick onyx goblin jumps over the lazy dwarf.

(I uttered that sentence just the other day!)

Just keep examining every low bid quoted for zinc etchings.

(This was a reasonable sentence until the word etchings.)

Bored? Craving a pub quiz fix? Why, just come to the Royal Oak!

(I prefer the Alex Trebek pangram more.)

4) Google AI overview seems to not quite know what a sentence one might actually say is.

By gasarch

A mnemonic device is a sentence where the first letters of the words are helpful to remember something. My favorite one is

My Very Educated Mother Just Said Uh, No Pluto

You probably know what it's for. If not you can type it into Google and you will find:

Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, Neptune

and of course NOT Pluto anymore.

Consider

Kids Prefer Cheese Over Fried Green Tomatoes

Again, if you just google that sentence you will find that it is a mnemonic for biological taxonomy:

Kingdom, Phylum, Class, Order, Family, Genus, Species

I came across the mnemonic device

Do Men Ever Visit Brighton Beach?

The place I read this did not say what it was a mnemonic device for. So I typed it into Google and found out:

Yes, they do! If you are refereeing to the Metropolitan museum of Art (The Met) staff, researchers or groups from New York, they frequently travel to the seaside city of Brighton, England, or its coastal namesake Brighton Beach, NY, for educational trips, research, and cultural exchange.

(This is word for word--- so any misspelled words odd phrasing is from Google, not from Bill.)

What happened? Most mnemonic devices are not sentences you would say in normal conversation. This one is! So what to do? I Googled

What is ``Do Men Ever Visit Brighton Beach' a mnemonic device for?

It is British nobility:

Duke, Marquess, Earl, Viscount, Baron, Baronet.

1) Are there other mnemonics that are sentences one might actually say? I asked Google and the Google AI overviews gave me the following:

Sam's Horse Must Eat Oats. This is a mnemonic for the great lakes.

A big secret conceal her past. This is a mnemonic for the last names of King Henry the 8th's wives. Not quite last names- Catherine of Aragon is regarded as having Aragon for a last name. Bonus: By looking all this up I found out that 3 of the 6 wives has first names that sounded the same: Catherine of Aragon, Catherine Howard, and Katherine Parr. So, he had a type. He had 2 of his 6 wives killed, so 1/3 and he had 1 of the 3 C/K atherine's killed, also 1/3.

Big gorillas eat hotdogs, not cold pizza. Really? I thought they liked cold pizza. I am more surprised that Google thinks someone might say this sentence in normal conversation, and not just when they are trying to remember the countries of Central America: Belize, Guatemala, El Salvador, Honduras, Nicaragua, Costa Rica, Panama.

2) I would normally see if Chatty or Claude does better, but at this point I'm beating a dead horse (maybe Sam's).

3) My favorite pangram (sentences with every letter) that one might actually say is (or was- you'll see why)

Watch Jeopardy!---Alex Trebek's fun TV quiz game

Maybe put `show' at the end to make it more something someone might say- or would have said before Alex Trebek passed away.

Google AI overview game me those below. Are they sentences people would say? I leave that as an exercise for the reader

Jim quickly realized that those beautiful gowns are expensive

The quick onyx goblin jumps over the lazy dwarf.

(I uttered that sentence just the other day!)

Just keep examining every low bid quoted for zinc etchings.

(This was a reasonable sentence until the word etchings.)

Bored? Craving a pub quiz fix? Why, just come to the Royal Oak!

(I prefer the Alex Trebek pangram more.)

4) Google AI overview seems to not quite know what a sentence one might actually say is.

By gasarch

Monday, June 15 2026, 01:08

Algebraic Circuits Over Sum and Shift and Existential Presburger Arithmetic with Divisibility

from arXiv: Computational Complexity

Authors: Ignacio Barros, Michaël Cadilhac, Guillermo A. Pérez

We study existential Presburger arithmetic extended with divisibility predicates (EPAD). Its satisfiability problem has long been known to be NP-hard, and has often been expected to lie in NP. We prove that it is PP-hard, ruling out this expectation unless NP=PP. This also implies \PP-hardness of satisfiability for positive Boolean combinations of word equations and length constraints. The lower bound is compatible with a strong form of Lipshitz-style simplification. We define a polynomial-time recognizable fragment, called \MergeAbs, in which the usual finite-quotient replacement of divisibility atoms can be repeated until no divisibility atom remains. Nevertheless, EPAD satisfiability is already PP-hard on this fully simplifiable fragment. The reduction starts from a threshold coefficient problem for a class of arithmetic circuits using only addition and shifts. The same systems used in the reduction also expose a limitation of normalization. A polynomial-size scaling family, indexed by $j$, forces an endpoint relation $v=(2^{2^j}+1)u$, and the natural finite-quotient simplification records it as one equation with coprime coefficients whose largest coefficient has bit-size $Θ(2^j)$.

Authors: Ignacio Barros, Michaël Cadilhac, Guillermo A. Pérez

We study existential Presburger arithmetic extended with divisibility predicates (EPAD). Its satisfiability problem has long been known to be NP-hard, and has often been expected to lie in NP. We prove that it is PP-hard, ruling out this expectation unless NP=PP. This also implies \PP-hardness of satisfiability for positive Boolean combinations of word equations and length constraints. The lower bound is compatible with a strong form of Lipshitz-style simplification. We define a polynomial-time recognizable fragment, called \MergeAbs, in which the usual finite-quotient replacement of divisibility atoms can be repeated until no divisibility atom remains. Nevertheless, EPAD satisfiability is already PP-hard on this fully simplifiable fragment. The reduction starts from a threshold coefficient problem for a class of arithmetic circuits using only addition and shifts. The same systems used in the reduction also expose a limitation of normalization. A polynomial-size scaling family, indexed by $j$, forces an endpoint relation $v=(2^{2^j}+1)u$, and the natural finite-quotient simplification records it as one equation with coprime coefficients whose largest coefficient has bit-size $Θ(2^j)$.

Monday, June 15 2026, 00:00

On Cutting Cakes and Crossing Curves

from arXiv: Computational Complexity

Authors: Alexandros Hollender, Gilbert Maystre, Kilian Risse

We consider the classic envy-free cake-cutting problem where the goal is to cut and allocate a divisible resource among a set of agents in a way that avoids any envy between them. When the agents' valuation functions are continuous and nonnegative, an envy-free solution is guaranteed to exist where each agent is allocated a contiguous piece of the resource. Such a solution can be efficiently computed using the standard cut-and-choose algorithm for two agents, but the problem is known to be hard when there are at least four agents. The setting with three agents has remained open. We show that the problem remains intractable for three agents. We obtain this result by uncovering a novel connection between cake-cutting and a computational problem corresponding to the Jordan curve theorem, introduced by Adler, Daskalakis, and Demaine (2016). As our main technical contribution, we provide the first lower bounds for the Jordan curve problem in the form of a query lower bound as well as hardness for the class UEOPL, a subclass of PPAD containing notoriously challenging problems such as Simple Stochastic Games and the P-matrix Linear Complementarity Problem.

Authors: Alexandros Hollender, Gilbert Maystre, Kilian Risse

We consider the classic envy-free cake-cutting problem where the goal is to cut and allocate a divisible resource among a set of agents in a way that avoids any envy between them. When the agents' valuation functions are continuous and nonnegative, an envy-free solution is guaranteed to exist where each agent is allocated a contiguous piece of the resource. Such a solution can be efficiently computed using the standard cut-and-choose algorithm for two agents, but the problem is known to be hard when there are at least four agents. The setting with three agents has remained open. We show that the problem remains intractable for three agents. We obtain this result by uncovering a novel connection between cake-cutting and a computational problem corresponding to the Jordan curve theorem, introduced by Adler, Daskalakis, and Demaine (2016). As our main technical contribution, we provide the first lower bounds for the Jordan curve problem in the form of a query lower bound as well as hardness for the class UEOPL, a subclass of PPAD containing notoriously challenging problems such as Simple Stochastic Games and the P-matrix Linear Complementarity Problem.

Monday, June 15 2026, 00:00

The Program Is Still There: A Conservation Law for Program Discovery

from arXiv: Computational Complexity

Authors: Jorge Miguel Silva

Finding the shortest program that generates a sequence is uncomputable, and for six decades that fact has been mistaken for a wall around finding any generating program. It is not a wall but a price, and this paper measures it. For every algorithm that learns about a candidate program only through its score, a class spanning Levin search, evolutionary methods, simulated annealing, and the cross-entropy method, we define the coupling width of a search problem and prove an unconditional worst-case lower bound, exponential in that width with base one less than the domain size. From it follows a conservation law: structural knowledge injected into a search trades one for one against the search it removes, and their sum can never fall below the length of the program sought. Levin's 1973 upper bound and the lower bound proved here are the two ends of one conserved quantity, closing on each other as the instruction set grows. The only escape is to read a candidate's structure rather than its score, and its price, which we prove for generic targets, is incompleteness. A deterministic engine built on this theory recovers a generating program, certified by compressing its data and predicting an unseen continuation, for 2,383 of 3,914 sequences across four independent populations, including 244 of the 256 elementary cellular automata, with measured discovery cost rising along program length more than an order of magnitude inside the score-oracle worst case.

Authors: Jorge Miguel Silva

Finding the shortest program that generates a sequence is uncomputable, and for six decades that fact has been mistaken for a wall around finding any generating program. It is not a wall but a price, and this paper measures it. For every algorithm that learns about a candidate program only through its score, a class spanning Levin search, evolutionary methods, simulated annealing, and the cross-entropy method, we define the coupling width of a search problem and prove an unconditional worst-case lower bound, exponential in that width with base one less than the domain size. From it follows a conservation law: structural knowledge injected into a search trades one for one against the search it removes, and their sum can never fall below the length of the program sought. Levin's 1973 upper bound and the lower bound proved here are the two ends of one conserved quantity, closing on each other as the instruction set grows. The only escape is to read a candidate's structure rather than its score, and its price, which we prove for generic targets, is incompleteness. A deterministic engine built on this theory recovers a generating program, certified by compressing its data and predicting an unseen continuation, for 2,383 of 3,914 sequences across four independent populations, including 244 of the 256 elementary cellular automata, with measured discovery cost rising along program length more than an order of magnitude inside the score-oracle worst case.

Monday, June 15 2026, 00:00

Moving between 3-manifold triangulations is NP-hard

from arXiv: Computational Geometry

Authors: Stephan Tillmann, Anastasiia Tsvietkova

We show that \textsc{number of bistellar moves and sparse degree-two edge collapses for 3-sphere} is NP-hard. It follows that a similar problem for an arbitrary 3-manifold is NP-hard as well. This is the first NP-hardness result concerning moves between two triangulations of a 3-manifold.

Authors: Stephan Tillmann, Anastasiia Tsvietkova

We show that \textsc{number of bistellar moves and sparse degree-two edge collapses for 3-sphere} is NP-hard. It follows that a similar problem for an arbitrary 3-manifold is NP-hard as well. This is the first NP-hardness result concerning moves between two triangulations of a 3-manifold.

Monday, June 15 2026, 00:00

An Efficient Private Algorithm for Community Detection

from arXiv: Data Structures and Algorithms

Authors: Vincent Cohen-Addad, Alessandro Epasto, Haim Kaplan, Hanna Komlós, Silvio Lattanzi

In this paper, we study the community detection problem in the stochastic block model (SBM) under privacy constraints. We introduce private and highly efficient algorithms for exact community detection within the SBM framework. Our algorithms represent the first differentially private methods capable of achieving exact recovery in a wide range of model parameters with near-linear time and space complexity. This is a significant improvement over previous SBM recovery algorithms, which either required pseudo-polynomial time or a quadratic scaling of resources for a constant privacy budget. Central to our approach is the introduction of a new concept, adaptive disjoint-star algorithms. These algorithms efficiently explore the graph's structure by querying node degrees on edge-disjoint subgraphs. We demonstrate that this general class of algorithms inherently offers strong privacy guarantees, a result that potentially holds value beyond the scope of SBM community detection. Finally, in we perform an empirical analysis of our algorithms showing that they can scale exact recovery on graphs with two orders of magnitude more nodes than prior work.

Authors: Vincent Cohen-Addad, Alessandro Epasto, Haim Kaplan, Hanna Komlós, Silvio Lattanzi

In this paper, we study the community detection problem in the stochastic block model (SBM) under privacy constraints. We introduce private and highly efficient algorithms for exact community detection within the SBM framework. Our algorithms represent the first differentially private methods capable of achieving exact recovery in a wide range of model parameters with near-linear time and space complexity. This is a significant improvement over previous SBM recovery algorithms, which either required pseudo-polynomial time or a quadratic scaling of resources for a constant privacy budget. Central to our approach is the introduction of a new concept, adaptive disjoint-star algorithms. These algorithms efficiently explore the graph's structure by querying node degrees on edge-disjoint subgraphs. We demonstrate that this general class of algorithms inherently offers strong privacy guarantees, a result that potentially holds value beyond the scope of SBM community detection. Finally, in we perform an empirical analysis of our algorithms showing that they can scale exact recovery on graphs with two orders of magnitude more nodes than prior work.

Monday, June 15 2026, 00:00

On a Conjecture for Parameterized st-Orientations

from arXiv: Data Structures and Algorithms

Authors: Charalampos Papamanthou

MaxSTN and MinSTN -- proposed by Papamanthou and Tollis (TCS 2008, JGAA 2010) -- are two algorithms for producing $st$-orientations of biconnected graphs with long and short longest paths respectively. Based on extensive experiments on planar and non-planar graphs of up to 5,000 nodes, it was conjectured that $\ell_{\max} \geq \ell_{\min}$ for every biconnected graph $G$, where $\ell_{\max}$ and $\ell_{\min}$ denote the longest-path lengths of the two orientations. This paper disproves this conjecture by exhibiting a biconnected graph on 9 vertices for which MaxSTN yields $\ell_{\max}=6$ while MinSTN yields $\ell_{\min}=7$, regardless of how ties are broken in either algorithm.

Authors: Charalampos Papamanthou

MaxSTN and MinSTN -- proposed by Papamanthou and Tollis (TCS 2008, JGAA 2010) -- are two algorithms for producing $st$-orientations of biconnected graphs with long and short longest paths respectively. Based on extensive experiments on planar and non-planar graphs of up to 5,000 nodes, it was conjectured that $\ell_{\max} \geq \ell_{\min}$ for every biconnected graph $G$, where $\ell_{\max}$ and $\ell_{\min}$ denote the longest-path lengths of the two orientations. This paper disproves this conjecture by exhibiting a biconnected graph on 9 vertices for which MaxSTN yields $\ell_{\max}=6$ while MinSTN yields $\ell_{\min}=7$, regardless of how ties are broken in either algorithm.

Monday, June 15 2026, 00:00

Designing Efficient and Reachable Routes: The $k$-Step-Central Shortest Path Problem

from arXiv: Data Structures and Algorithms

Authors: Johnson Phosavanh, Dmytro Matsypura

Designing rapid transportation routes requires balancing efficiency and reachability. Shortest-path models ensure direct, cost-efficient routes but ignore coverage, while centrality-based approaches maximize accessibility but do not enforce operational constraints. We study the problem of selecting a shortest path that maximizes reachability, measured as the number of nodes within a fixed distance of the path. To do this, we introduce the $k$-Step-Central Shortest Path problem and analyse its structural properties. We show that optimal solutions on unweighted graphs can be found in polynomial time and propose an algorithm with a novel pruning rule. We also prove that the problem becomes NP-hard when edge weights are introduced. Additionally, we show that our algorithm can be used to solve the NP-hard problem of finding the closeness-central shortest path in a graph. We demonstrate the efficiency and scalability of our algorithm on synthetic and real-world networks with up to 2,000 nodes. Our results show that improving reachability can substitute for route expansion: increasing the reach of transit lines drastically increases their coverage with shorter routes. This suggests that investments in active transport infrastructure that improve reachability can be more effective than extending primary routes, providing a data-driven basis for allocating resources in network design.

Authors: Johnson Phosavanh, Dmytro Matsypura

Designing rapid transportation routes requires balancing efficiency and reachability. Shortest-path models ensure direct, cost-efficient routes but ignore coverage, while centrality-based approaches maximize accessibility but do not enforce operational constraints. We study the problem of selecting a shortest path that maximizes reachability, measured as the number of nodes within a fixed distance of the path. To do this, we introduce the $k$-Step-Central Shortest Path problem and analyse its structural properties. We show that optimal solutions on unweighted graphs can be found in polynomial time and propose an algorithm with a novel pruning rule. We also prove that the problem becomes NP-hard when edge weights are introduced. Additionally, we show that our algorithm can be used to solve the NP-hard problem of finding the closeness-central shortest path in a graph. We demonstrate the efficiency and scalability of our algorithm on synthetic and real-world networks with up to 2,000 nodes. Our results show that improving reachability can substitute for route expansion: increasing the reach of transit lines drastically increases their coverage with shorter routes. This suggests that investments in active transport infrastructure that improve reachability can be more effective than extending primary routes, providing a data-driven basis for allocating resources in network design.

Monday, June 15 2026, 00:00

Flood and Harvest: The Provable Necessity of Trivia for Generating Valuable Mathematics via the Lens of Language Generation in the Limit

from arXiv: Data Structures and Algorithms

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

AI systems coupled to proof assistants now generate formal mathematics at scale, and the gap between what a checker can verify and what a mathematician would value has become the binding constraint. We model the generation of valuable mathematics as nested language generation in the limit: a verifiable formal language $F$, accessed through a membership oracle (the proof checker), contains an unknown valuable language $H \in \mathcal{H}$ revealed only through an adversarial enumeration of a core $C \subseteq H$ of exact density $α$ (the literature). Every output is valuable ($\in H$), trivial ($\in F \setminus H$), or a hallucination ($\notin F$). We settle four questions. First, the verifier is not taste: the collections admitting generation with breadth are exactly those of the oracle-free model, characterized fiber-wise by Angluin's condition. Second, the verifier does buy sound coverage, covering all unseen valuable statements while asserting only valid ones: possible with it, impossible without it; it relocates unavoidable errors from false to trivial. Third, and centrally, a sharp dichotomy on the tight family: generators emitting finitely many trivia achieve optimal coverage $α/2$, while any infinite trivia allowance, even at vanishing rate, jumps the optimum to $1-α/2$ (both tight, for cores presented as the candidate intersection), and one generator attains both ends. The transition is in trivia count, not rate; the gap $1-α$ is the unrecorded mass. Fourth, both regimes instantiate in a compression model of mathematics. A perfect verifier cannot substitute for taste: the unbounded stream of correct-but-worthless statements is not an engineering accident but a provable necessity, since covering unrecorded valuable mathematics requires an infinite, but asymptotically negligible, stream of certified trivia.

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

AI systems coupled to proof assistants now generate formal mathematics at scale, and the gap between what a checker can verify and what a mathematician would value has become the binding constraint. We model the generation of valuable mathematics as nested language generation in the limit: a verifiable formal language $F$, accessed through a membership oracle (the proof checker), contains an unknown valuable language $H \in \mathcal{H}$ revealed only through an adversarial enumeration of a core $C \subseteq H$ of exact density $α$ (the literature). Every output is valuable ($\in H$), trivial ($\in F \setminus H$), or a hallucination ($\notin F$). We settle four questions. First, the verifier is not taste: the collections admitting generation with breadth are exactly those of the oracle-free model, characterized fiber-wise by Angluin's condition. Second, the verifier does buy sound coverage, covering all unseen valuable statements while asserting only valid ones: possible with it, impossible without it; it relocates unavoidable errors from false to trivial. Third, and centrally, a sharp dichotomy on the tight family: generators emitting finitely many trivia achieve optimal coverage $α/2$, while any infinite trivia allowance, even at vanishing rate, jumps the optimum to $1-α/2$ (both tight, for cores presented as the candidate intersection), and one generator attains both ends. The transition is in trivia count, not rate; the gap $1-α$ is the unrecorded mass. Fourth, both regimes instantiate in a compression model of mathematics. A perfect verifier cannot substitute for taste: the unbounded stream of correct-but-worthless statements is not an engineering accident but a provable necessity, since covering unrecorded valuable mathematics requires an infinite, but asymptotically negligible, stream of certified trivia.

Monday, June 15 2026, 00:00

Online Convex Optimization with Sublinear Noisy Probes

from arXiv: Data Structures and Algorithms

Authors: Simone Di Gregorio, Anupam Gupta, Stefano Leonardi, Matteo Russo

We study Online Convex Optimization (OCO) over a convex set $K\subseteq \mathbb R^d$, where in each round $t$ the learner selects $x_t\in K$ and then observes a convex loss $f_t:K\to[0,1]$, with the goal of minimizing regret to the best fixed decision in hindsight. We introduce a unified probing model that generalizes two recent lines of work: sublinear best-expert queries in the experts setting, and pairwise (comparison-based) feedback available every round in OCO. In our framework, the learner has a budget of $k\le T$ pairwise probes; on a probed round it may query two points and learn which one has smaller loss. Our main result shows that even a sublinear and noisy probe budget can provably improve worst-case regret in the full feedback OCO regime. With $k$ $δ$-noisy pairwise probes, we obtain: $ \text{Reg}_T \le O\left(\min\left\{\sqrt{dT\ln T},\; \frac{dT\ln T}{k|1-2δ|}\right\}\right) $, which is tight (up to logarithmic factors in $T$) across $T$, $k$ and $δ$. Specifically regarding the noise parameter $δ\in [0,1]$, the regret guarantee smoothly degrades as the oracle response approaches a coin flip, i.e., $δ$ is close to $\frac{1}{2}$. When applying the same techniques to a finite $K$ for the prediction with $d$ experts setting, the resulting rates are instead completely tight in all parameters, including $d$. Our analysis gives a streamlined treatment of pairwise probing in OCO by quantifying the benefit of probing via a variance reduction effect, combined with a second-order (variance-based) analysis of Continuous Exponential Weights.

Authors: Simone Di Gregorio, Anupam Gupta, Stefano Leonardi, Matteo Russo

We study Online Convex Optimization (OCO) over a convex set $K\subseteq \mathbb R^d$, where in each round $t$ the learner selects $x_t\in K$ and then observes a convex loss $f_t:K\to[0,1]$, with the goal of minimizing regret to the best fixed decision in hindsight. We introduce a unified probing model that generalizes two recent lines of work: sublinear best-expert queries in the experts setting, and pairwise (comparison-based) feedback available every round in OCO. In our framework, the learner has a budget of $k\le T$ pairwise probes; on a probed round it may query two points and learn which one has smaller loss. Our main result shows that even a sublinear and noisy probe budget can provably improve worst-case regret in the full feedback OCO regime. With $k$ $δ$-noisy pairwise probes, we obtain: $ \text{Reg}_T \le O\left(\min\left\{\sqrt{dT\ln T},\; \frac{dT\ln T}{k|1-2δ|}\right\}\right) $, which is tight (up to logarithmic factors in $T$) across $T$, $k$ and $δ$. Specifically regarding the noise parameter $δ\in [0,1]$, the regret guarantee smoothly degrades as the oracle response approaches a coin flip, i.e., $δ$ is close to $\frac{1}{2}$. When applying the same techniques to a finite $K$ for the prediction with $d$ experts setting, the resulting rates are instead completely tight in all parameters, including $d$. Our analysis gives a streamlined treatment of pairwise probing in OCO by quantifying the benefit of probing via a variance reduction effect, combined with a second-order (variance-based) analysis of Continuous Exponential Weights.

Monday, June 15 2026, 00:00

TR26-100 | Bipartite Matching is in NC | Rohit Gurjar, Roshan Raj, Thomas Thierauf, Abhranil Chatterjee, Sumanta Ghosh

from ECCC Papers

We show that the bipartite matching problem is in NC. We extend the result to weighted bipartite matching and the computation of the noncommutative rank of a symbolic matrix. In particular, this implies that the decision version of linear matroid intersection is in NC as well. The techniques are based on the polynomial method, inspired from a construction of subspace design by Guruswami and Kopparty (Combinatorica 2016).

Sunday, June 14 2026, 15:43

TR26-099 | Kikuchi Graphs of Random Hypergraphs are Approximately Johnson | Pravesh Kothari

from ECCC Papers

We prove that level-$\ell$ Kikuchi graphs of random $2r$-uniform hypergraphs spectrally approximate Kikuchi graph of the complete $2r$-uniform hypergraph at a sampling rate that is sharp up to a logarithmic factor, in the regime $r\leq \ell \leq n/2$. Our proof is based on the matrix Bernstein inequality, but, unlike prior works, we apply it to an appropriate collection of blocks of Johnson eigenspaces. Our analysis relies on a new, simple band-locality property for arbitrary Kikuchi graphs. As an application, we prove that the natural degree-$2\ell$ sum-of-squares relaxation for the Max $2r$-XOR problem is ``integral'' when the input is a planted noisy $2r$-XOR instance on a random hypergraph with $\gtrsim n \cdot (n/\ell)^{r-1} \log n$ hyperedges.

Sunday, June 14 2026, 13:05

TR26-098 | SNARGs for NP from Unprovability of Mathematical Theorems | Jiatu Li, YaoChing Hsieh, Abhishek Jain, Surya Mathialagan

from ECCC Papers

Modern cryptography relies on the intractability of computational problems. We present an approach to build cryptography from a new source of hardness: proving mathematical theorems. Our main result is a construction of succinct non-interactive arguments (SNARGs) for NP under standard derandomization (prBPP = prP) and cryptographic assumptions (LWE and SXDH), as well as a new, but natural assumption on the hardness of proving lower bounds in proof complexity. Specifically, our assumption states that it is impossible to prove, within a weak bounded arithmetic theory, the correctness of certifying hard tautologies against Extended Frege. This assumption is inspired by an informal mathematical challenge proposed by Razborov [Ann. Math. '15], and can be viewed as a generalization of an unconditional unprovability result due to Krají?ek and Pudlák [J. Symb. Log. '89]. Our construction is, in fact, a simple variant of the SNARG constructed by Jin, Kalai, Lombardi, and Vaikuntanathan [STOC '24]. While the soundness of their construction was only proven for a subclass of NP, we prove its soundness for all NP under our assumption. At the heart of our result is the key observation that cryptographic reasoning is simple in a formal sense: the security proof of most cryptographic primitives can be formalized in a weak theory. In particular, we show how to formalize the scheme of Jin et al. in Je?ábek's theory APC? [J. Symb. Log. '07] -- a weak theory in bounded arithmetic.

Sunday, June 14 2026, 05:45

The "fable" of Anthropic and the USG

from The Geomblog

News moves fast. 12 hours ago I was enjoying the demolition that the US put on Paraguay when I heard that Anthropic had shut down access to Fable and Mythos (their latest and most powerful models).

Since then, more news has surfaced about what went down, and I feel like it's a good exercise in understanding both the policy and psychodrama around AI today - with maybe even a moral or two like Aesop's .... FABLES (yes I'm going to keep making bad jokes and no you can't stop me)

Part 1: The event

Let's first lay out the facts of the matter. To the best of my knowledge, here's what transpired.

Some researchers (apparently at Amazon) uncovered ways to jailbreak Fable to (possibly) perform cybersecurity-related attacks.
Someone (apparently Andy Jassy) told the White House (or the Treasury Secretary) about this.
The WH and Anthropic had a back and forth on what needed to be done about this: Anthropic claimed these were not serious jalbreaks, and the WH said that they were and that Anthropic needed to either take down the model or something...
The WH then invoked export controls to demand that Anthropic block access to Fable/Mythos for foreign nationals (regardless of where they happen to be)
Anthropic blocked access entirely, arguing that they had no way of distinguishing foreign nationals from American citizens.

Now most of the reporting will focus on solidifying the facts of the matter (I hope) and will probably also focus on the drama. Drama is fun (don't get me wrong), but it can make thinking about policy really hard.
So let me lay out some of the questions about the drama that might be useful to have answered, but then try to focus on the bigger policy questions that come out of this.

What were these mysterious jailbreaks? This is actually an important question that will shape the policy response as well.
How were these jailbreaks flagged and sent up the chain, and why was the communication of the form "hey I called my buddy at the WH and told him stuff"?
What actually transpired in the discussion between the WH and Anthropic?

Part II: Clean-slate PolicyLet's pretend we are working in a vacuum for a second, and think about this with policy hats on, without worrying about the actual players (unrealistic I know, but a useful exercise).
The US Government is worried about powerful models allowing any user to generate (say) cybersecurity hacks that can compromise critical national infrastructure (for e.g the financial sector which is why the Treasury Secretary is paying close attention). These models are general purpose and have many uses, and the USG doesn't just want to shut them down entirely (we can debate that, but not right now).
What they'd like to do is have some way to monitor models for specific kinds of risks, before deployment, and also on a continuing basis. Maybe there's some kind of voluntary program where providers of powerful models give access to independent testers (for eg. some kind of Center for AI Security Standards and Innovation) who can identify risks, communicate these risks to the companies involved, and make sure that mitigations are put in place. It wouldn't be perfect, but it would be an ongoing process.
If this sounds familiar, it should. because a) it's how we do cybersecurity right now without any government involvement and b) it's a little bit of how the recent WH EO was constructed (there were other parts of the EO that are problematic, but again, not for now)
In other words, there's a way to do what the government wants if this is indeed what they want and companies are willing to cooperate (this is setting aside whether you and I want the government to do this. That's a different discussion)
Part III: (we know) DramaWell. that's all well and good. But I don't unfortunately live in a rationalist universe where I can write 20,000 word screeds on moreright.com and be "aligned" with everyone else. What's the reality here?
The first thing I want to emphasize is that drama loves a good guy (yes "guy") and a bad guy, and it's really tempting to first decide who's the bad guy and then decide the other one must be good. It would be really tempting to say for e.g "the Trump administration has no clue on AI and therefore Anthropic is the good guy", or "Tech companies are evillll and the administration is therefore doing the right thing".
Unfortunately (reporters please please pretty please pay attention), it's not that simple.
There are no innocent actors here.
This particular administration has always approached AI regulation in a very "we will say we are hands off but actually we are not but it's really about who's in favor and who's not that decides how we will act" way. Trying to retrofit logical policy actions onto that is hard, and this case is no different. The administration seems to operate its AI policy on some mix of favoritism, pique, and vengeance, and so it's hard to reconcile this reaction with the complete silence when (say) Grok was churning out CSAM and deepfake nonconsensual porn on demand while also being used within the department of war defense. For more on the internal incoherence of the administration's approach to AI, see Justin Hendrix's great analysis.
Anthropic is the "hero" of the moment, because their seeming adversary is the "bad guy" for so many in tech policy. But on the eve of the UFC fight on the WH lawn, keep in mind that these are all actors, and there's an audience. Anthropic is about to go public and make an insane amount of money for some people. It's in their interest to say "oh yeah our models are SCARY (good) and the best out there" and also say at the same time "Yeah your jailbreak is not that scary and we are fine and can release our systems". I don't doubt that there are people at Anthropic who genuinely believe such things, but Anthropic is a corporation (not a "lab") and is in the business of market control and profit.
Specifically, it is entirely possible that Fable is both a great improvement on Opus, and can do some questionable things better, and is also susceptible to the same jailbreaks and vulnerabilities as other models. It's possible it's not some special unicorn that is so dangerous we all have to trust in Anthropic's good intentions, but just the next incarnation of a product with many of the same weaknesses. We just don't know because Anthropic won't say, and won't actually allow for independent testing separately from the folks they want to give access to.
Part IV: So what should we do? This episode doesn't change many of the things we understand already about the contours of AI policy. And in fact it's dangerous to overindex on one episode - that tends to leads to a whack-a-mole approach to doing AI regulation that has been harmful in other settings.
1. We need to regulate the downstream risks and harms that come from the introduction of AI.
All this nonsense around "but but innovation" needs to stop. You can tell an argument is not very useful when it's been used over and over again for virtually every single sector of society over the past century, including all the currently regulated sectors that we don't want to loosen regulations on.
We need to do this 10 years ago. And we need to do this now. The AI industry is not some delicate hothouse flower that needs nurturing. It's a robust trillion dollar enterprise that's reshaping our world and will do so without our say so.
2. It's more effective to focus sector by sector.
Cybersecurity risks are concrete risks that we can evaluate in a focused way. And we can make use of the infrastructure and policy around cybersecurity to do so. Will this exact framework work for (say) threats to the electrical grid? probably not, and so we need a different "vertical" for understanding, evaluating, and mitigating risks in that sector. And so on.
3. You don't need to focus only on the tech: focus on the ecosystem of actors and safeguards currently in place
There's a lot of concern around the use of AI in medicine, and in the financial sector. But these are both heavily regulated sectors where there are already checks in place to make sure that the systems function as we want them to. Are they perfect? no. But it's easier to tweak an existing system of safeguards. Maybe AI is used to generate a new drug: but such a drug will need to go through regular clinical trials with real people (not synthetic!) in order to be put on the market. So focus on where AI might be compromising an existing system of governance, rather than assuming we need to regulate the model itself.
4. Testing testing testing (independently) To really assess the risks associated with the introduction of AI in different sectors, we need ... testing. Independent testing - not whatever blog posts the labs companies put out. But focused testing on specific issues, rather than general "capability testing". And we need to build and support the infrastructure for that. This is already too long to go on a rant about the decimation of the scientific research apparatus in the US courtesy of the administration, but yes, the decimation of the scientific research apparatus in the US will have a direct effect on our ability to test for risks and harms, and has to be part of any policy directions we explore.

By Suresh Venkatasubramanian

News moves fast. 12 hours ago I was enjoying the demolition that the US put on Paraguay when I heard that Anthropic had shut down access to Fable and Mythos (their latest and most powerful models).

Since then, more news has surfaced about what went down, and I feel like it's a good exercise in understanding both the policy and psychodrama around AI today - with maybe even a moral or two like Aesop's .... FABLES (yes I'm going to keep making bad jokes and no you can't stop me)

Part 1: The event

Let's first lay out the facts of the matter. To the best of my knowledge, here's what transpired.

Some researchers (apparently at Amazon) uncovered ways to jailbreak Fable to (possibly) perform cybersecurity-related attacks.
Someone (apparently Andy Jassy) told the White House (or the Treasury Secretary) about this.
The WH and Anthropic had a back and forth on what needed to be done about this: Anthropic claimed these were not serious jalbreaks, and the WH said that they were and that Anthropic needed to either take down the model or something...
The WH then invoked export controls to demand that Anthropic block access to Fable/Mythos for foreign nationals (regardless of where they happen to be)
Anthropic blocked access entirely, arguing that they had no way of distinguishing foreign nationals from American citizens.

Now most of the reporting will focus on solidifying the facts of the matter (I hope) and will probably also focus on the drama. Drama is fun (don't get me wrong), but it can make thinking about policy really hard.

So let me lay out some of the questions about the drama that might be useful to have answered, but then try to focus on the bigger policy questions that come out of this.

What were these mysterious jailbreaks? This is actually an important question that will shape the policy response as well.
How were these jailbreaks flagged and sent up the chain, and why was the communication of the form "hey I called my buddy at the WH and told him stuff"?
What actually transpired in the discussion between the WH and Anthropic?

Part II: Clean-slate Policy

Let's pretend we are working in a vacuum for a second, and think about this with policy hats on, without worrying about the actual players (unrealistic I know, but a useful exercise).

The US Government is worried about powerful models allowing any user to generate (say) cybersecurity hacks that can compromise critical national infrastructure (for e.g the financial sector which is why the Treasury Secretary is paying close attention). These models are general purpose and have many uses, and the USG doesn't just want to shut them down entirely (we can debate that, but not right now).

What they'd like to do is have some way to monitor models for specific kinds of risks, before deployment, and also on a continuing basis. Maybe there's some kind of voluntary program where providers of powerful models give access to independent testers (for eg. some kind of Center for AI Security Standards and Innovation) who can identify risks, communicate these risks to the companies involved, and make sure that mitigations are put in place. It wouldn't be perfect, but it would be an ongoing process.

If this sounds familiar, it should. because a) it's how we do cybersecurity right now without any government involvement and b) it's a little bit of how the recent WH EO was constructed (there were other parts of the EO that are problematic, but again, not for now)

In other words, there's a way to do what the government wants if this is indeed what they want and companies are willing to cooperate (this is setting aside whether you and I want the government to do this. That's a different discussion)

Part III: (we know) Drama

Well. that's all well and good. But I don't unfortunately live in a rationalist universe where I can write 20,000 word screeds on moreright.com and be "aligned" with everyone else. What's the reality here?

The first thing I want to emphasize is that drama loves a good guy (yes "guy") and a bad guy, and it's really tempting to first decide who's the bad guy and then decide the other one must be good. It would be really tempting to say for e.g "the Trump administration has no clue on AI and therefore Anthropic is the good guy", or "Tech companies are evillll and the administration is therefore doing the right thing".

Unfortunately (reporters please please pretty please pay attention), it's not that simple.

There are no innocent actors here.

This particular administration has always approached AI regulation in a very "we will say we are hands off but actually we are not but it's really about who's in favor and who's not that decides how we will act" way. Trying to retrofit logical policy actions onto that is hard, and this case is no different. The administration seems to operate its AI policy on some mix of favoritism, pique, and vengeance, and so it's hard to reconcile this reaction with the complete silence when (say) Grok was churning out CSAM and deepfake nonconsensual porn on demand while also being used within the department of war defense. For more on the internal incoherence of the administration's approach to AI, see Justin Hendrix's great analysis.

Anthropic is the "hero" of the moment, because their seeming adversary is the "bad guy" for so many in tech policy. But on the eve of the UFC fight on the WH lawn, keep in mind that these are all actors, and there's an audience. Anthropic is about to go public and make an insane amount of money for some people. It's in their interest to say "oh yeah our models are SCARY (good) and the best out there" and also say at the same time "Yeah your jailbreak is not that scary and we are fine and can release our systems". I don't doubt that there are people at Anthropic who genuinely believe such things, but Anthropic is a corporation (not a "lab") and is in the business of market control and profit.

Specifically, it is entirely possible that Fable is both a great improvement on Opus, and can do some questionable things better, and is also susceptible to the same jailbreaks and vulnerabilities as other models. It's possible it's not some special unicorn that is so dangerous we all have to trust in Anthropic's good intentions, but just the next incarnation of a product with many of the same weaknesses. We just don't know because Anthropic won't say, and won't actually allow for independent testing separately from the folks they want to give access to.

Part IV: So what should we do?

This episode doesn't change many of the things we understand already about the contours of AI policy. And in fact it's dangerous to overindex on one episode - that tends to leads to a whack-a-mole approach to doing AI regulation that has been harmful in other settings.

1. We need to regulate the downstream risks and harms that come from the introduction of AI.

All this nonsense around "but but innovation" needs to stop. You can tell an argument is not very useful when it's been used over and over again for virtually every single sector of society over the past century, including all the currently regulated sectors that we don't want to loosen regulations on.

We need to do this 10 years ago. And we need to do this now. The AI industry is not some delicate hothouse flower that needs nurturing. It's a robust trillion dollar enterprise that's reshaping our world and will do so without our say so.

2. It's more effective to focus sector by sector.

Cybersecurity risks are concrete risks that we can evaluate in a focused way. And we can make use of the infrastructure and policy around cybersecurity to do so. Will this exact framework work for (say) threats to the electrical grid? probably not, and so we need a different "vertical" for understanding, evaluating, and mitigating risks in that sector. And so on.

3. You don't need to focus only on the tech: focus on the ecosystem of actors and safeguards currently in place

There's a lot of concern around the use of AI in medicine, and in the financial sector. But these are both heavily regulated sectors where there are already checks in place to make sure that the systems function as we want them to. Are they perfect? no. But it's easier to tweak an existing system of safeguards. Maybe AI is used to generate a new drug: but such a drug will need to go through regular clinical trials with real people (not synthetic!) in order to be put on the market. So focus on where AI might be compromising an existing system of governance, rather than assuming we need to regulate the model itself.

4. Testing testing testing (independently)

To really assess the risks associated with the introduction of AI in different sectors, we need ... testing. Independent testing - not whatever blog posts the labs companies put out. But focused testing on specific issues, rather than general "capability testing". And we need to build and support the infrastructure for that. This is already too long to go on a rant about the decimation of the scientific research apparatus in the US courtesy of the administration, but yes, the decimation of the scientific research apparatus in the US will have a direct effect on our ability to test for risks and harms, and has to be part of any policy directions we explore.

By Suresh Venkatasubramanian

Saturday, June 13 2026, 20:51

Congratulations, Dr. Sridhar!

from David Eppstein

This past week was the final exam week for our spring term, and in it we also held the doctoral defense of another Ph.D. student, Vinesh Sridhar (advised by Mike Goodrich). Vinesh organized his thesis in an unusually symmetric way, with two parts on computing with noisy primitives, two parts on in-place algorithms, two parts on sequential algorithms, and two parts on parallel algorithms, in four combinations (noisy sequential, noisy parallel, in-place sequential, in-place parallel).

I’ve previously written here about Vinesh’s work with Mike and me on computational geometry algorithms with noisy primitives, which we published in WADS 2025. In this work, following a random walk back and forth along a search path in a history DAG or other geometric data structure (and occasionally, choosing a false step and then backtracking) allows algorithms based on this idea to avoid the logarithmic time penalty of repeating each noisy query for enough repetitions to be sure that it is accurate. Being sure means “with high probability”: the failure probability should be inversely polynomial in the input size.

Vinesh and Mike published a parallel follow-up to this at CCCG 2025, “Optimal parallel algorithms for convex hulls in 2d and 3d under noisy primitive operations”. A difficulty here is that, for a divide-and-conquer algorithm, a failure probability that is inverse polynomial in the size of a small subproblem may not be inverse polynomial in the much larger input size. To work around this, Vinesh and Mike used the idea of “failure sweeping”, in which one divides the input into polynomially-many subproblems, lets some of them fail with a probability that is larger than the target failure probability (but still small enough that with high probability there are few failures). Then, one cleans up the failed subproblems in a second pass using a fast and more reliable parallel algorithm with a greater total work bound that is cancelled by the smaller number of subproblems.

The in-place part of Vinesh’s thesis focused on in-place sorting algorithms, where one is allowed only $O(1)$ extra words of memory beyond the array being sorted. The classical choice for this is heapsort, which can be implemented to run in-place and takes time $O(n\log n)$ to sort an $n$-item array. This is optimal in the worst case, but many other sorting algorithms go beyond worst case time complexity to run more quickly for inputs that are not completely unsorted. An important class of these are entropy-sensitive sorting algorithms. Their runtime on input sequences that can be partitioned into $r$ sorted runs of size $n_i$ is $O(n(H+1))$, where the entropy $H$ is defined by

\[\mathrm{H}=-\sum_{i=1}^r \frac{n_i}{n}\log_2 \frac{n_i}{n}.\]

This can be done by finding runs and then repeatedly merging the shortest two, but the merged runs may not be consecutive in the input sequence, making an in-place merge problematic. Instead, Timsort and several similar alternatives build a stack of runs in a left-right scan of the input, while doing so merging pairs of short runs near the top of the stack. This leaves a sequence of sorted runs on the stack whose sizes grow roughly according to a geometric sequence, which can be repeatedly popped and merged. The geometric growth of the stack means that the stack itself can be stored in $O(\log n)$ space, but while small this is not small enough to be in-place. Vinesh finds two strategies for reducing the space in this family of algorithms. In the “walking” strategy, only the top $O(1)$ stack elements are maintained; the next ones below that are rediscovered one at a time, as they become needed, by a sequential search within each run. In the “jumping” strategy, some elements within each run are placed out of order, in order to encode extra information to speed up the walking algorithm. Vinesh shows that most entropy-sensitive merging algorithms (but not Timsort itself) can be made in-place by walking, and that all known ones can be made in-place by jumping. He published this work (joint with Ofek Gila and Mike Goodrich) as “How to sort in a refrigerator: Simple entropy-sensitive strictly in-place sorting algorithms” in LATIN 2026.

The final part of the thesis comes from a paper with the colorful title “Raiders of the lost log: Synchronous parallel in-place models and algorithms” (with Goodrich in the 28th Workshop on Advances in Parallel and Distributed Computational Models, 2026, and selected as an “outstanding paper” for APDCM 2027). It’s not currently free online but Vinesh and Mike promise to make an arXiv version soon. This part involves PRAM model parallel machines where the only shared memory is the input and each parallel processor has only a bounded amount of private memory. The title comes from a technique inspired by the first scene of the first Indiana Jones movie, in which Jones (unsuccessfully) swaps a sandbag for a booby-trapped gold figurine. In their algorithmic technique, Vinesh and Mike have the parallel processors each swap their working memory for a piece of the input data that they control, freeing up enough shared memory to perform their algorithms. They apply this technique not only to in-place sorting, but also to convex hulls, parallel primitives such as prefix sums and tree contraction, and the generation of random permutations.

The defense was presented very smoothly and clearly, and Vinesh’s many results (including several papers not included in the thesis) made for an easy pass of his defense. Congratulations, Vinesh!

(Discuss on Mastodon)

By David Eppstein

Saturday, June 13 2026, 18:21

Announcing WoLA 2026 in Boston

from Property Testing Review

The 10th edition of WoLA, the Workshop on Local Algorithms, will be taking place on August 16-18, 2026 at at Boston University, Boston, MA, just before APPROX/RANDOM! For those unfamiliar with WoLA: Local algorithms, that is, algorithms that compute and make decisions on parts of the output considering only a portion of the input, have […]

The 10th edition of WoLA, the Workshop on Local Algorithms, will be taking place on August 16-18, 2026 at at Boston University, Boston, MA, just before APPROX/RANDOM!

For those unfamiliar with WoLA:

Local algorithms, that is, algorithms that compute and make decisions on parts of the output considering only a portion of the input, have been studied in a number of areas in theoretical computer science and mathematics. Some of these areas include sublinear-time algorithms, distributed algorithms, inference in large networks and graphical models. These communities have similar goals but a variety of approaches, techniques, and methods. This workshop is aimed at fostering dialogue and cross-pollination of ideas between the various communities.

You are all invited! For more on (free) registration, how to submit a poster or propose a talk, list of invited speakers, and local arrangements, see the website.

Don’t miss it! Not only is WoLA a truly enjoyable and interesting event, showcasing exciting new results and directions of research, it’s also one centered around an incredibly welcoming and collegial (and fun!) community of researchers. But that’s not all! Expect a particularly amazing edition this year, as this is the 10th anniversary edition of WoLA, and it is being held on the top floor of the new Computer and Data Sciences building at BU, with breathtaking views of Boston.

From Futurama: the Professor, saying "Good news, everyone"

Program Committee: Maryam Aliakbarpour (Rice University), Sepehr Assadi (University of Waterloo; Chair), Eric Blais (University of Waterloo), Yi-Jun Chang (National University of Singapore), Talya Eden (Bar Ilan University), Nathan Harms (University of British Columbia), Akash Kumar (IIT Bombay), Yannic Maus (TU Graz), Sofya Raskhodnikova (Boston University; Local Chair)), Chen Wang (Rensselaer Polytechnic Institute).

By Clement Canonne

Saturday, June 13 2026, 10:14

Language Models and Automated Reification

from Ben Recht

A new piece in The Ideas Letter with Leif Weatherby and Tyler Shoemaker.

Leif Weatherby, Tyler Shoemaker, and I have a new essay out today in The Ideas Letter about the creation of reality through pseudoscience, religion, and psychosis. Of course, it’s mostly about AI. Starting with the bizarre appearance of Antropic co-founder and mechanistic interpretability zealot Chris Olah at the side of Pope Leo as he read out his encyclical, we explore how commercial large language models automate the creation of reality.

The term of art for the process by which abstract concepts are made into material objects is reification. Marxist theorists think of the reification of social relations, where qualitative things like actions become commodified. This is the process by which labor becomes objectified and priced, and subsequently alienated from the person who does the work. Distinctly, historians and philosophers of science think of reification in terms of how correlational associations are named and become real through coordinated research programs. When your biggest companies all claim to be doing research, you can see how these two become one, with coordinated research becoming commodity itself.

LLMs are not only generated by a technological oligarchy, but also introduce a new twist into the process of reality generation. LLMs automate reification. LLMs are designed to produce explanations for us. We skip the steps in the collective creation of scientific concepts (aka thinking and arguing) and let LLMs do it for us through their linguistic association. LLMs entice you to skip the step of interpretation of outputs. Why not just ask Claude what it thinks?

As an illustrative example, we discuss Stephen J Gould’s historical analysis of the g factor in psychometrics research. In the social sciences, everything is correlated with everything. If you run some sort of correlational analysis on any data set, you’ll find something. Gould describes the process through which psychometricians decided that the correlational quantity that linked different measures of intelligence—the g factor—was real, and how they created a whole scientific research program to reinforce the reality of the g factor.

You know who still loves factor analysis? Mechanistic interpretability researchers. AI researchers have found themselves enamored with psychometrics as they work to prove their LLM toys are conscious. But they have new technology that Charles Spearman and his colleagues didn’t have a century ago: the LLMs themselves! Whereas 20th-century psychometrists had to think about causal stories to explain their strong correlational findings, interpretability researchers can automate this process. They can give an LLM the output of a factor analysis and ask it to explain the factors. Since it returns answers in natural language, this feels like discovery even though you have offloaded the process that would have been done by thinking about it to a machine. This process sets off a loop in which scientists and citizens alike give iterative credence to concepts generated by correlating text. We write:

“Models, in other words, kick off an associative chain of ideas by effectively auto-labeling queries. It’s like taking the principal components derived from that data about oak trees, boat speeds, cat whiskers, and Letterboxd reviews, and asking ChatGPT: “What do each of these artifacts mean?” ChatGPT will respond—and then keep the conversation going, bringing in more associations that more or less fit. But as we have already argued, this doesn’t only happen to amateurs who are easy to pathologize. How is this different from the standard methodology of interpretability research? In both the cases that might be dismissed as psychosis and the ones celebrated at AI conferences, interaction with LLMs induces mental friction. They create a feeling that discovery is there. By elaborating on what you put in through a context that the model has trained on, it is able to make connections that feel both correct and expansive, filling in the area around your thought—simulating the feeling that you are having a new thought. The model helps you refine the obscurity of your prompt through a chain of associations, and suddenly you have something. This is reification at work. And when the next link in a chain of thoughts comes along, it becomes hard to resist prompting the model again.”

LLMs are built to automate a complex web of reification. They are designed to tell us what we want to hear. As we write, “Trained on an enormous corpus of human writing, speech, and code, and tuned to refine responses around context and memory as user interactions unroll, a model of this kind is designed to provide the sense that one’s expectation is being exceeded.”

Artificial intelligence is a bizarre technology that participates in its own mythmaking. Anthropic is the most deeply invested in telling outrageous stories about its products, but no one in this space is innocent. As I’ve written before, I think that benchmarks get an unnecessarily bad rap. I certainly agree that you can’t “benchmark general purpose technology.” I agree that maxing out benchmark scores doesn’t mean a product will be better received by customers. But when we move away from benchmarking in artificial intelligence, we get stuck in storytelling. LLMs are designed and intended to convince us that their stories are real. When backed by a turbocharged capitalist engine, the reification becomes inevitable. Stories become commodities. Those commodities sell like hotcakes. And there is nothing more real than when the number goes up.

I’ll leave you there, as I need to go check on the value of my SpaceX shares. Read the whole article and let us know what you think.

Subscribe now

By Ben Recht

Friday, June 12 2026, 14:15

Workshop on Local Algorithms

from CS Theory Events

August 16-18, 2026 Boston University, Boston, USA www.local-algorithms.com/WOLA2026/ Local algorithms, that is, algorithms that compute and make decisions on parts of the output considering only a portion of the input, have been studied in a number of areas in theoretical computer science and mathematics. Some of these areas include sublinear-time algorithms, distributed algorithms, inference in … Continue reading Workshop on Local Algorithms

By shacharlovett

August 16-18, 2026 Boston University, Boston, USA https://www.local-algorithms.com/WOLA2026/ Local algorithms, that is, algorithms that compute and make decisions on parts of the output considering only a portion of the input, have been studied in a number of areas in theoretical computer science and mathematics. Some of these areas include sublinear-time algorithms, distributed algorithms, inference in … Continue reading Workshop on Local Algorithms

By shacharlovett

Friday, June 12 2026, 01:44

Extended Frege proofs, circuits and rewriting

from arXiv: Computational Complexity

Authors: Jan Krajicek

Inspired by a statement about Extended Frege proof systems by Jain and Jin (FOCS 2022) we prove that: - there is a p-time binary relation $\approx$ between circuits that implies their logical equivalence, - the relation $\approx$ implies that each of the two circuits can be rewritten into the other one by possibly deleting some gates and adding at most seven new gates, - if the equivalence $C \equiv D$ has a size $s$ proof in an Extended Frege or a Circuit Frege proof system then there is a chain of circuits $E_i$ $$ C = E_0 \approx \dots \approx E_t = D $$ with $t \le s^{O(1)}$.

Authors: Jan Krajicek

Inspired by a statement about Extended Frege proof systems by Jain and Jin (FOCS 2022) we prove that: - there is a p-time binary relation $\approx$ between circuits that implies their logical equivalence, - the relation $\approx$ implies that each of the two circuits can be rewritten into the other one by possibly deleting some gates and adding at most seven new gates, - if the equivalence $C \equiv D$ has a size $s$ proof in an Extended Frege or a Circuit Frege proof system then there is a chain of circuits $E_i$ $$ C = E_0 \approx \dots \approx E_t = D $$ with $t \le s^{O(1)}$.

Friday, June 12 2026, 00:00

Token Complexity Theory for AI-Augmented Computing

from arXiv: Computational Complexity

Authors: Jie Wang

AI-augmented computing delegates natural language queries, code generation requests, and other open-ended tasks to a cluster of AI models that processes queries and generates responses. This paradigm introduces a resource dimension that neither classical time nor space complexity captures: the cost of sending queries to and receiving responses from such a cluster. We introduce token complexity, a formal resource measure defined as the minimum expected token cost to achieve a specified level of output quality on a task, and develop a taxonomy classifying AI systems by the strength of their probabilistic properties. We develop token complexity within the framework of AI-Oracle Turing machines, in which a probabilistic Turing machine interacts with a stochastic oracle via dedicated query and response tapes. We prove basic theorems establishing that token complexity behaves as expected: monotonicity (higher quality costs more tokens), convexity (quality improvements become progressively more expensive), price sensitivity (small price changes produce bounded cost changes), and price-relativity of task ordering (the token complexity ordering of tasks can reverse depending on the query-to-response cost ratio). We prove that the complexity frontier, defined as the set of all feasible resource bounds in tokens, time, and space, is non-empty, upward-closed, and convex.

Authors: Jie Wang

AI-augmented computing delegates natural language queries, code generation requests, and other open-ended tasks to a cluster of AI models that processes queries and generates responses. This paradigm introduces a resource dimension that neither classical time nor space complexity captures: the cost of sending queries to and receiving responses from such a cluster. We introduce token complexity, a formal resource measure defined as the minimum expected token cost to achieve a specified level of output quality on a task, and develop a taxonomy classifying AI systems by the strength of their probabilistic properties. We develop token complexity within the framework of AI-Oracle Turing machines, in which a probabilistic Turing machine interacts with a stochastic oracle via dedicated query and response tapes. We prove basic theorems establishing that token complexity behaves as expected: monotonicity (higher quality costs more tokens), convexity (quality improvements become progressively more expensive), price sensitivity (small price changes produce bounded cost changes), and price-relativity of task ordering (the token complexity ordering of tasks can reverse depending on the query-to-response cost ratio). We prove that the complexity frontier, defined as the set of all feasible resource bounds in tokens, time, and space, is non-empty, upward-closed, and convex.

Friday, June 12 2026, 00:00

The Switching Lemma shows what the Switching Lemma cannot prove: an unconditional natural-proofs barrier

from arXiv: Computational Complexity

Authors: Bruno Loff, Suhail Sherif, Navid Talebanfard, Francesca Ugazio

Razborov and Rudich (JCSS'97) observed that all known lower-bound proofs follow a certain pattern: when showing that a function $F$ is hard, along the way the proof provides us with a distinguisher, namely, an efficient algorithm which can distinguish easy functions from random functions. They called such lower-bound proofs natural proofs. They then showed a natural-proofs barrier: under standard cryptographic assumptions, natural proofs cannot show superpolynomial lower-bounds against Boolean circuits. Along similar lines it can be shown that under a suitable cryptographic assumption, natural proofs cannot significantly improve the current state-of-the-art lower bound against constant depth circuits (AC0). The state of the art, using Håstad's Switching Lemma (SL), is $2^{n^{1/(d-1)}}$ for depth-$d$ circuits, and (conditionally) no natural proof can prove lower bounds of $2^{n^{c/d}}$ for some large constant $c$. In this paper we revisit the natural-proofs barrier from an $\textit{unconditional}$ perspective. We focus on AC0-natural proofs, i.e. proofs whose distinguishers are computable by AC0 circuits. Razborov and Rudich observed that lower bounds based on SL are AC0-natural. We show that this is true for most known lower-bound techniques against constant-depth circuits. We then establish an unconditional barrier for such proofs. By localizing the Trevisan--Xue pseudorandom generator, we are able to show that no AC0-natural proof can prove a lower bound greater than $2^{n^{7/(d-5)}}$ against depth-$d$ circuits. This is in the same quantitative regime as the SL frontier which instead has $1/(d-1)$ in the power of $n$. The proof has a striking self-referential aspect: the proof of security of the Trevisan--Xue generator crucially relies on SL, and so SL has been used to show that AC0-natural proofs, such as SL itself, cannot prove AC0 lower bounds better than that of SL.

Authors: Bruno Loff, Suhail Sherif, Navid Talebanfard, Francesca Ugazio

Razborov and Rudich (JCSS'97) observed that all known lower-bound proofs follow a certain pattern: when showing that a function $F$ is hard, along the way the proof provides us with a distinguisher, namely, an efficient algorithm which can distinguish easy functions from random functions. They called such lower-bound proofs natural proofs. They then showed a natural-proofs barrier: under standard cryptographic assumptions, natural proofs cannot show superpolynomial lower-bounds against Boolean circuits. Along similar lines it can be shown that under a suitable cryptographic assumption, natural proofs cannot significantly improve the current state-of-the-art lower bound against constant depth circuits (AC0). The state of the art, using Håstad's Switching Lemma (SL), is $2^{n^{1/(d-1)}}$ for depth-$d$ circuits, and (conditionally) no natural proof can prove lower bounds of $2^{n^{c/d}}$ for some large constant $c$. In this paper we revisit the natural-proofs barrier from an $\textit{unconditional}$ perspective. We focus on AC0-natural proofs, i.e. proofs whose distinguishers are computable by AC0 circuits. Razborov and Rudich observed that lower bounds based on SL are AC0-natural. We show that this is true for most known lower-bound techniques against constant-depth circuits. We then establish an unconditional barrier for such proofs. By localizing the Trevisan--Xue pseudorandom generator, we are able to show that no AC0-natural proof can prove a lower bound greater than $2^{n^{7/(d-5)}}$ against depth-$d$ circuits. This is in the same quantitative regime as the SL frontier which instead has $1/(d-1)$ in the power of $n$. The proof has a striking self-referential aspect: the proof of security of the Trevisan--Xue generator crucially relies on SL, and so SL has been used to show that AC0-natural proofs, such as SL itself, cannot prove AC0 lower bounds better than that of SL.

Friday, June 12 2026, 00:00