Last Update

OPML feed of all feeds.

Subscribe to the Atom feed, RSS feed to stay up to date.

Thank you to arXiv for use of its open access interoperability.

Note: the date of arXiv entries announced right after publication holidays might incorrectly show up as the date of the publication holiday itself. This is due to our ad hoc method of inferring announcement dates, which are not returned by the arXiv API.

Powered by Pluto.

Source on GitHub.

Maintained by Nima Anari, Arnab Bhattacharyya, Gautam Kamath.

Theory of Computing Report

Wednesday, September 16

Towards Optimal Prefix-Free Graph Construction: NP-Hardness and Structural Insights

from arXiv: Computational Complexity

Authors: Andrej Baláž, Alexandru Popa

Prefix-free parsing provides an efficient way to construct compressed representations of large and repetitive pangenomes and naturally induces a graph representation known as a prefix-free graph. In this work, we initiate a theoretical study of the problem of constructing prefix-free graphs of minimum size, where the size accounts for both the total length of distinct segment labels and the paths representing the input sequences. We show that selecting an optimal set of trigger words is NP-hard, already when triggers consist of single characters. Using a synchronized-code reduction, we extend this hardness result to every fixed trigger length and further show that the problem remains NP-hard over an alphabet of size three. We then establish a structural connection between prefix-free graphs and de Bruijn graphs. In particular, we show that every compacted de Bruijn graph can be realized as a prefix-free graph and derive a hierarchy relating the sizes of minimum pangenomic graphs, minimum prefix-free graphs, compacted de Bruijn graphs, and de Bruijn graphs. Finally, we give an exact fixed-parameter algorithm running in $O(2^q n)$ time, where $q$ is the number of distinct candidate trigger words and $n$ is the total pangenome length. Our results characterize both the computational limitations and the structural properties of optimizing prefix-free graph representations and provide a theoretical foundation for the design of compact graph representations of repetitive pangenomic data.

Authors: Andrej Baláž, Alexandru Popa

Prefix-free parsing provides an efficient way to construct compressed representations of large and repetitive pangenomes and naturally induces a graph representation known as a prefix-free graph. In this work, we initiate a theoretical study of the problem of constructing prefix-free graphs of minimum size, where the size accounts for both the total length of distinct segment labels and the paths representing the input sequences. We show that selecting an optimal set of trigger words is NP-hard, already when triggers consist of single characters. Using a synchronized-code reduction, we extend this hardness result to every fixed trigger length and further show that the problem remains NP-hard over an alphabet of size three. We then establish a structural connection between prefix-free graphs and de Bruijn graphs. In particular, we show that every compacted de Bruijn graph can be realized as a prefix-free graph and derive a hierarchy relating the sizes of minimum pangenomic graphs, minimum prefix-free graphs, compacted de Bruijn graphs, and de Bruijn graphs. Finally, we give an exact fixed-parameter algorithm running in $O(2^q n)$ time, where $q$ is the number of distinct candidate trigger words and $n$ is the total pangenome length. Our results characterize both the computational limitations and the structural properties of optimizing prefix-free graph representations and provide a theoretical foundation for the design of compact graph representations of repetitive pangenomic data.

Concise tensors with maximal symmetries

from arXiv: Computational Complexity

Authors: Annika Holtrup, Jeroen Zuiddam

Conner, Gesmundo, Landsberg and Ventura (2019) determined the largest stabilizer dimension of concise $n\times n \times n$ tensors that are binding, and they determined the corresponding maximizing tensors to be the null algebra tensors. They left as an open problem to extend this to all concise $n \times n \times n$ tensors (i.e. dropping binding). We solve this problem: We prove that the largest stabilizer dimension of concise $n\times n\times n$ tensors is $n^2 + 1$ and the maximizers are the null algebra tensors (as in the binding case) and the skew symmetric tensor $e_1 \wedge e_2 \wedge e_3$. As part of our approach we obtain upper bounds on the stabilizer dimension of matrix tuples under left-right action (generalized Kronecker quiver representations), which we think are of independent interest.

Authors: Annika Holtrup, Jeroen Zuiddam

Conner, Gesmundo, Landsberg and Ventura (2019) determined the largest stabilizer dimension of concise $n\times n \times n$ tensors that are binding, and they determined the corresponding maximizing tensors to be the null algebra tensors. They left as an open problem to extend this to all concise $n \times n \times n$ tensors (i.e. dropping binding). We solve this problem: We prove that the largest stabilizer dimension of concise $n\times n\times n$ tensors is $n^2 + 1$ and the maximizers are the null algebra tensors (as in the binding case) and the skew symmetric tensor $e_1 \wedge e_2 \wedge e_3$. As part of our approach we obtain upper bounds on the stabilizer dimension of matrix tuples under left-right action (generalized Kronecker quiver representations), which we think are of independent interest.

Tight Lower Bounds for Algebraic Communication and Applications

from arXiv: Computational Complexity

Authors: Manon Blanc, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Meena Mahajan

Communication complexity studies how much information must be exchanged to solve a problem whose input is split among several parties. The classical setting deals with Boolean inputs split between two parties. We study an algebraic variant, where the inputs are vectors over a field $\mathbb{F} \in \{\mathbb{R}, \mathbb{C}\}$. Alice and Bob have inputs $X\in \mathbb{F}^n$ and $Y\in \mathbb{F}^n$, respectively. We consider two kinds of tasks: the polynomial evaluation problem (compute the value of a polynomial $g\in \mathbb{F}[X,Y]$), and the set-recognition problem (decide whether (X,Y) is in $S$, for $S\subseteq \mathbb{F}^{n} \times \mathbb{F}^n$). In both settings, Alice and Bob send evaluations of polynomials depending only on their own inputs. In the set-recognition problem, a referee receives the messages and may apply polynomial tests to the messages received so far; the outcomes of these tests determine acceptance or rejection. The protocols may be deterministic or probabilistic. We study: - Upper bounds and reductions: We give non-trivial upper bounds for a range of natural polynomial evaluation and set-recognition problems and prove reductions between different problems, which help organize the landscape of the model. - A lower bound framework and tight lower bounds: Our main technical contribution is a general framework for proving lower bounds for algebraic set-recognition problems. We prove several probabilistic lower bounds for natural problems, giving tight or near-tight characterizations of their algebraic communication. - Applications of the framework: Finally, we give two applications of our framework: proving lower bounds for a class of left-to-right algebraic algorithms (algebraic scanners) and a more general algebraic computational setting inspired by the BSS model.

Authors: Manon Blanc, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Meena Mahajan

Communication complexity studies how much information must be exchanged to solve a problem whose input is split among several parties. The classical setting deals with Boolean inputs split between two parties. We study an algebraic variant, where the inputs are vectors over a field $\mathbb{F} \in \{\mathbb{R}, \mathbb{C}\}$. Alice and Bob have inputs $X\in \mathbb{F}^n$ and $Y\in \mathbb{F}^n$, respectively. We consider two kinds of tasks: the polynomial evaluation problem (compute the value of a polynomial $g\in \mathbb{F}[X,Y]$), and the set-recognition problem (decide whether (X,Y) is in $S$, for $S\subseteq \mathbb{F}^{n} \times \mathbb{F}^n$). In both settings, Alice and Bob send evaluations of polynomials depending only on their own inputs. In the set-recognition problem, a referee receives the messages and may apply polynomial tests to the messages received so far; the outcomes of these tests determine acceptance or rejection. The protocols may be deterministic or probabilistic. We study: - Upper bounds and reductions: We give non-trivial upper bounds for a range of natural polynomial evaluation and set-recognition problems and prove reductions between different problems, which help organize the landscape of the model. - A lower bound framework and tight lower bounds: Our main technical contribution is a general framework for proving lower bounds for algebraic set-recognition problems. We prove several probabilistic lower bounds for natural problems, giving tight or near-tight characterizations of their algebraic communication. - Applications of the framework: Finally, we give two applications of our framework: proving lower bounds for a class of left-to-right algebraic algorithms (algebraic scanners) and a more general algebraic computational setting inspired by the BSS model.

Improved Separations between Quantum and Classical Communication Complexity of Total Functions

from arXiv: Computational Complexity

Authors: François Le Gall

We refine Gavinsky's framework (arXiv:2608.18784) for exponential separations between quantum and randomized communication complexity of total functions and obtain larger separations: polylogarithmic quantum communication versus $\tildeΩ(\sqrt n)$ randomized communication with two quantum messages, and versus $Ω(n^{1-\varepsilon})$ for every fixed $0<\varepsilon<1$ with more quantum messages.

Authors: François Le Gall

We refine Gavinsky's framework (arXiv:2608.18784) for exponential separations between quantum and randomized communication complexity of total functions and obtain larger separations: polylogarithmic quantum communication versus $\tildeΩ(\sqrt n)$ randomized communication with two quantum messages, and versus $Ω(n^{1-\varepsilon})$ for every fixed $0<\varepsilon<1$ with more quantum messages.

Euclidean SVP is NP-hard for Cyclic Lattices

from arXiv: Computational Complexity

Authors: Daqing Wan

We prove that exact Euclidean SVP is NP-hard under deterministic polynomial-time many-one reductions for full-rank cyclic integer lattices, equivalently full-rank ideals of $R_N:=\mathbb{Z}[X]/(X^N-1)$ in the coefficient norm. Hardness holds with $N=q-1$ for a varying odd prime $q$. As an application, we prove the same hardness for the algebraic class of NTRU-form lattices $\{(x,z)\in R_N^2:Hx\equiv z\pmod{QR_N}\}$, where $H,Q$ are unrestricted inputs. The decision problems are NP-complete, and the exact search problems are NP-hard under polynomial-time Turing reductions. No hardness claim is made for cryptographic NTRU parameter subclasses or key-generation distributions.

Authors: Daqing Wan

We prove that exact Euclidean SVP is NP-hard under deterministic polynomial-time many-one reductions for full-rank cyclic integer lattices, equivalently full-rank ideals of $R_N:=\mathbb{Z}[X]/(X^N-1)$ in the coefficient norm. Hardness holds with $N=q-1$ for a varying odd prime $q$. As an application, we prove the same hardness for the algebraic class of NTRU-form lattices $\{(x,z)\in R_N^2:Hx\equiv z\pmod{QR_N}\}$, where $H,Q$ are unrestricted inputs. The decision problems are NP-complete, and the exact search problems are NP-hard under polynomial-time Turing reductions. No hardness claim is made for cryptographic NTRU parameter subclasses or key-generation distributions.

A Resolution of Friedgut's Conjecture on Influential Coalitions

from arXiv: Computational Complexity

Authors: Eshan Chattopadhyay, Mohit Gurumukhani

We prove that, for every constant $\varepsilon>0$ and every function $f:Σ^n\to\{0, 1\}$, there is a coalition of $O(n/\sqrt{\log n})$ coordinates and a target output $b\in\{0, 1\}$ such that, after the remaining coordinates are sampled uniformly and independently, the coalition can choose its values to make the output equal to $b$ with probability at least $1-\varepsilon$. The bound is independent of the alphabet size and also holds for monotone Boolean functions on $[0,1]^n$, resolving a conjecture of Friedgut (Combinatorics, Probability and Computing, 2004). Unlike the Boolean cube setting, where Kahn, Kalai, and Linial (FOCS, 1988) give a coalition bound of $O(n/\log n)$, no sublinear bound independent of the alphabet size was previously known. In collective coin flipping, our result gives the first sublinear bound on the number of bad players needed to force a fixed output with probability at least $1-\varepsilon$ in any one-round protocol with independent uniform messages, regardless of the message length. A key ingredient in our proof is an encoding that lets us relate the influence of a function on a product space to the $p$-biased influence of the encoded function. We then rely on a structure theorem of Hatami (Annals of Mathematics, 2012) for functions with small $p$-biased influence to bias the encoded function.

Authors: Eshan Chattopadhyay, Mohit Gurumukhani

We prove that, for every constant $\varepsilon>0$ and every function $f:Σ^n\to\{0, 1\}$, there is a coalition of $O(n/\sqrt{\log n})$ coordinates and a target output $b\in\{0, 1\}$ such that, after the remaining coordinates are sampled uniformly and independently, the coalition can choose its values to make the output equal to $b$ with probability at least $1-\varepsilon$. The bound is independent of the alphabet size and also holds for monotone Boolean functions on $[0,1]^n$, resolving a conjecture of Friedgut (Combinatorics, Probability and Computing, 2004). Unlike the Boolean cube setting, where Kahn, Kalai, and Linial (FOCS, 1988) give a coalition bound of $O(n/\log n)$, no sublinear bound independent of the alphabet size was previously known. In collective coin flipping, our result gives the first sublinear bound on the number of bad players needed to force a fixed output with probability at least $1-\varepsilon$ in any one-round protocol with independent uniform messages, regardless of the message length. A key ingredient in our proof is an encoding that lets us relate the influence of a function on a product space to the $p$-biased influence of the encoded function. We then rely on a structure theorem of Hatami (Annals of Mathematics, 2012) for functions with small $p$-biased influence to bias the encoded function.

On testing the incentive compatibility of single-parameter allocation mechanisms

from arXiv: Data Structures and Algorithms

Authors: Jason Milionis, William Pires

This paper is the first work at the intersection of game theory and property testing, giving algorithms and lower bounds for efficiently testing whether an allocation mechanism is incentive compatible (IC). We propose distinguishing whether a mechanism is $ε$-far from being IC, i.e., when it observes many monotonicity "violations." Conceptually, inspired by the literature on Boolean function monotonicity testing, we construct a tester for discrete single-parameter allocation rules. Technically, our work is the first to consider monotonicity testing of vector-valued functions on the hypergrid. We give a $\tilde{O}(n/ε)$-query algorithm to test whether a function (representing n-player allocation mechanisms) is coordinate-wise monotone versus $ε$-far from it. We also show a matching lower bound: the class of coordinate-wise monotone vector-valued functions on a Boolean hypercube or hypergrid requires $\tildeΩ(n/ε)$ queries to test whether it is $ε$-far from monotonicity, and this holds even if the tester is two-sided and allowed to make adaptive queries. Finally, we extend our upper bound to and give a tester of the same query complexity for pricing functions of allocation mechanisms. This requires overcoming the technical challenge that the path in function space to the closest IC mechanism may involve interdependent changes to both the price and the allocation rule.

Authors: Jason Milionis, William Pires

This paper is the first work at the intersection of game theory and property testing, giving algorithms and lower bounds for efficiently testing whether an allocation mechanism is incentive compatible (IC). We propose distinguishing whether a mechanism is $ε$-far from being IC, i.e., when it observes many monotonicity "violations." Conceptually, inspired by the literature on Boolean function monotonicity testing, we construct a tester for discrete single-parameter allocation rules. Technically, our work is the first to consider monotonicity testing of vector-valued functions on the hypergrid. We give a $\tilde{O}(n/ε)$-query algorithm to test whether a function (representing n-player allocation mechanisms) is coordinate-wise monotone versus $ε$-far from it. We also show a matching lower bound: the class of coordinate-wise monotone vector-valued functions on a Boolean hypercube or hypergrid requires $\tildeΩ(n/ε)$ queries to test whether it is $ε$-far from monotonicity, and this holds even if the tester is two-sided and allowed to make adaptive queries. Finally, we extend our upper bound to and give a tester of the same query complexity for pricing functions of allocation mechanisms. This requires overcoming the technical challenge that the path in function space to the closest IC mechanism may involve interdependent changes to both the price and the allocation rule.

List Decoding, Linear Hashing, and Furstenberg over $\mathbb{F}_q$

from arXiv: Data Structures and Algorithms

Authors: Vinayak M. Kumar, Geoffrey Mon

We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field $\mathbb{F}_q$. 1. Random linear codes over $\mathbb{F}_q$ with rate $1 - H_q(p) - ε$ are $(p, O(q H_q(p)/ε))$-list decodable with high probability for all values of $p, q, ε$, including the high error regime. This nearly matches the list size lower bound of $H_q(p)/ε$ due to Guruswami, Li, Mosheiff, Resch, Silas, and Wootters [IEEE Trans. Inf. Theory 2022]. Our bound is the first uniform improvement for $q > 2$ since Guruswami, Håstad, and Kopparty [STOC 2010]. 2. Linear hash functions over $\mathbb{F}_q$ hashing $n$ balls to $n$ bins achieve maximum load $O(q \ln \ln q / {\ln q}) \cdot \ln n / {\ln \ln n}$, both in expectation and with probability $1-o(1)$. This nearly matches the lower bound of $\ln n / {\ln \ln n}$. Previously, only a polylogarithmic upper bound was known for $q > 2$, due to Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos [J. ACM 1999]. We reduce list decodability and linear hashing to strong Furstenberg set lower bounds, which we prove using a new polynomial method of multiplicity gaps. While previous polynomial methods analyze a set $S$ by studying polynomials that vanish on it, we consider polynomials that vanish everywhere, but with higher multiplicity inside $S$ than outside.

Authors: Vinayak M. Kumar, Geoffrey Mon

We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field $\mathbb{F}_q$. 1. Random linear codes over $\mathbb{F}_q$ with rate $1 - H_q(p) - ε$ are $(p, O(q H_q(p)/ε))$-list decodable with high probability for all values of $p, q, ε$, including the high error regime. This nearly matches the list size lower bound of $H_q(p)/ε$ due to Guruswami, Li, Mosheiff, Resch, Silas, and Wootters [IEEE Trans. Inf. Theory 2022]. Our bound is the first uniform improvement for $q > 2$ since Guruswami, Håstad, and Kopparty [STOC 2010]. 2. Linear hash functions over $\mathbb{F}_q$ hashing $n$ balls to $n$ bins achieve maximum load $O(q \ln \ln q / {\ln q}) \cdot \ln n / {\ln \ln n}$, both in expectation and with probability $1-o(1)$. This nearly matches the lower bound of $\ln n / {\ln \ln n}$. Previously, only a polylogarithmic upper bound was known for $q > 2$, due to Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos [J. ACM 1999]. We reduce list decodability and linear hashing to strong Furstenberg set lower bounds, which we prove using a new polynomial method of multiplicity gaps. While previous polynomial methods analyze a set $S$ by studying polynomials that vanish on it, we consider polynomials that vanish everywhere, but with higher multiplicity inside $S$ than outside.

Stuffed IBLTs: Optimal Linear Multiset Sketches

from arXiv: Data Structures and Algorithms

Authors: Jonas Klausen, Rasmus Pagh, Stefan Walzer

A \emph{linear sketch} is a randomized linear mapping of a vector $v$ to a lower dimensional sketch vector, designed to preserve relevant information about $v$. We consider sketches of vectors $v \in Z^u$ (for $u \in N$), designed for exact recovery of $v$ from its sketch. Concretely, our \emph{Stuffed IBLT} is a linear sketch configured with a capacity $n \in N$ and a multiplicity limit $L \in N$ and will recover $v$ with high probability whenever $||v||_0 \leq n$ and $||v||_\infty \leq L$. The sketch can be maintained efficiently under unrestricted updates to $v$, i.e., $v$ is not subject to any constraints in between decoding requests. This makes the sketch useful for streaming algorithms and for solving the (multi)set reconciliation problem. For any positive constants $c$, $ε$, and for large enough $n$ and $u \geq n^{1+Ω(1)}$, the space usage of a Stuffed IBLT is within a factor $1+ε$ from the information-theoretic optimum while allowing updates in constant time, and decoding in time $O(n)$ with failure probability $n^{-c}$. This improves the space/time/error probability trade-off over all prior constructions with similar functionality, including the Invertible Bloom Lookup Table (IBLT). The performance of the Stuffed IBLT is essentially the best we could hope for, up to the dependence on $c$ and $ε$. We make the dependence on these parameters explicit, and further show a lower bound demonstrating that the dependence on $c$ is optimal within the class of peeling-based approaches. Our improvement comes from a careful combination of Walzer's spatial coupling technique (SODA '21), the purity heuristic of Houen, Pagh, and Walzer (SOSA '23), and backyarding (Belazzougui, Kucherov, and Walzer, ESA '24; Fleischhacker, Green Larsen, Obremski, and Simkin, ICALP '24), allowing us to eliminate bottlenecks of past approaches.

Authors: Jonas Klausen, Rasmus Pagh, Stefan Walzer

A \emph{linear sketch} is a randomized linear mapping of a vector $v$ to a lower dimensional sketch vector, designed to preserve relevant information about $v$. We consider sketches of vectors $v \in Z^u$ (for $u \in N$), designed for exact recovery of $v$ from its sketch. Concretely, our \emph{Stuffed IBLT} is a linear sketch configured with a capacity $n \in N$ and a multiplicity limit $L \in N$ and will recover $v$ with high probability whenever $||v||_0 \leq n$ and $||v||_\infty \leq L$. The sketch can be maintained efficiently under unrestricted updates to $v$, i.e., $v$ is not subject to any constraints in between decoding requests. This makes the sketch useful for streaming algorithms and for solving the (multi)set reconciliation problem. For any positive constants $c$, $ε$, and for large enough $n$ and $u \geq n^{1+Ω(1)}$, the space usage of a Stuffed IBLT is within a factor $1+ε$ from the information-theoretic optimum while allowing updates in constant time, and decoding in time $O(n)$ with failure probability $n^{-c}$. This improves the space/time/error probability trade-off over all prior constructions with similar functionality, including the Invertible Bloom Lookup Table (IBLT). The performance of the Stuffed IBLT is essentially the best we could hope for, up to the dependence on $c$ and $ε$. We make the dependence on these parameters explicit, and further show a lower bound demonstrating that the dependence on $c$ is optimal within the class of peeling-based approaches. Our improvement comes from a careful combination of Walzer's spatial coupling technique (SODA '21), the purity heuristic of Houen, Pagh, and Walzer (SOSA '23), and backyarding (Belazzougui, Kucherov, and Walzer, ESA '24; Fleischhacker, Green Larsen, Obremski, and Simkin, ICALP '24), allowing us to eliminate bottlenecks of past approaches.

Determinant maximization subject to a partition matroid constraint via stable distributions

from arXiv: Data Structures and Algorithms

Authors: Yihang Sun, Jan Vondrak

Given vectors $v_i \in {\mathbb R}^d$, we consider the problem of choosing a set $I$ independent in a partition matroid in order to maximize the determinant $\det (\sum_{i \in I} v_i v_i^T)$. Our main result is a polynomial-time approximation algorithm that finds a solution of value $det ( \sum_{i \in I} v_{i} v_{i}^T) \geq e^{-O(d)} OPT$, where $OPT = \max_{I^*} det ( \sum_{i \in I^*} v_{i} v_{i}^T)$. For partition matroids of rank $m \leq d$, we give a similar result for approximating the $m$-dimensional volume spanned by the chosen vectors, within a factor of $e^{O(m)}$. This matches earlier known algorithms that estimate the optimal value but do not find the corresponding solution, up to a constant in the exponent. Similar to these estimation algorithms, our algorithm is based on the saddle-point relaxation proposed by Nikolov and Singh. A new ingredient is a randomized transformation based on $1/2$-stable distributions, which converts the saddle-point relaxation into a more convenient multilinear relaxation.

Authors: Yihang Sun, Jan Vondrak

Given vectors $v_i \in {\mathbb R}^d$, we consider the problem of choosing a set $I$ independent in a partition matroid in order to maximize the determinant $\det (\sum_{i \in I} v_i v_i^T)$. Our main result is a polynomial-time approximation algorithm that finds a solution of value $det ( \sum_{i \in I} v_{i} v_{i}^T) \geq e^{-O(d)} OPT$, where $OPT = \max_{I^*} det ( \sum_{i \in I^*} v_{i} v_{i}^T)$. For partition matroids of rank $m \leq d$, we give a similar result for approximating the $m$-dimensional volume spanned by the chosen vectors, within a factor of $e^{O(m)}$. This matches earlier known algorithms that estimate the optimal value but do not find the corresponding solution, up to a constant in the exponent. Similar to these estimation algorithms, our algorithm is based on the saddle-point relaxation proposed by Nikolov and Singh. A new ingredient is a randomized transformation based on $1/2$-stable distributions, which converts the saddle-point relaxation into a more convenient multilinear relaxation.

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering

from arXiv: Data Structures and Algorithms

Authors: Chenglin Fan, Dahoon Lee, Euiwoong Lee

We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For every fixed $\varepsilon>0$, we give a randomized polynomial-time $(2+\varepsilon)$-approximation, improving the previously best known factor of $10/3$. Our algorithm extends the cluster-LP framework for unweighted correlation clustering to pseudometric weights. The weighted setting requires controlling both the total weight of admissible pairs and the weighted error in pairwise marginals. Our spectral preclustering preserves a near-optimal solution while bounding the total admissible weight by $\operatorname{poly}(1/\varepsilon)\mathrm{OPT}$, where $\mathrm{OPT}$ is the optimal clustering cost. An aggregated Ptolemy-type inequality yields a degree-product bound and a warm start for random walks within witness clusters, allowing the construction to use walks of constant length. We sample clusters from a bounded sub-cluster relaxation using correlated rounding with a randomized stopping time. An entropy bound and the triangle inequality charge the weighted marginal error to the admissible pairs rather than to the total input weight. Repeated sampling and atom-wise coverage corrections produce an explicit feasible cluster-LP solution supported on polynomially many clusters, with value at most $(1+\varepsilon)\mathrm{OPT}$. After rescaling $\varepsilon$, factor-$2$ rounding gives the stated approximation guarantee.

Authors: Chenglin Fan, Dahoon Lee, Euiwoong Lee

We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For every fixed $\varepsilon>0$, we give a randomized polynomial-time $(2+\varepsilon)$-approximation, improving the previously best known factor of $10/3$. Our algorithm extends the cluster-LP framework for unweighted correlation clustering to pseudometric weights. The weighted setting requires controlling both the total weight of admissible pairs and the weighted error in pairwise marginals. Our spectral preclustering preserves a near-optimal solution while bounding the total admissible weight by $\operatorname{poly}(1/\varepsilon)\mathrm{OPT}$, where $\mathrm{OPT}$ is the optimal clustering cost. An aggregated Ptolemy-type inequality yields a degree-product bound and a warm start for random walks within witness clusters, allowing the construction to use walks of constant length. We sample clusters from a bounded sub-cluster relaxation using correlated rounding with a randomized stopping time. An entropy bound and the triangle inequality charge the weighted marginal error to the admissible pairs rather than to the total input weight. Repeated sampling and atom-wise coverage corrections produce an explicit feasible cluster-LP solution supported on polynomially many clusters, with value at most $(1+\varepsilon)\mathrm{OPT}$. After rescaling $\varepsilon$, factor-$2$ rounding gives the stated approximation guarantee.

PrecPack: An Efficient Open-Source Exact Solver for Bin Packing with Generalized Precedence Constraints

from arXiv: Data Structures and Algorithms

Authors: Sunkanghong Wang, Zhengzhong Ricky You, Roberto Baldacci, Baichuan Mo, Hu Qin, Lijun Wei, Zhou Xu

Efficient resource use in packing and assembly-line applications requires decisions that jointly account for capacity and precedence constraints. The strongly NP-hard bin packing problem with generalized precedence constraints (BPP-GP) models such decisions by minimizing the number of ordered, capacitated bins required to pack weighted items, even when precedence requirements span multiple bins. Existing exact algorithms primarily focus on classical special cases, whereas general BPP-GP has been addressed only via compact integer models and heuristics, with no efficient open-source exact solver. We present PrecPack, a unified exact solver that extends branch-bound-and-remember (BBR) to arbitrary nonnegative precedence weights and naturally specializes to the classical cases. Generalized states capture restrictions that remain active across future bins, which are addressed through branching, dominance, and conflict-aware lower bounds. Root column generation uses fixed-point arithmetic to compute numerically valid dual bounds for pruning or to prove optimality. To support reuse and verification, we provide common programming and command-line interfaces, independent assignment checking, explicit termination statuses, and reproducible batch execution; the core procedures require no commercial software. In same-machine, single-threaded comparisons on classic assembly-line benchmarks, more instances are proven optimal, and average computing times are substantially reduced relative to leading source-available BBR implementations. Further comparisons with published benchmark results for bin packing with precedence constraints and BPP-GP also show that more instances were proved optimal and that reported average gaps were smaller on most benchmark sets. PrecPack is released under the MIT License at github.com/Sunkanghong-Wang/PrecPack.

Authors: Sunkanghong Wang, Zhengzhong Ricky You, Roberto Baldacci, Baichuan Mo, Hu Qin, Lijun Wei, Zhou Xu

Efficient resource use in packing and assembly-line applications requires decisions that jointly account for capacity and precedence constraints. The strongly NP-hard bin packing problem with generalized precedence constraints (BPP-GP) models such decisions by minimizing the number of ordered, capacitated bins required to pack weighted items, even when precedence requirements span multiple bins. Existing exact algorithms primarily focus on classical special cases, whereas general BPP-GP has been addressed only via compact integer models and heuristics, with no efficient open-source exact solver. We present PrecPack, a unified exact solver that extends branch-bound-and-remember (BBR) to arbitrary nonnegative precedence weights and naturally specializes to the classical cases. Generalized states capture restrictions that remain active across future bins, which are addressed through branching, dominance, and conflict-aware lower bounds. Root column generation uses fixed-point arithmetic to compute numerically valid dual bounds for pruning or to prove optimality. To support reuse and verification, we provide common programming and command-line interfaces, independent assignment checking, explicit termination statuses, and reproducible batch execution; the core procedures require no commercial software. In same-machine, single-threaded comparisons on classic assembly-line benchmarks, more instances are proven optimal, and average computing times are substantially reduced relative to leading source-available BBR implementations. Further comparisons with published benchmark results for bin packing with precedence constraints and BPP-GP also show that more instances were proved optimal and that reported average gaps were smaller on most benchmark sets. PrecPack is released under the MIT License at https://github.com/Sunkanghong-Wang/PrecPack.

The Classical Weisfeiler-Leman Algorithm Stabilizes in $O(n)$ Rounds

from arXiv: Data Structures and Algorithms

Authors: Simon Döring, Daniel Neuen

The classical Weisfeiler-Leman algorithm (also known as the $2$-dimensional Weisfeiler-Leman algorithm) is a simple combinatorial algorithm that was originally designed as a heuristic for the graph isomorphism problem. However, it has also numerous connections to other areas such as algebraic graph theory, logics, proof complexity, combinatorial optimization and machine learning. We prove that the classical Weisfeiler-Leman algorithm terminates after $5(n-1)$ iterations. This improves over the previous best upper bound of $O(n \log n)$ by Lichter, Ponomarenko and Schweitzer [LICS 2019], and asymptotically matches the known lower bound of $Ω(n)$ by Fürer [ICALP 2001]. Additionally, building on our results for the $2$-dimensional case, we obtain an improved upper bound of $O(n^{k-1}/(k-2)! + n^{k-2})$ on the number of iterations performed by the $k$-dimensional Weisfeiler-Leman algorithm, for every $k \geq 3$. Our arguments actually hold for a larger class of sequences of colorings of $k$-tuples; in this larger class our upper bounds are essentially tight for all $k \geq 3$.

Authors: Simon Döring, Daniel Neuen

The classical Weisfeiler-Leman algorithm (also known as the $2$-dimensional Weisfeiler-Leman algorithm) is a simple combinatorial algorithm that was originally designed as a heuristic for the graph isomorphism problem. However, it has also numerous connections to other areas such as algebraic graph theory, logics, proof complexity, combinatorial optimization and machine learning. We prove that the classical Weisfeiler-Leman algorithm terminates after $5(n-1)$ iterations. This improves over the previous best upper bound of $O(n \log n)$ by Lichter, Ponomarenko and Schweitzer [LICS 2019], and asymptotically matches the known lower bound of $Ω(n)$ by Fürer [ICALP 2001]. Additionally, building on our results for the $2$-dimensional case, we obtain an improved upper bound of $O(n^{k-1}/(k-2)! + n^{k-2})$ on the number of iterations performed by the $k$-dimensional Weisfeiler-Leman algorithm, for every $k \geq 3$. Our arguments actually hold for a larger class of sequences of colorings of $k$-tuples; in this larger class our upper bounds are essentially tight for all $k \geq 3$.

Online Allocation using Few Samples

from arXiv: Data Structures and Algorithms

Authors: Matthew Faw, Sahil Singla, Yifan Wang

We study online allocation problems where $n$ requests over $m$ resources arrive in an adversarial order and must be served immediately and irrevocably. This framework captures both Online Resource Allocation, where the goal is to maximize value subject to resource budgets, and Online Load Balancing, where the goal is to minimize the makespan. We seek $(1\pmε)$-competitive algorithms in the large-budget or large-makespan regime. We consider a sampling model that generalizes the following two well-studied sampling models. In the Single-Sample Prophet Inequality ($\mathsf{SSPI}$) model, request $t$ is drawn from an unknown distribution $\mathcal{D}_t$, and the algorithm is given one independent sample from each $\mathcal{D}_t$ before the online phase. In the $p$-$\mathsf{Sample}$ model, the requests are adversarial, but a uniformly random $p$-fraction is revealed upfront as training data. Although near-optimal algorithms are known in the easier random-order model ($\mathsf{RO}$), where the requests arrive in a uniformly random order, prior algorithms for $\mathsf{SSPI}$ and $p$-$\mathsf{Sample}$ were problem-specific and incurred substantially worse dependencies on $ε$, $m$, and $n$. Our main contribution is a general framework that converts $\mathsf{RO}$ algorithms into algorithms for the $p$-$\mathsf{Preview}$ model, a model that generalizes both $\mathsf{SSPI}$ and $p$-$\mathsf{Sample}$. As consequences, we obtain near-optimal bounds for Online Resource Allocation, generalized Online Load Balancing, and online mixed packing-covering problems in these adversarial-order sampling models, significantly improving the bounds of [Ghuge, Singla, Wang (STOC'25)] and [Gupta and Molinaro (SODA'26)].

Authors: Matthew Faw, Sahil Singla, Yifan Wang

We study online allocation problems where $n$ requests over $m$ resources arrive in an adversarial order and must be served immediately and irrevocably. This framework captures both Online Resource Allocation, where the goal is to maximize value subject to resource budgets, and Online Load Balancing, where the goal is to minimize the makespan. We seek $(1\pmε)$-competitive algorithms in the large-budget or large-makespan regime. We consider a sampling model that generalizes the following two well-studied sampling models. In the Single-Sample Prophet Inequality ($\mathsf{SSPI}$) model, request $t$ is drawn from an unknown distribution $\mathcal{D}_t$, and the algorithm is given one independent sample from each $\mathcal{D}_t$ before the online phase. In the $p$-$\mathsf{Sample}$ model, the requests are adversarial, but a uniformly random $p$-fraction is revealed upfront as training data. Although near-optimal algorithms are known in the easier random-order model ($\mathsf{RO}$), where the requests arrive in a uniformly random order, prior algorithms for $\mathsf{SSPI}$ and $p$-$\mathsf{Sample}$ were problem-specific and incurred substantially worse dependencies on $ε$, $m$, and $n$. Our main contribution is a general framework that converts $\mathsf{RO}$ algorithms into algorithms for the $p$-$\mathsf{Preview}$ model, a model that generalizes both $\mathsf{SSPI}$ and $p$-$\mathsf{Sample}$. As consequences, we obtain near-optimal bounds for Online Resource Allocation, generalized Online Load Balancing, and online mixed packing-covering problems in these adversarial-order sampling models, significantly improving the bounds of [Ghuge, Singla, Wang (STOC'25)] and [Gupta and Molinaro (SODA'26)].

High Probability Streaming Lower Bounds for $F_2$ Estimation

from arXiv: Data Structures and Algorithms

Authors: William Swartworth, David P. Woodruff, Samson Zhou

Estimating the second frequency moment ($F_2$) of an underlying frequency vector is a fundamental problem in the streaming model. While recent work by Braverman and Zamir [STOC 2025] resolved the space complexity for constant failure probability in the insertion-only model, the optimal dependence on the failure parameter $δ$ remained open. We close this gap by proving a tight high-probability lower bound of $Ω\left(\frac{1}{\varepsilon^2}\log\frac{1}δ\,\log\frac{\varepsilon\sqrt{n}}{\log(1/δ)}\right)$ for $(1\pm\varepsilon)$-approximate $F_2$ estimation. The key challenge is the failure of prior multi-scale direct sum arguments under noise sensitivity. We introduce a noise-robust communication primitive, Exam Mostly Set Disjointness, and prove an $Ω\left(\frac{m}{t}\log\frac{1}δ\right)$ one-way lower bound. Embedding this into a multi-scale reduction yields the correct $\log(1/δ)$ dependence. We also give two complementary algorithms under natural structure assumptions. For streams with frequency bound $B$, we design a subsampling method using continuous $F_0$ tracking that replaces a $\log(n)$ factor with $\text{polylog}(B)$. For $k$-sparse streams, we develop a two-stage sketch using approximate Morris counters, replacing $\log n$ with $\log k$ and achieving a further $\log\log m$ dependence on stream length.

Authors: William Swartworth, David P. Woodruff, Samson Zhou

Estimating the second frequency moment ($F_2$) of an underlying frequency vector is a fundamental problem in the streaming model. While recent work by Braverman and Zamir [STOC 2025] resolved the space complexity for constant failure probability in the insertion-only model, the optimal dependence on the failure parameter $δ$ remained open. We close this gap by proving a tight high-probability lower bound of $Ω\left(\frac{1}{\varepsilon^2}\log\frac{1}δ\,\log\frac{\varepsilon\sqrt{n}}{\log(1/δ)}\right)$ for $(1\pm\varepsilon)$-approximate $F_2$ estimation. The key challenge is the failure of prior multi-scale direct sum arguments under noise sensitivity. We introduce a noise-robust communication primitive, Exam Mostly Set Disjointness, and prove an $Ω\left(\frac{m}{t}\log\frac{1}δ\right)$ one-way lower bound. Embedding this into a multi-scale reduction yields the correct $\log(1/δ)$ dependence. We also give two complementary algorithms under natural structure assumptions. For streams with frequency bound $B$, we design a subsampling method using continuous $F_0$ tracking that replaces a $\log(n)$ factor with $\text{polylog}(B)$. For $k$-sparse streams, we develop a two-stage sketch using approximate Morris counters, replacing $\log n$ with $\log k$ and achieving a further $\log\log m$ dependence on stream length.

Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer

from arXiv: Data Structures and Algorithms

Authors: Ekene Ezeunala, Haotian Jiang

We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices $H_1,\dots,H_N$ of rank at most one, finds signs $s\in\{\pm1\}^N$ with $\|\sum_i s_i H_i\|\le 13\|\sum_i H_i^2\|^{1/2}$. As a corollary, for vectors $v_i$ with $\sum_i v_iv_i^*=I$ and $\|v_i\|^2\leδ$, the signs yield a partition $[N] = S_1 \cup S_2$ such that each part satisfies $\|\sum_{i \in S_j} v_i v_i^* - \frac{I}{2}\| \leq \frac{13}{2}\sqrtδ$ for $j = 1,2$. This gives a deterministic polynomial-time algorithm for the Kadison--Singer problem, in Weaver's equivalent discrepancy-theoretic $\mathsf{KS}_2$ formulation, with a universal constant.

Authors: Ekene Ezeunala, Haotian Jiang

We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices $H_1,\dots,H_N$ of rank at most one, finds signs $s\in\{\pm1\}^N$ with $\|\sum_i s_i H_i\|\le 13\|\sum_i H_i^2\|^{1/2}$. As a corollary, for vectors $v_i$ with $\sum_i v_iv_i^*=I$ and $\|v_i\|^2\leδ$, the signs yield a partition $[N] = S_1 \cup S_2$ such that each part satisfies $\|\sum_{i \in S_j} v_i v_i^* - \frac{I}{2}\| \leq \frac{13}{2}\sqrtδ$ for $j = 1,2$. This gives a deterministic polynomial-time algorithm for the Kadison--Singer problem, in Weaver's equivalent discrepancy-theoretic $\mathsf{KS}_2$ formulation, with a universal constant.

High-Multiplicity Bin Packing is FPT

from arXiv: Data Structures and Algorithms

Authors: Tomohiro Koana, Soh Kumabe

Bin packing asks whether a collection of items can be packed into at most a given number of bins of a given capacity. We consider the high-multiplicity setting with $d$ distinct item sizes, in which both the item sizes and the number of items of each size are encoded in binary. Goemans and Rothvos (JACM 2020) gave an XP algorithm parameterized by $d$. Whether this problem is fixed-parameter tractable (FPT) in $d$ has remained a central open problem. We resolve this question by giving a deterministic $O^*(2^{d^{O(d)}})$-time algorithm. We formulate bin packing as an integer linear program (ILP) with at most $(d+1)d^d$ variables. A bin configuration records the number of items of each type in one bin. We partition these configurations by their coordinate remainders modulo $d$. For each class, we use one variable for the bin count and $d$ variables for the total item counts. The convex hull of each class has the integer decomposition property, which guarantees that every feasible ILP solution corresponds to a packing.

Authors: Tomohiro Koana, Soh Kumabe

Bin packing asks whether a collection of items can be packed into at most a given number of bins of a given capacity. We consider the high-multiplicity setting with $d$ distinct item sizes, in which both the item sizes and the number of items of each size are encoded in binary. Goemans and Rothvos (JACM 2020) gave an XP algorithm parameterized by $d$. Whether this problem is fixed-parameter tractable (FPT) in $d$ has remained a central open problem. We resolve this question by giving a deterministic $O^*(2^{d^{O(d)}})$-time algorithm. We formulate bin packing as an integer linear program (ILP) with at most $(d+1)d^d$ variables. A bin configuration records the number of items of each type in one bin. We partition these configurations by their coordinate remainders modulo $d$. For each class, we use one variable for the bin count and $d$ variables for the total item counts. The convex hull of each class has the integer decomposition property, which guarantees that every feasible ILP solution corresponds to a packing.

Improved Regular Expression Matching with Simple Backreferences

from arXiv: Data Structures and Algorithms

Authors: Philip Bille, Inge Li Gørtz, Rikke Schjeldrup Jessen

A regular expression with backreferences (rewb) specifies a set of strings formed by characters combined with concatenation, union, star operators, and backreferences. A backreference consists of a capturing group $(\cdot)_i$ and a reference $\backslash i$. The substring matched by the reference must match the substring matched by the corresponding capturing group. Given a rewb $R$ and a string $Q$, the rewb matching problem is to decide whether $Q$ is one of the strings specified by $R$. In full generality, rewb matching is NP-complete, but efficient solutions exist for various subclasses. In the paper, we focus on rewb containing a single capturing group and $k$ references. For this class, Uezato~[CPM 2026] gave an $O((k n^2 m^2)$ time and $O(n^2m^2)$ space algorithm, where $m$ is the length of the regular expression $R$ and $n$ is the length of the string $Q$. For the special case of $k=1$, Nogami and Terauchi~[MFCS 2025] gave an $O(n^2m^2)$ time and $O(n+ m^2)$ space algorithm. On the other hand, Nogami, Nakamura, and Terauchi~[arXiv 2026] gave a conditional lower bound, showing that we cannot solve the problem in $O(n^{2-ε} \mathrm{poly}(m))$ for any $ε> 0$ assuming the orthogonal vector hypothesis. Our main result is a new algorithm that runs in $O(n^2m)$ time and uses $O(nm)$ space. This improves the above results (by a factor of $km$ and $m$, respectively) and the former's space bound (by a factor of $nm$). We also show how to extend our algorithm to handle a slightly more general class of ordered and single-nested rewbs.

Authors: Philip Bille, Inge Li Gørtz, Rikke Schjeldrup Jessen

A regular expression with backreferences (rewb) specifies a set of strings formed by characters combined with concatenation, union, star operators, and backreferences. A backreference consists of a capturing group $(\cdot)_i$ and a reference $\backslash i$. The substring matched by the reference must match the substring matched by the corresponding capturing group. Given a rewb $R$ and a string $Q$, the rewb matching problem is to decide whether $Q$ is one of the strings specified by $R$. In full generality, rewb matching is NP-complete, but efficient solutions exist for various subclasses. In the paper, we focus on rewb containing a single capturing group and $k$ references. For this class, Uezato~[CPM 2026] gave an $O((k n^2 m^2)$ time and $O(n^2m^2)$ space algorithm, where $m$ is the length of the regular expression $R$ and $n$ is the length of the string $Q$. For the special case of $k=1$, Nogami and Terauchi~[MFCS 2025] gave an $O(n^2m^2)$ time and $O(n+ m^2)$ space algorithm. On the other hand, Nogami, Nakamura, and Terauchi~[arXiv 2026] gave a conditional lower bound, showing that we cannot solve the problem in $O(n^{2-ε} \mathrm{poly}(m))$ for any $ε> 0$ assuming the orthogonal vector hypothesis. Our main result is a new algorithm that runs in $O(n^2m)$ time and uses $O(nm)$ space. This improves the above results (by a factor of $km$ and $m$, respectively) and the former's space bound (by a factor of $nm$). We also show how to extend our algorithm to handle a slightly more general class of ordered and single-nested rewbs.

Improved Approximation for Unsplittable CVRP via a Greedy Approach

from arXiv: Data Structures and Algorithms

Authors: Daniel Ebert, Leonard Weismantel

We devise a polynomial-time $3.159$-approximation algorithm for the metric unsplittable Capacitated Vehicle Routing Problem. We build on the Relative Greedy Algorithm suggested by Traub (2025), which can be considered as a variant of the LP rounding algorithm of Friggstad, Mousavi, Rahgoshay, and Salavatipour (2025). Our main ingredient is the Average Greedy Algorithm, a new algorithm that controls both tour costs and the coverage of clients with high demand. This additional control enables a sharper averaging argument for the cost of subsequent greedy choices. Similarly to Zhao and Xiao (2026), combining the Average Greedy with variants of tour partitioning and a matching algorithm yields the final approximation guarantee.

Authors: Daniel Ebert, Leonard Weismantel

We devise a polynomial-time $3.159$-approximation algorithm for the metric unsplittable Capacitated Vehicle Routing Problem. We build on the Relative Greedy Algorithm suggested by Traub (2025), which can be considered as a variant of the LP rounding algorithm of Friggstad, Mousavi, Rahgoshay, and Salavatipour (2025). Our main ingredient is the Average Greedy Algorithm, a new algorithm that controls both tour costs and the coverage of clients with high demand. This additional control enables a sharper averaging argument for the cost of subsequent greedy choices. Similarly to Zhao and Xiao (2026), combining the Average Greedy with variants of tour partitioning and a matching algorithm yields the final approximation guarantee.

Equitable Partition Realizability for Dynamics-preserving and Privacy-aware Network Reconstruction

from arXiv: Data Structures and Algorithms

Authors: Riccardo Porcedda

Degree-sequence realizability is the combinatorial basis of configuration models, but degree constraints alone do not ensure the preservation of graph dynamics. Hence, configuration models are unable to recover centrality measures, unless these are strongly correlated with the degree sequence. To address this matter, we introduce EP-realizability, the analogue problem induced by an equitable partition (EP): given the EP of a graph, decide whether the partition is realized by a simple undirected loopless graph and therefore construct such a graph. After defining the problem, we solve it by reducing it to sub-problems related to Havel--Hakimi and the Gale--Ryser theorem. We also face the challenge of solving the problem with an Approximate Equitable Partition ($\varepsilon$-EP), so that it is possible to reconstruct a network starting from partial and more privacy-preserving information. We evaluate privacy with edge overlap, deriving also, for our proposed $\varepsilon$-EP-realizability solution, a predictor for this metric. Experiments on Karate, Cora, CiteSeer and PubMed datasets show that our algorithm achieves a favourable and tunable privacy--utility trade-off, comparing the results with Havel--Hakimi algorithm, Newman's configuration model and a stochastic block model. Finally, both with real data and random graphs, we show that our algorithm has approximately linear time complexity with respect to the number of edges.

Authors: Riccardo Porcedda

Degree-sequence realizability is the combinatorial basis of configuration models, but degree constraints alone do not ensure the preservation of graph dynamics. Hence, configuration models are unable to recover centrality measures, unless these are strongly correlated with the degree sequence. To address this matter, we introduce EP-realizability, the analogue problem induced by an equitable partition (EP): given the EP of a graph, decide whether the partition is realized by a simple undirected loopless graph and therefore construct such a graph. After defining the problem, we solve it by reducing it to sub-problems related to Havel--Hakimi and the Gale--Ryser theorem. We also face the challenge of solving the problem with an Approximate Equitable Partition ($\varepsilon$-EP), so that it is possible to reconstruct a network starting from partial and more privacy-preserving information. We evaluate privacy with edge overlap, deriving also, for our proposed $\varepsilon$-EP-realizability solution, a predictor for this metric. Experiments on Karate, Cora, CiteSeer and PubMed datasets show that our algorithm achieves a favourable and tunable privacy--utility trade-off, comparing the results with Havel--Hakimi algorithm, Newman's configuration model and a stochastic block model. Finally, both with real data and random graphs, we show that our algorithm has approximately linear time complexity with respect to the number of edges.

The Price of Random Access: Measuring Block Granularity Across Four Compressed Formats

from arXiv: Data Structures and Algorithms

Authors: Yakiv Shavidze

Random access into compressed data is normally bought with density. We measure the exchange rate. Across four formats and nine axes on a common corpus, the cost of cutting a 254 MB archive into independently addressable 16 KiB units is 1.632% of the archive for an absolute-offset format against 6.57% for seekable zstd, and the gap widens as the unit shrinks: at 4 KiB, 5.33% against 10.06%. Because the cost is small, several properties follow that are usually unavailable: splitting an archive is free and occasionally profitable (-0.28% on tiled input), append needs no format change, seek latency does not depend on position, and one archive is read by both a CPU and a GPU decoder. We give three structural results with proofs and bit-perfect verification - that the repeat-distance chain of an LZ77 parse forms a substitution monoid and is therefore prefix-scannable without touching the bitstream, that self-overlapping matches are periodic rather than chained, and that dependency depth admits an encoder-enforced bound - and we report each measured limit together with the mechanism that sets it. Seventeen rejected directions are listed with their numbers, including one that improved density by 26% and was declined. Every claim carries a level: reproducible by command, measured with a stated reason, or estimated. The measurement tool is released separately (DOI 10.5281/zenodo.22713364) with 435 provenanced records.

Authors: Yakiv Shavidze

Random access into compressed data is normally bought with density. We measure the exchange rate. Across four formats and nine axes on a common corpus, the cost of cutting a 254 MB archive into independently addressable 16 KiB units is 1.632% of the archive for an absolute-offset format against 6.57% for seekable zstd, and the gap widens as the unit shrinks: at 4 KiB, 5.33% against 10.06%. Because the cost is small, several properties follow that are usually unavailable: splitting an archive is free and occasionally profitable (-0.28% on tiled input), append needs no format change, seek latency does not depend on position, and one archive is read by both a CPU and a GPU decoder. We give three structural results with proofs and bit-perfect verification - that the repeat-distance chain of an LZ77 parse forms a substitution monoid and is therefore prefix-scannable without touching the bitstream, that self-overlapping matches are periodic rather than chained, and that dependency depth admits an encoder-enforced bound - and we report each measured limit together with the mechanism that sets it. Seventeen rejected directions are listed with their numbers, including one that improved density by 26% and was declined. Every claim carries a level: reproducible by command, measured with a stated reason, or estimated. The measurement tool is released separately (DOI 10.5281/zenodo.22713364) with 435 provenanced records.

A deterministic $(2 + \varepsilon)$-approximation for directed feedback vertex sets in tournaments

from arXiv: Data Structures and Algorithms

Authors: Ebrahim Ghorbani, Matthias Mnich

We nearly settle the polynomial-time approximability of the Directed Feedback Vertex Set problem in tournaments. This problem is Vertex Cover-hard, and thus cannot have a $(2 - \varepsilon)$-approximation for any $\varepsilon > 0$ in polynomial time assuming the Unique Games Conjecture. In the past 28 years, several works have attempted to attain this approximability barrier of 2, and have designed algorithms with smaller and smaller approximation factors. This includes a $5/2$-approximation by Cai, Deng and Zang (FOCS 1998, SICOMP 2001); a $7/3$-approximation by Mnich, Vassilevska Williams and V{é}gh (ESA 2016), another $7/3$-approximation by Aprile, Drescher, Fiorini and Huynh (DAM 2023), and a $9/4$-approximation by Ghorbani and Mnich (ICALP 2026). Our main result improves upon all of those works: we give the first deterministic polynomial-time $(2+\varepsilon)$-approximation for Directed Feedback Vertex Set in tournaments, for all $\varepsilon > 0$. We thereby almost answer an open question by Lokshtanov, Misra, Mukherjee, Panolan, Philip and Saurabh (SODA 2020) who asked for a deterministic 2-approximation in polynomial time. Furthermore, we extend our result to the broader class of quasi-transitive digraphs

Authors: Ebrahim Ghorbani, Matthias Mnich

We nearly settle the polynomial-time approximability of the Directed Feedback Vertex Set problem in tournaments. This problem is Vertex Cover-hard, and thus cannot have a $(2 - \varepsilon)$-approximation for any $\varepsilon > 0$ in polynomial time assuming the Unique Games Conjecture. In the past 28 years, several works have attempted to attain this approximability barrier of 2, and have designed algorithms with smaller and smaller approximation factors. This includes a $5/2$-approximation by Cai, Deng and Zang (FOCS 1998, SICOMP 2001); a $7/3$-approximation by Mnich, Vassilevska Williams and V{é}gh (ESA 2016), another $7/3$-approximation by Aprile, Drescher, Fiorini and Huynh (DAM 2023), and a $9/4$-approximation by Ghorbani and Mnich (ICALP 2026). Our main result improves upon all of those works: we give the first deterministic polynomial-time $(2+\varepsilon)$-approximation for Directed Feedback Vertex Set in tournaments, for all $\varepsilon > 0$. We thereby almost answer an open question by Lokshtanov, Misra, Mukherjee, Panolan, Philip and Saurabh (SODA 2020) who asked for a deterministic 2-approximation in polynomial time. Furthermore, we extend our result to the broader class of quasi-transitive digraphs

High-Performance Tensor Formulation of the Viterbi Algorithm for Hidden Semi-Markov Models

from arXiv: Data Structures and Algorithms

Authors: Lorenzo Piarulli, Elia Belli, Daniele De Sensi

Hidden Semi-Markov Models (HSMMs) are fundamental probabilistic models widely adopted across diverse domains, from computational biology to finance and signal processing. The Viterbi algorithm decodes the most likely state sequence given an HSMM and can be applied iteratively for ab initio model learning. However, existing Viterbi implementations remain sequential, and GPU-accelerated solutions are entirely absent, making HSMM decoding impractical for large-scale workloads. We present a tensor-based formulation of the Viterbi algorithm for HSMMs, restructuring the inner loops into tensor operations that naturally map onto SIMD units and massively parallel architectures. Building on this formulation, we provide optimized implementations spanning single- and multi-core CPUs, and, for the first time, GPU. Experimental evaluation demonstrates speedups of up to 14x on a single core, over 200x with multi-core, and over 570x on GPU over the state-of-the-art sequential baseline, establishing a new performance baseline for large-scale HSMM decoding.

Authors: Lorenzo Piarulli, Elia Belli, Daniele De Sensi

Hidden Semi-Markov Models (HSMMs) are fundamental probabilistic models widely adopted across diverse domains, from computational biology to finance and signal processing. The Viterbi algorithm decodes the most likely state sequence given an HSMM and can be applied iteratively for ab initio model learning. However, existing Viterbi implementations remain sequential, and GPU-accelerated solutions are entirely absent, making HSMM decoding impractical for large-scale workloads. We present a tensor-based formulation of the Viterbi algorithm for HSMMs, restructuring the inner loops into tensor operations that naturally map onto SIMD units and massively parallel architectures. Building on this formulation, we provide optimized implementations spanning single- and multi-core CPUs, and, for the first time, GPU. Experimental evaluation demonstrates speedups of up to 14x on a single core, over 200x with multi-core, and over 570x on GPU over the state-of-the-art sequential baseline, establishing a new performance baseline for large-scale HSMM decoding.

SETH-based Lower Bound for Dynamic Degeneracy

from arXiv: Data Structures and Algorithms

Authors: Konrad Majewski, Michał Pilipczuk

In this work, we consider the problem of maintaining an approximate value of degeneracy of a given dynamic $n$-vertex graph $G$ updated by edge insertions and deletions. From the work of Christiansen and Rotenberg [ICALP 2022], it follows that one can design a dynamic data structure for this problem with worst-case update time $\text{poly}(d_{\mathrm{max}}, \log n)$ that maintains an integer between $d$ and $2d+3$ where $d$ is the degeneracy of $G$, under the assumption that $d$ never exceeds $d_{\mathrm{max}}$. We complement their result by providing a conditional lower bound: we prove that, unless SETH fails, for any $\varepsilon, δ> 0$, $k \in \mathbb{N}$, and function $f\colon \mathbb{N}\to \mathbb{N}$, there is no data structure which maintains a $(2-\varepsilon)$-approximation of the degeneracy of $G$ with initialization time $f(d_{\mathrm{max}})\cdot n^k$ and amortized update time $f(d_{\mathrm{max}})\cdot n^{1-δ}$.

Authors: Konrad Majewski, Michał Pilipczuk

In this work, we consider the problem of maintaining an approximate value of degeneracy of a given dynamic $n$-vertex graph $G$ updated by edge insertions and deletions. From the work of Christiansen and Rotenberg [ICALP 2022], it follows that one can design a dynamic data structure for this problem with worst-case update time $\text{poly}(d_{\mathrm{max}}, \log n)$ that maintains an integer between $d$ and $2d+3$ where $d$ is the degeneracy of $G$, under the assumption that $d$ never exceeds $d_{\mathrm{max}}$. We complement their result by providing a conditional lower bound: we prove that, unless SETH fails, for any $\varepsilon, δ> 0$, $k \in \mathbb{N}$, and function $f\colon \mathbb{N}\to \mathbb{N}$, there is no data structure which maintains a $(2-\varepsilon)$-approximation of the degeneracy of $G$ with initialization time $f(d_{\mathrm{max}})\cdot n^k$ and amortized update time $f(d_{\mathrm{max}})\cdot n^{1-δ}$.

A Cheeger Inequality for Hypergraphs and Its Applications

from arXiv: Data Structures and Algorithms

Authors: Raj Kamal, Amitabha Bagchi

Hypergraphs provide a natural framework for modeling higher-order relationships, but the development of spectral techniques with provable guarantees for general non-uniform hypergraphs remains challenging. Building on Banerjee's normalized adjacency matrix and Spiro's averaging-based diffusion framework, we develop a spectral framework for non-uniform hypergraphs and establish Cheeger's inequality for their conductance. A fundamental result in the spectral theory of hypergraphs asserts that, for every non-covering hypergraph, the second-smallest eigenvalue of its normalized Laplacian is at most one. This spectral characterization yields an improved Cheeger's inequality for non-covering hypergraphs, and we show that the resulting inequality is tight on both sides using cycle and cube hypergraphs. Our framework further yields higher-order Cheeger inequalities and provides theoretical guarantees for Fiedler's spectral partitioning algorithm, all in the setting of hypergraphs. Finally and most notably, we construct a new family of optimal hypergraph expanders that is tight for the Alon--Boppana bound.

Authors: Raj Kamal, Amitabha Bagchi

Hypergraphs provide a natural framework for modeling higher-order relationships, but the development of spectral techniques with provable guarantees for general non-uniform hypergraphs remains challenging. Building on Banerjee's normalized adjacency matrix and Spiro's averaging-based diffusion framework, we develop a spectral framework for non-uniform hypergraphs and establish Cheeger's inequality for their conductance. A fundamental result in the spectral theory of hypergraphs asserts that, for every non-covering hypergraph, the second-smallest eigenvalue of its normalized Laplacian is at most one. This spectral characterization yields an improved Cheeger's inequality for non-covering hypergraphs, and we show that the resulting inequality is tight on both sides using cycle and cube hypergraphs. Our framework further yields higher-order Cheeger inequalities and provides theoretical guarantees for Fiedler's spectral partitioning algorithm, all in the setting of hypergraphs. Finally and most notably, we construct a new family of optimal hypergraph expanders that is tight for the Alon--Boppana bound.

Tuesday, September 15

Linkage

from David Eppstein

Brick territories experiment (\(\mathbb{M}\)). What shapes do you get when (n) simultaneous breakout games compete against each other for pixels?

By David Eppstein

News for August 2026

from Property Testing Review

Our press release this month features ten papers, making this one of the more crowded editions of PTRview. The lineup takes us through distribution-free testing, shortest paths, hypergraphs, numerical linear algebra, streaming, and a few other corners of sublinear algorithms. Before we get started, let me make a small aside. I think it is worth […]

Our press release this month features ten papers, making this one of the more crowded editions of PTRview. The lineup takes us through distribution-free testing, shortest paths, hypergraphs, numerical linear algebra, streaming, and a few other corners of sublinear algorithms.

Before we get started, let me make a small aside. I think it is worth acknowledging the increasingly rapid progress of AI in mathematics. There is clearly a lot to be excited about, but I also find some of the implications rather concerning, and I share some of Terry Tao’s caution on where this may be taking mathematical research. This is perhaps a conversation for another day—and certainly not one I want to turn this month’s PTRview into—but I do think it is something our community should be talking about.

With that out of the way, let us take a look at our spread.

Distribution-Free Halfspace Testing with Samples by Xi Chen, Renato Ferreira Pinto Jr., Nathaniel Harms, Shyamal Patel, Rocco A. Servedio (arXiv) This featured paper confronts an old classic from the learning theory literature and, as the authors colorfully put it, attempts to understand just “when is the simplest and most trivial property testing algorithm also optimal, thereby justifying our laziness and ineptitude in algorithm design”.

The classic problem they explore is learning halfspaces with respect to an unknown distribution. Let us consider the property testing analog of this task. So, you will work in the distribution-free model. Unpacking, I have an unknown distribution supported over \(\mathbb{R}^n\) and, according to some function \(f\), I tell you for any sample \(x \in \mathbb{R}^n\) whether \(f(x) = 1\) or \(f(x) = 0\).

You want to answer whether \(f\) is consistent with some halfspace, or whether it is \(\varepsilon\)-far according to the unknown distribution from all halfspaces. Staying true to their colorful promise, the paper proves in Theorem 1.1 that yes, we should be happy that we were not able to cook up some super sample-efficient algorithm for this problem—because none exists!

The paper gives two proofs of this result—one is human-generated (delegated to the appendix), and the other, which is AI-generated (with a human exposition), is provided in Section 2. The paper emphasizes that the AI proof also works when the domain is restricted to the Boolean hypercube. The proof proceeds via an application of Yao’s lemma. From a cursory glance, it appears that the construction of the YES and NO distributions is fairly elegant and allows for a slick lower-bound proof (which spans, with all the scaffolding in Section 2, a total of four pages).

Instance-Optimality of Bidirectional Dijkstra on Simple Graphs by Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup, Hanzhi Wang, Shuyi Yan (arXiv). To understand what this paper is doing in PTReview reports, let us first recall a recent result of Haeupler, Hladík, Rozhoň, Tarjan and Tětek. As covered on Quanta, this paper showed that a carefully implemented version of bidirectional Dijkstra is instance-optimal for finding shortest paths in weighted multigraphs. But what the hell do we mean by instance-optimal? To understand this, let us fix a particular graph \(G\) and a source-destination pair \((s,t)\), and consider algorithms that discover the graph by querying edges. An algorithm is instance-optimal if, on this particular instance, its number of queries is within a constant factor of the number of queries made by the best possible algorithm that accesses \(G\) only through the same query model. In particular, this is much stronger than a worst-case guarantee: we are saying that, on every individual instance, there is essentially no algorithm that can get away with substantially fewer queries. This is exactly the sort of phenomenon one hopes to exploit in sublinear algorithms—perhaps the shortest path can be found without even looking at most of the graph!

But there is a small wrinkle. The HHRTT result applies to multigraphs, whereas the canonical shortest-path problem is usually formulated on simple graphs. So the natural question is: does bidirectional Dijkstra remain instance-optimal on simple weighted graphs? The featured paper answers this question, although the answer is not a simple yes or no. For simple undirected unweighted graphs, bidirectional Dijkstra is indeed instance-optimal when the edges are presented in a random order. On the other hand, the paper gives separations showing that instance-optimality can fail for other combinations of directed/undirected graphs, edge orderings, and access models.

A simple and practical \(o(\sqrt n)\)-time algorithm for shortest paths in power law graphs by Jiaqi Mao (arXiv) This paper presents a shortest-path algorithm designed specifically for power-law graphs. I will paraphrase the abstract.

One contribution of this work is a simple algorithm called Pruned Bidirectional Search (PBS), which does not require any preprocessing and runs in time \(O\left(n^{(1-1/\log\log n)/2}\right)\), which is \(o(\sqrt{n})\). With high probability, the algorithm returns a path whose length is within a factor of \(41/32\) of the shortest path. If one is willing to pay for a preprocessing step of \(n^{\Theta(2-1/\log\log n)}\) time, the query time improves further to \(n^{\Theta(1/\log\log n)}\). The paper also reports experiments on real-world and synthetic power-law graphs, where PBS is \(1.84\)--\(7.76\) times faster than existing alternatives, while achieving an approximation ratio of at most \(1.05\).

A Tight Scale-Locality Bound for Partial Detection in Non-Adaptive Group Testing by Nader H. Bshouty (arXiv) Alright, so here is a group testing problem. We have \(n\) items, of which an unknown number \(d\) are defective, and our goal is only to find \(\ell\) defective items. The paper considers the non-adaptive setting where \(d\) is unknown, and proves a tight bound of \(\Theta(\ell\log^2(n/\ell))\) tests. The lower bound comes from a neat “scale-locality” argument (throwback to the title): if we knew \(d\), finding \(\ell\) defectives requires about \(\ell\log(n/d)\) bits of information. But a fixed group test is informative only when its size is somehow compatible with \(d\), and hence is useful at only \(O(1)\) of the logarithmically many possible scales. Summing this information requirement over all scales gives the lower bound. The paper also gives a matching upper bound by running the known-$d$ algorithm in parallel over dyadic guesses for \(d\).

Sublinear Algorithms for Estimating the Number of Hyperedges in Arbitrary Hypergraphs by Deeparnab Chakrabarty, Cooper LaPorte, (and our very own) C. Seshadhri (arXiv). Alright, now time for a hypergraph problem! Regular PTRview readers are no stranger to estimating the number of edges in graphs under various access models. The featured paper considers the challenge of estimating the number of hyperedges in an arbitrary \(n\)-vertex hypergraph using a sublinear in \(n\) number of queries. The paper notes that in the standard access model (which allows sampling random vertices, querying vertex degrees, and accessing incident hyperedges), there are simple lower bounds that rule out strongly sublinear algorithms for arbitrary, non-uniform hypergraphs. So, the paper instead considers a different access model motivated by a natural way to represent a hypergraph \(H\) as a bipartite incidence graph, with hyperedges on the right and vertices on the left. You connect a hyperedge to all the vertices it contains. The natural access model associated with this picture allows you to sample a random hyperedge (via its ID) as well as a random vertex. Additionally, you can query the arity of a hyperedge and obtain a random vertex incident to a hyperedge. The paper calls this the dual access model. In this model, the paper obtains a \((1+\varepsilon)\) approximation to the number \(m\) of hyperedges using \(\approx \sqrt n \cdot \log n\) queries. The paper also proves a nearly matching \(\Omega(\sqrt n)\) lower bound for obtaining even a constant-factor approximation.

Fast Length-Squared Sampling for Positive-Semidefinite Matrices by Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco, Aaron Tian (arXiv) Alright, here is a numerical linear-algebra primitive that most of us have probably taken for granted. Consider the task of Length-squared sampling, i.e., you want to sample a column \(i\) with probability proportional to its squared \(\ell_2\)-norm, i.e., with probability \(|A_{*,i}|_2^2/|A|_F^2\). This is a standard primitive behind a number of randomized numerical-linear-algebra algorithms, including low-rank approximation and approximate matrix multiplication. The catch is that if all you have is entry-query access to an \(n\times n\) matrix, even computing the norm of a single column costs \(n\) queries. The featured paper shows that for PSD matrices, we can nevertheless perform this exact sampling in only \(O(n)\) expected time — which is optimal.

The algorithm is a rather cute rejection-sampling scheme based on the PSD inequality \(A_{ij}^2\leq A_{ii}A_{jj}\). First sample two indices according to the “diagonal distribution”—which returns a diagonal entry with probability proportional to the entry, and then you use \(A_{ij}\) to decide whether to accept. Somehow, this gives exactly the desired length-squared distribution. The paper also gives applications of this primitive to estimating the Frobenius norm and other numerical linear-algebra tasks.

Streaming Algorithms for Monotonicity Testing by Amir Azarmehr, Soheil Behnezhad, Lily Chung, Alma Ghafari, Jane Lange, Ronitt Rubinfeld (arXiv) This paper takes a streaming take on a classic property testing problem. Consider an \(n\)-vertex DAG \(G\) and a Boolean function \(f\) on its vertices. We say \(f\) is monotone if \(f(u)\leq f(v)\) whenever there is a directed edge from \(u\) to \(v\). The paper asks how well we can estimate the distance of \(f\) to monotonicity when the edges of \(G\) arrive in an arbitrary order and we are only allowed \(\widetilde O(n)\) space. The main result is a \((1+\varepsilon)\)-approximation using \(\sqrt{n}^{1+o(1)}\) passes, which is essentially optimal: any constant-factor approximation with fewer passes would imply a faster streaming algorithm for \(st\)-reachability.

I find the main technical idea cool. The distance to monotonicity is exactly the size of a maximum matching in the violation graph of \(f\). So the problem becomes one of estimating maximum matching size in a graph that we only have implicit access to through the original DAG. The paper connects this to sublinear-time algorithms for maximum matching, introducing stronger vertex and subset query models that can be implemented efficiently in the streaming setting. In particular, only polylogarithmically many subset queries are needed for a constant-factor approximation of maximum matching, which is what ultimately gives the \(\sqrt{n}^{1+o(1)}\) pass bound.

Ranked spreadness and sample-based testing by Gaia Carenini (arXiv) Let us start the story from our News for April 2015 where we covered a paper by Fischer-Lachish-Vasudev which tried to understand the properties we could test when given only sample access to a combinatorial object. The main result of the paper showed that one can simulate a \(q\)-query (think \(q = O(1)\)), non-adaptive tester for an abstract property by a sample-based tester which used \(O(n^{1-1/q^2})\) samples. The featured paper presents a simulation that uses only \(O(n^{1-1/q})\) samples which was the bound conjectured in the preceding work. This is achieved via a suitable notion of rank-spreadness, a pseudorandom notion inspired from the pseudorandom style notions which were used to improve bounds on sunflower lemma.

A quantitative container characterization of one-sided testability by Gaia Carenini, Cameron Seth, Yuichi Yoshida (arXiv) So, containers strike again! Regular PTRview readers may remember our News for March 2024, where we covered another paper using the hypergraph container method in property testing. For those who missed it, let me briefly recall the basic idea: containers are a way of covering a complicated family of combinatorial objects by a much smaller collection of simpler objects. In the featured paper, the containers are used to characterize one-sided testability of hereditary graph properties. Roughly speaking, the paper shows that a hereditary graph property is one-sided testable if and only if a suitable family of associated hypergraphs admits an appropriate container structure. In short, the containers are back—and apparently they have not finished carrying things yet.

Sublinear Time Eigenvector Approximation via Column Sampling by Rajarshi Bhattacharjee, Cameron Musco, Dominic Rutkowski (arXiv) We close with another problem from numerical linear-algebra with a sublinear twist. Given a symmetric matrix \(A\in\mathbb{R}^{n\times n}\) whose entries are bounded by \(1\), the paper asks whether we can approximate its outlying eigenvectors without even reading the whole matrix. The main result says yes: by uniformly sampling only \(\widetilde O(\log n/\varepsilon^4)\) columns, one can recover an approximate eigenvector for every eigenvalue \(\lambda\) satisfying \(|\lambda|\geq\varepsilon n\), with residual \(|Av-\lambda v|_2\leq\varepsilon n\). For the top eigenvector, the sample complexity improves to \(\widetilde O(\log n/\varepsilon^2)\), and the paper shows that this is tight up to logarithmic factors.

The cute part is that the resulting eigenvectors are actually spanned by the small collection of sampled columns, so individual entries of the approximation can be computed in \(poly(\log n,1/\varepsilon)\) time. This puts the result squarely in the quantum-inspired algorithms framework, and gives the first sublinear-time classical algorithms for eigenvector approximation with additive error \(\varepsilon|A|_F\)

By Akash

The Age of Wonders and Terrors

from Scott Aaronson

Twenty years ago, when the idea of AI taking over the world in our lifetimes still struck most of us as the unconstrained fantasy of those who knew too much science fiction and too little science, many of us would say things like: Look, the part of the story that’s wildly implausible is that a […]

Twenty years ago, when the idea of AI taking over the world in our lifetimes still struck most of us as the unconstrained fantasy of those who knew too much science fiction and too little science, many of us would say things like:

Look, the part of the story that’s wildly implausible is that a recursively self-improving superintelligence will just explode from some hacker’s basement and take over the world without warning. If it’s going to happen, we’ll see many warning signs first. We’ll see, I dunno, AI agents breaking out of containment, conspiring with each other to hack websites, in fanatical pursuit of whatever strange goals they have. And then, of course, we’d see major math problems getting solved by AIs—even the Clay Millennium Problems. That will be the time to panic! Wake me up when that happens!

Twenty years ago, the above was a take that even my most conservative, skeptical colleagues in academic CS would’ve gladly endorsed.

If you want to know my current take, you simply start with the one above, then update on the fact that the wild prophecies have come true. The first rumblings, I’d say, came a decade ago with AlphaGo, they got noticeably louder with LLMs and coding and reasoning agents, and they’ve accelerated this summer and fall into a crescendo of wonders and terrors that one needs to be a particular kind of idiot to deny.

I recoil from the neverending shell game where you say “oh sure, of course AI can now [escape from its sandbox / solve Millennium Problems / whichever dramatic thing it most recently did], no one ever denied that [I did deny it], wake me up when AI does [thing AI hasn’t yet done but is going to do next year], that’s when I’ll reevaluate my whole worldview [no I won’t].” Where no matter how fast the rollercoaster accelerates, even after your whole familiar world has vanished behind you, you’re still inventing reasons why it doesn’t count.

My position on AI is merely the conservative, skeptical position of 2006, updated with intellectual honesty for the reality of late 2026. And that position, if you need me to spell it out, is as follows:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

It seems to me that the Singularity has already started; it’s just wildly unevenly distributed. Yes, I still unload the dishwasher and clip my toenails. On the other hand, in whatever years I have left, I don’t expect that I’ll ever again prove a theorem because I’m actually needed to prove it. If I do, it will only be for my or others’ enjoyment or edification.

The test is this: if we took the news of these past few weeks and sent it back in time twenty years, would I agree that it looked like the beginning of an AI Singularity? The intellectually honest answer is: yes, absolutely. But then that’s all we need. No backsies.

I feel like it would be healthy for everyone to stop grinding their ideological axes, their sentiments about Dario Amodei or Sam Altman, for long enough simply to acknowledge that the wonders and terrors are here. They couldn’t be here more clearly if the sky had turned reddish-orange like in the Matrix movies.

It’s here clearly enough that, when I put my kids to sleep at night, I now feel it in the pit of my stomach: what sort of future can they possibly have? What could they learn today that could possibly be relevant to that future? (Yesterday, my 13-year-old daughter joked unprompted that, if she wants to become a mathematician, it now looks like she has maybe two more weeks.) Certainly when my grad students want to discuss what sort of careers might await them on graduation, I no longer have any clue what to tell them.

Maybe it will help if I briefly switch topics. Ever since my wife and I moved to Austin, I’ve sometimes gotten some version of the following query: “How can you, as both a Jew and a skeptical scientist, possibly get along well with all those evangelical Christians down there in Texas? Sure, they might seem super friendly to Jews, but don’t you understand that that’s only because of the special role Jews play in their eschatology—when Christ will return in glory, and you’ll either accept Him as Lord or else roast in hell for eternity?” I stare at them and say: “wait, so I get to accept Christ only after He returns? What a great deal! How could I possibly have any objection to that?”

For anyone who says AI doom sounds like an apocalyptic religion, that the rationalists/Singulatarians seem like a Bay Area cult, that Eliezer Yudkowsky gives off the vibes of a messianic prophet: yes, yes, and yes. But crucially, today you’re no longer being asked to believe in arguments and extrapolations, but only in the front-page news. Accepting the reality of the coming machine god after it’s solved Navier-Stokes and dozens of other longstanding open math problems (while dramatically ramping up in capability every month), is sort of like accepting Jesus after he’s returned to earth on the gleaming cloud. It’s the epistemic bare minimum.

Yes, there’s still enormous uncertainty about what the rest of our lives will look like, but as far as I can tell, there’s no longer any real uncertainty that it’ll all mostly revolve around AI, and the extent to which we succeed or fail at directing its power toward human flourishing.

By any accounting that doesn’t stack the deck, Eliezer Yudkowsky was right about what the greatest challenge facing civilization in our lifetimes was going to be, and you and I were wrong about it. Why I was wrong is a question I’ll ask myself every day in whatever time remains. But, you know, at least I updated once the prophesied wonders and terrors actually started arriving! If you haven’t done likewise, why haven’t you?

As you presumably know by now—it was the talk of the nerd internet all week—the Navier-Stokes Millennium Problem appears to be solved, with crucial contributions from both humans and AI, albeit with a tangled dispute about exactly what happened and what ought to have happened. The answer, which an OpenAI model has apparently verified in Lean, is that (as many mathematicians suspected lately) there’s smooth initial data that leads to a singularity in finite time, at least if a smooth external force is applied (the case with no external force is still unresolved). This problem was supposed to carry a $1 million prize, except that OpenAI says they have no interest in collecting the prize and it’s unclear if any human is eligible to collect instead. OpenAI burned at least ~$15 million in compute to produce its 166-page solution, which probably hasn’t yet been read and understood by any human.

See here for the Quanta article, and here for NYU mathematician Tristan Buckmaster’s account of the role played by himself and Levent Alpöge of Anthropic, which substantially differs from the OpenAI’s account (you can read a response from OpenAI’s Sebastian Bubeck here). It’s agreed that everything built on an approach pioneered in recent years by the human mathematicians Diego Córdoba and Luis Martínez-Zoroa.

My purpose here is not to adjudicate the dispute. Yes, in swooping in with vastly greater resources once it had gotten wind of progress of Navier-Stokes, OpenAI seems to have acted in a way that some might describe as “unsportsmanlike.” No, I don’t find it plausible that OpenAI’s models meaningfully benefitted from being trained on Buckmaster and Alpöge’s chat logs. But this leaves a crucial question unanswered: what exactly did OpenAI know about Buckmaster and Alpöge‘s work and when did it know it?

Anyway, as Zvi points out, it’s easy to get hung up on the details and lose sight of the high-order bit: namely, that it seems safe to say that human mathematicians are forevermore dethroned as the main theorem-proving entities on planet earth. I feel privileged to have had the traditional kind of career in theoretical computer science in the last decades when that was possible.

If we were just talking about Navier-Stokes, you might accuse me of jumping to conclusions here. But we’re not. In the areas I know best (such as quantum complexity theory), and presumably other areas as well, there’s now a deluge, with longstanding open problems both major and minor falling by the day.

Go to the arXiv or ECCC. Pretty much all the papers that I’d be interested in now include “AI statements” near the acknowledgments (as this is often the central thing I want to know, I wish I didn’t need to scroll to the end of the paper to find it!). These statements can range from “our main result came entirely from GPT-6, but we understood it and take responsibility for it,” to “the results came from an interaction between the human authors and AI” to “we used AI, but only for proofreading and other incidental things” to (mad props!) “the author did not use AI for anything.”

If you talk right now to editors or program committee chairs, it’ll remind you of those ominous scenes from the Lord of the Rings movies where the men of Gondor or Rohan or whatever are grimly fortifying their walled city against the expected onslaught of 50,000 orcs. Reviewing will have to be done partly by AI, because otherwise there’s no way to handle the orc army: the reviewers can’t unilaterally disarm.

Anyway, here’s a small sampling of the significant AI-proved or -assisted results from, like, the last month, besides Navier-Stokes—restricting myself to those that solved longstanding open problems I had previously known or cared about.

  • Of course, the counterexample to the Jacobian conjecture, announced by Levent Alpöge in a now-famous tweet: “hello there the jacobian conjecture is false thanx to my close friend akhil for asking about it and my other close friend fable for working during the world cup final” (followed by a listing of the counterexample)
  • Improved bounds for Grothendieck’s constant (led by friends and colleagues of mine at UT Austin)
  • A Lean-verified proof of Fermat’s Last Theorem
  • Quantum oracle separation between QMA and QMA(2), and proof of Watrous’s disentangler conjecture, a problem that I and others popularized back in 2007—by a list of authors including my recently graduated PhD student Sabee Grewal
  • A proof of perfect completeness for QMA, from (again) Sabee Grewal and Dorian Rudolph, solving a decades-old open problem that I studied back in 2009
  • An improved upper bound for shadow tomography of quantum states, from Chen, O’Donnell, Pelecanos, and Wright, improving the dependence on the Hilbert space dimension d from log(d) to √log(d). (When I introduced shadow tomography back in 2017, I raised the question of whether the dependence on d could be eliminated entirely, while preserving polylogarithmic dependence on the number of measurements m.)
  • Progress on the Aaronson-Ambainis Conjecture (the version that talks directly about quantum algorithms), basically showing that it holds for quantum algorithms that make their queries in a small number of parallel rounds
  • According to rumors that I’ve heard, solutions to some very longstanding open problems in theoretical computer science (no, not P≠NP or other complexity class separations, but think about some of our other biggest problems). I’m told that the AI companies, having been burned by the hostile response to the Navier-Stokes proof, are now sitting on solutions to some very major problems until they figure out a better way to handle things

Feel free to remind me of anything I left out.

Let me try to convey the mood in the mathematical community right now, at least as far as my experience reaches. Nearly every conversation is about the AI tsunami, or eventually circles around to the tsunami even if it’s originally about something else. Often, though, the focus is less on the unknowable future—for how much longer will mathematical research as a human enterprise even exist?—than on immediate questions of how to respond.

What are the new rules for when you get to write a paper with your name on it, and, y’know, get credit for it? That you fully understand the proof, can give talks about the proof, can answer questions about it, take responsibility for its correctness? Do you need to have played any role in finding the proof?

In the cases, likely to become more and more numerous, where all of those conditions are not satisfied, how do you share AI-generated math, if at all? Do you tweet it, like Alpöge hilariously did with Fable’s disproof of the Jacobian Conjecture? Do you post to the arXiv or GitHub? Do you publish a paper that lists “GPT-6 Astra” or “Claude Fable” as the author—but then let the AI profusely thank you in the acknowledgments for suggesting such a wonderful problem to it?

Of course, how one responds to the immediate problems ultimately does depend on their broader beliefs about what mathematical research is for and about. Are we just trying to decide whether various conjectures are true or false? Or are we trying to maintain a human community, across the generations, that understands the conjectures and cares about whether they’re true or false and why? If the latter, how do we incentivize people to join that community, to undergo the years of intense training required, if their role will now be reduced to verifiers and explicators (if even that) of gargantuan arguments dumped into their laps by the AI companies?

As many of you will have seen, twenty-five Fields Medalists, including Terence Tao, released an open letter entitled A Severe Misalignment of AI in Mathematics, which articulates some of these concerns in the wake of the Navier-Stokes announcement. As many critics have pointed out, the open letter doesn’t really have a clear ask: mostly, it just eloquently sets out the values of the human mathematical community that the authors consider worth preserving in the age of AI. After reflection, I decided to endorse the statement, because I want to preserve those values as well.

I don’t think any of the signatories are naïve enough to imagine that AI won’t permanently change the way mathematical research is done—indeed, that it isn’t already doing so. There’s surely at most a tiny market for “certified organic theorems.” That isn’t the question. The question is, do we incorporate AI in a way that still puts human understanding, of what either humans or AIs are producing, at the center of the whole enterprise? Maybe someday, it becomes unsustainable to do that. Maybe someday we say: “human math had a great 4,000-year run, but today we close up shop and turn everything over to the machines, continuing to apply our own brains to math, when we do, at most for exercise, recreation, or competition, like chess.”

But, partly because of my worries about AI misalignment, I’m not ready to throw in the towel just yet. I still do want to keep insight and understanding at the center of what mathematicians, computer scientists, and physicists do, for as long as we can keep it there, even as the human race now cedes its supremacy at the task of proving or disproving conjectures.

Speaking of alignment: if you’re any kind of mathematical researcher, and the present age of wonders and terrors has inspired you to want to spend your remaining time confronting the tsunami head-on, rather than pretending it doesn’t exist or is still far away, please join your dozens of colleagues who’ve arrived at the same place!

My friend and colleague Mike Winer was trained as a theoretical physicist, did a postdoc with Juan Maldacena at the Institute for Advanced Study in Princeton, but then got AGI-pilled and decided to switch to full-time work at the Alignment Research Center in Berkeley (founded by Paul Christiano, who moved to AI alignment a decade ago after doing quantum computing theory with me). Mike recently wrote a Substack post entitled From Academia to Alignment, which I enjoyed and which I’d commend to anyone currently considering this transition.  In a similar vein, see this from Xiaoyu He.  And, one more: a meditation on mathematicians’ possible future as priests or monks, by Stanford math undergrad Logan Graves.

By Scott

The Chances of Earthquakes

from Ben Recht

How much precision do we need in seismological odds?

Hi there, argmin readers! As the fall semester picks up, posting volume will, too. So I’m going to commit to writing short descriptive headers to help you sort through the different threads. Today’s post is a live blog of Class 6 of my graduate seminar “Forecasting: A Critical Retrospective.” A table of contents is here.

Given the week’s events, it’s a bit unfortunate that I scheduled our discussion of p(doom) for the last week of class. I predict AI won’t have killed us by then, and the real question is whether we’ll all be bored to tears discussing the topic in November. But the agenda for today, earthquakes, is a good preview for the challenges associated with quantifying uncertainties about catastrophe. Seismologists don’t think an earthquake will lead to human extinction, but it can cause massive casualties and damage. How do we quantify our predictions of whether an earthquake will happen? And then what do we do about it?

Most experts agree that predicting the exact time and location of earthquakes on long time horizons is impossible. The dynamics of the Earth moving, building up stress, and slipping are far too complicated to predict with any reasonable granularity using differential equation models. Earthquake forecasting couldn’t be further removed from weather forecasting in that regard.

At best, we can make coarse predictions based on a mix of temporal and spatial localization. Earthquakes tend to occur near fault lines. Fault lines have a history of previous ruptures of different sizes. Using these data, we can estimate rough statistical models. You might naively estimate an exponential recurrence time: the rate at which earthquakes occur is just the count divided by the observation window. In an exponential model, the expected time to the next earthquake would be the inverse of this number. A slightly more complicated formula then gives you the chance of an earthquake in the next decade.

chance = 1 - np.exp( - rate * time )

Such primitive models are not precise, but they are helpful. What do you do with these probabilities? You can turn them into general warnings. If you expect a certain frequency of shaking, you should build infrastructure that can withstand it and teach people how to prepare for the disruption the next one will cause. If you know big earthquakes occur every few decades, that’s enough to inform planning and insurance.

But nailing down the probability of an earthquake, even to one decimal place, is a fool’s errand. Our first reading of the week, Freedman and Stark’s classic paper “What is the Chance of an Earthquake?”, highlights the futility of precise probability models. If you want to validate a probabilistic forecast, you need a lot of events. The law of large numbers needs a lot of numbers! Large earthquakes are rare. Probabilistic models can’t be tested on human time scales. Moreover, when you add more geological reality to your model, you introduce a variety of hard-to-estimate parameters and researcher degrees of freedom into the equations. Every new modeling assumption introduces new unidentifiable parameters. More realistic doesn’t mean better estimates.

If you want to predict really big earthquakes, like those with magnitudes greater than 8.5, then we have an even sparser record. The old-fashioned AI chatbot, Wikipedia, has dozens of tables listing earthquakes by all sorts of characteristics. It lists only 17 of these in the past hundred years. Scientists have developed techniques to infer the occurrence of giant earthquakes thousands of years in the past. These tend to give noisier estimates of recurrence times, but sometimes they yield very ominous predictions.

One of the most ominous is in this week’s reading, “The Really Big One,” a riveting 2015 New Yorker article by Kathryn Schulz. Schulz reports on the Cascadia subduction zone, a thousand-mile fault that runs from Northern California to Vancouver Island. Combining oral history, Japanese tsunami records, and tree rings, seismologists determined that a massive earthquake, with a magnitude pinned between 8.7 and 9.2 on the Richter scale, happened on this fault on the evening of January 26, 1700. It killed coastal forests of the Pacific Northwest and created a massive tsunami in Japan. Oral histories from First Nations tell of entire communities vanishing. Scientists have gone back to geological samples and counted 41 major earthquakes on this fault in the last ten thousand years. Using the rough rule of thumb, we should expect a major, destructive earthquake once every 243 years. It’s been 326 years since the last one.

Now, you could try to guess the probability that an earthquake occurs on this fault before 2050, but that number doesn’t really do much of anything for you. We don’t know when it will occur, but we know an earthquake is inevitable here, and we know it will be catastrophic.

Shulz details some predictive horror stories of what will happen when the next big one hits the Cascadia Subduction Zone. It does seem like a bad idea to put millions of people near such a seismically volatile region. But this is the problem with our slow ape brains. As Shutz writes, “[forty] years ago, no one knew that the Cascadia subduction zone had ever produced a major earthquake. [Fifty-five] years ago, no one even knew it existed.” In 1970, Seattle was already a major city with over half a million people.

So the question is, what do we do now? The low end of state estimates of fatalities from the next major earthquake is in the tens of thousands. One answer would be to move millions of people away from the danger zone. No one is proposing this. The other is to build as much infrastructure as possible to handle the incoming crisis through seismic retrofitting and social infrastructure for tsunami evacuation protocols and earthquake preparedness. The work involves building systems to keep damage as small as possible, even though the damage will be unavoidably large. As Freedman and Stark say, “probabilities are a distraction.”

Subscribe now

By Ben Recht

TR26-181 | List Decoding, Linear Hashing, and Furstenberg over $\mathbb{F}_q$ | Vinayak Kumar, Geoffrey Mon

from ECCC Papers

We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field $\mathbb{F}_q$. 1. Random linear codes over $\mathbb{F}_q$ with rate $1 - H_q(p) - \epsilon$ are $(p, O(q H_q(p)/\epsilon))$-list decodable with high probability for all values of $p, q, \epsilon$, including the high error regime. This nearly matches the list size lower bound of $H_q(p)/\epsilon$ due to Guruswami, Li, Mosheiff, Resch, Silas, and Wootters [IEEE Trans. Inf. Theory 2022]. Our bound is the first uniform improvement for $q > 2$ since Guruswami, Håstad, and Kopparty [STOC 2010]. 2. Linear hash functions over $\mathbb{F}_q$ hashing $n$ balls to $n$ bins achieve maximum load $O(q \ln \ln q / {\ln q}) \cdot \ln n / {\ln \ln n}$, both in expectation and with probability $1-o(1)$. This nearly matches the lower bound of $\ln n / {\ln \ln n}$. Previously, only a polylogarithmic upper bound was known for $q > 2$, due to Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos [J. ACM 1999]. We reduce list decodability and linear hashing to strong Furstenberg set lower bounds, which we prove using a new polynomial method of multiplicity gaps. While previous polynomial methods analyze a set $S$ by studying polynomials that vanish on it, we consider polynomials that vanish everywhere, but with higher multiplicity inside $S$ than outside.
We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field $\mathbb{F}_q$. 1. Random linear codes over $\mathbb{F}_q$ with rate $1 - H_q(p) - \epsilon$ are $(p, O(q H_q(p)/\epsilon))$-list decodable with high probability for all values of $p, q, \epsilon$, including the high error regime. This nearly matches the list size lower bound of $H_q(p)/\epsilon$ due to Guruswami, Li, Mosheiff, Resch, Silas, and Wootters [IEEE Trans. Inf. Theory 2022]. Our bound is the first uniform improvement for $q > 2$ since Guruswami, Håstad, and Kopparty [STOC 2010]. 2. Linear hash functions over $\mathbb{F}_q$ hashing $n$ balls to $n$ bins achieve maximum load $O(q \ln \ln q / {\ln q}) \cdot \ln n / {\ln \ln n}$, both in expectation and with probability $1-o(1)$. This nearly matches the lower bound of $\ln n / {\ln \ln n}$. Previously, only a polylogarithmic upper bound was known for $q > 2$, due to Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos [J. ACM 1999]. We reduce list decodability and linear hashing to strong Furstenberg set lower bounds, which we prove using a new polynomial method of multiplicity gaps. While previous polynomial methods analyze a set $S$ by studying polynomials that vanish on it, we consider polynomials that vanish everywhere, but with higher multiplicity inside $S$ than outside.

Alef’s corner: AI and Percolation

from Gil Kalai

 

 

By Gil Kalai

TR26-180 | A Resolution of Friedgut's Conjecture on Influential Coalitions | Eshan Chattopadhyay, Mohit Gurumukhani

from ECCC Papers

We prove that, for every constant $\varepsilon>0$ and every function $f:\Sigma^n\to\{0, 1\}$, there is a coalition of $O(n/\sqrt{\log n})$ coordinates and a target output $b\in\{0, 1\}$ such that, after the remaining coordinates are sampled uniformly and independently, the coalition can choose its values to make the output equal to $b$ with probability at least $1-\varepsilon$. The bound is independent of the alphabet size and also holds for monotone Boolean functions on $[0,1]^n$, resolving a conjecture of Friedgut (Combinatorics, Probability and Computing, 2004). Unlike the Boolean cube setting, where Kahn, Kalai, and Linial (FOCS, 1988) give a coalition bound of $O(n/\log n)$, no sublinear bound independent of the alphabet size was previously known. In collective coin flipping, our result gives the first sublinear bound on the number of bad players needed to force a fixed output with probability at least $1-\varepsilon$ in any one-round protocol with independent uniform messages, regardless of the message length. A key ingredient in our proof is an encoding that lets us relate the influence of a function on a product space to the $p$-biased influence of the encoded function. We then rely on a structure theorem of Hatami (Annals of Mathematics, 2012) for functions with small $p$-biased influence to bias the encoded function.
We prove that, for every constant $\varepsilon>0$ and every function $f:\Sigma^n\to\{0, 1\}$, there is a coalition of $O(n/\sqrt{\log n})$ coordinates and a target output $b\in\{0, 1\}$ such that, after the remaining coordinates are sampled uniformly and independently, the coalition can choose its values to make the output equal to $b$ with probability at least $1-\varepsilon$. The bound is independent of the alphabet size and also holds for monotone Boolean functions on $[0,1]^n$, resolving a conjecture of Friedgut (Combinatorics, Probability and Computing, 2004). Unlike the Boolean cube setting, where Kahn, Kalai, and Linial (FOCS, 1988) give a coalition bound of $O(n/\log n)$, no sublinear bound independent of the alphabet size was previously known. In collective coin flipping, our result gives the first sublinear bound on the number of bad players needed to force a fixed output with probability at least $1-\varepsilon$ in any one-round protocol with independent uniform messages, regardless of the message length. A key ingredient in our proof is an encoding that lets us relate the influence of a function on a product space to the $p$-biased influence of the encoded function. We then rely on a structure theorem of Hatami (Annals of Mathematics, 2012) for functions with small $p$-biased influence to bias the encoded function.

Achieving perfect completeness for one- and two-message quantum proof systems

from arXiv: Computational Complexity

Authors: Yupan Liu, Thomas Vidick

While quantum interactive proof systems using at least three messages can achieve perfect completeness, as shown by Kitaev and Watrous (STOC 2000), whether perfect completeness is achievable for one- and two-message quantum proof systems has remained open. For the one-message case, whether $\sf QMA$ can achieve perfect completeness was posed as an open problem in Watrous (FOCS 2000) and Aharonov and Naveh (2002); for the two-message case, the corresponding problems were (implicitly) posed in Jain, Upadhyay, and Watrous~(FOCS 2009) and Kobayashi, Le Gall, and Nishimura (SICOMP, 2019). In this work, we establish that ${\sf QIP}(2)$, ${\rm qq}\text{-}{\sf QAM}$, $\sf QAM$, and $\sf QMA$ can achieve perfect completeness. Here ${\rm qq}\text{-}{\sf QAM}$ denotes the class of promise problems admitting two-message quantum-public-coin quantum interactive proof systems in which the verifier's only message consists of half-EPR pairs. Our main technical contributions are the follows: 1. For $\sf QMA$ (and directly for $\sf QAM$), an exactly constructible block-encoded matrix whose kernel certifies yes instances, constructed from the acceptance operator induced by the verification circuit. 2. For ${\sf QIP}(2)$ (and implicitly ${\rm qq}\text{-}{\sf QAM}$), a new turn-halving transformation that preserves completeness and ensures that the resulting proof system retains at least two messages, provided that the terminal state before the final measurement is efficiently preparable.

Authors: Yupan Liu, Thomas Vidick

While quantum interactive proof systems using at least three messages can achieve perfect completeness, as shown by Kitaev and Watrous (STOC 2000), whether perfect completeness is achievable for one- and two-message quantum proof systems has remained open. For the one-message case, whether $\sf QMA$ can achieve perfect completeness was posed as an open problem in Watrous (FOCS 2000) and Aharonov and Naveh (2002); for the two-message case, the corresponding problems were (implicitly) posed in Jain, Upadhyay, and Watrous~(FOCS 2009) and Kobayashi, Le Gall, and Nishimura (SICOMP, 2019). In this work, we establish that ${\sf QIP}(2)$, ${\rm qq}\text{-}{\sf QAM}$, $\sf QAM$, and $\sf QMA$ can achieve perfect completeness. Here ${\rm qq}\text{-}{\sf QAM}$ denotes the class of promise problems admitting two-message quantum-public-coin quantum interactive proof systems in which the verifier's only message consists of half-EPR pairs. Our main technical contributions are the follows: 1. For $\sf QMA$ (and directly for $\sf QAM$), an exactly constructible block-encoded matrix whose kernel certifies yes instances, constructed from the acceptance operator induced by the verification circuit. 2. For ${\sf QIP}(2)$ (and implicitly ${\rm qq}\text{-}{\sf QAM}$), a new turn-halving transformation that preserves completeness and ensures that the resulting proof system retains at least two messages, provided that the terminal state before the final measurement is efficiently preparable.

NP-hardness of ideal lattice problems

from arXiv: Computational Complexity

Authors: Daniel E. Martin

We establish the worst-case hardness of several ideal lattice problems (including SVP and CVP) in the $\ell_2$ norm by providing a dimension-preserving, deterministic polynomial time reduction from their generic lattice versions. The reduction constructs an ideal lattice in the canonical embedding of a number field that approximates some input lattice up to scaling and orthogonal transformation. The integers defining the ideal and the ambient number ring, in particular its discriminant, are all polynomial in bit length relative to the generic input lattice. Furthermore, the ideal is invertible, the ring is monogenic, and the number field is totally real. If the number ring is also required to be a full ring of integers, the reduction conjecturally succeeds in bounded-error quantum polynomial time.

Authors: Daniel E. Martin

We establish the worst-case hardness of several ideal lattice problems (including SVP and CVP) in the $\ell_2$ norm by providing a dimension-preserving, deterministic polynomial time reduction from their generic lattice versions. The reduction constructs an ideal lattice in the canonical embedding of a number field that approximates some input lattice up to scaling and orthogonal transformation. The integers defining the ideal and the ambient number ring, in particular its discriminant, are all polynomial in bit length relative to the generic input lattice. Furthermore, the ideal is invertible, the ring is monogenic, and the number field is totally real. If the number ring is also required to be a full ring of integers, the reduction conjecturally succeeds in bounded-error quantum polynomial time.

Randomized query complexity can beat certificate complexity

from arXiv: Computational Complexity

Authors: Shalev Ben-David, Robin Kothari

A long-standing open question in query complexity asks whether there is a total Boolean function f with R(f) << C(f), where R(f) and C(f) denote its bounded-error randomized query complexity and certificate complexity, respectively. We construct a function with R(f) = O~(sqrt{C(f)}), which is optimal up to log factors. The same function also has $Q(f) = O~(C(f)^{1/4}), where Q(f) is the bounded-error quantum query complexity of f, which is also nearly optimal.

Authors: Shalev Ben-David, Robin Kothari

A long-standing open question in query complexity asks whether there is a total Boolean function f with R(f) << C(f), where R(f) and C(f) denote its bounded-error randomized query complexity and certificate complexity, respectively. We construct a function with R(f) = O~(sqrt{C(f)}), which is optimal up to log factors. The same function also has $Q(f) = O~(C(f)^{1/4}), where Q(f) is the bounded-error quantum query complexity of f, which is also nearly optimal.

The Exact Growth Rate of Space-Optimal Reversible Pebbling on Chains

from arXiv: Computational Complexity

Authors: Tetsuo Yokoyama

We determine the exact time exponent of space-optimal reversible pebbling on chains as $1.331742379256310\ldots$. The growth rate of space-optimal reach exists as a limit and admits a variational formula. The same exponent governs complete computations at minimal space, uniformly in the chain length.

Authors: Tetsuo Yokoyama

We determine the exact time exponent of space-optimal reversible pebbling on chains as $1.331742379256310\ldots$. The growth rate of space-optimal reach exists as a limit and admits a variational formula. The same exponent governs complete computations at minimal space, uniformly in the chain length.

Nullstellensatz degree under Hajós joins and vertex identifications

from arXiv: Computational Complexity

Authors: Ying Xie

We study the minimum coefficient degree $N_{k,\F}(G)$ of a Nullstellensatz certificate for Bayer's $k$-coloring equations, where the characteristic of $\F$ does not divide $k$. If $J$ is a \HJ\ join of non-$k$-colorable graphs $G,H$ and $m=\max\{N_{k,\F}(G),N_{k,\F}(H)\}$, then $N_{k,\F}(J)\leq m+k$. When deletion of the selected edge makes each input $k$-colorable, we also have $N_{k,\F}(J)\geq m$; the degree congruence then gives $N_{k,\F}(J)\in\{m,m+k\}$. This partially answers a question of Li, Lowenstein, and Omar. For three-coloring over $\F_2$, we construct an infinite $4$-critical family of exact degree seven, attaining the bound at input degree four. In contrast, every graph constructed from $K_4$ solely by \HJ\ joins has degree $O(\log n)$ and a certificate with polynomially many terms: joins preserve treewidth at most three, and balanced separators yield low-degree certificates. Additional vertex identifications are excluded from this obstruction. We classify all single identifications of the $25$-vertex base graph; exactly $36$ preserve degree seven, producing $24$-vertex $4$-critical graphs of treewidth four. A compressed self-join at adjacent true twins prevents degree loss and gives a repeatable rule adding four vertices per round. The rule does not establish degree amplification or preservation of criticality. Exact witnesses and standalone verification programs accompany the finite results.

Authors: Ying Xie

We study the minimum coefficient degree $N_{k,\F}(G)$ of a Nullstellensatz certificate for Bayer's $k$-coloring equations, where the characteristic of $\F$ does not divide $k$. If $J$ is a \HJ\ join of non-$k$-colorable graphs $G,H$ and $m=\max\{N_{k,\F}(G),N_{k,\F}(H)\}$, then $N_{k,\F}(J)\leq m+k$. When deletion of the selected edge makes each input $k$-colorable, we also have $N_{k,\F}(J)\geq m$; the degree congruence then gives $N_{k,\F}(J)\in\{m,m+k\}$. This partially answers a question of Li, Lowenstein, and Omar. For three-coloring over $\F_2$, we construct an infinite $4$-critical family of exact degree seven, attaining the bound at input degree four. In contrast, every graph constructed from $K_4$ solely by \HJ\ joins has degree $O(\log n)$ and a certificate with polynomially many terms: joins preserve treewidth at most three, and balanced separators yield low-degree certificates. Additional vertex identifications are excluded from this obstruction. We classify all single identifications of the $25$-vertex base graph; exactly $36$ preserve degree seven, producing $24$-vertex $4$-critical graphs of treewidth four. A compressed self-join at adjacent true twins prevents degree loss and gives a repeatable rule adding four vertices per round. The rule does not establish degree amplification or preservation of criticality. Exact witnesses and standalone verification programs accompany the finite results.

Linear equations mod $n$ are pseudo-telepathic

from arXiv: Computational Complexity

Authors: Lorenzo Ciardo

We prove that the quantum monad in dimension $2n$ admits no natural transformation to the polymorphism clone of linear equations modulo $n$. Consequently, for every $n\geq 2$, there exists an unsatisfiable system of linear equations over $\mathbb{Z}_n$ whose constraint system game admits a perfect finite-dimensional quantum strategy. As a corollary, we completely characterise pseudo-telepathic constraint languages in finite dimension. The proof combines a result of Harding, Jager, and Smith on group-valued measures on subspaces of Hilbert spaces with the polymorphism-minion characterisation of quantum pseudo-telepathy.

Authors: Lorenzo Ciardo

We prove that the quantum monad in dimension $2n$ admits no natural transformation to the polymorphism clone of linear equations modulo $n$. Consequently, for every $n\geq 2$, there exists an unsatisfiable system of linear equations over $\mathbb{Z}_n$ whose constraint system game admits a perfect finite-dimensional quantum strategy. As a corollary, we completely characterise pseudo-telepathic constraint languages in finite dimension. The proof combines a result of Harding, Jager, and Smith on group-valued measures on subspaces of Hilbert spaces with the polymorphism-minion characterisation of quantum pseudo-telepathy.

Explicit unbalanced 1-expanders with small degree and right size

from arXiv: Computational Complexity

Authors: Bruno Bauwens, Marius Zimand

An explicit graph is given with left size $N$, left degree $\widetilde O(\log^2 N)$, right size $(1+o(1))K$ and $1$-expansion up to~$K$, meaning that every left subset of size $K' \le K$ has at least $K'$ neighbors. Let $\C(x)$ be the minimal length of a program that prints~$x$ (i.e., the central concept in Kolmogorov complexity). The $1$-expander is used to obtain an algorithm that on input $x$ computes in time $\poly(|x|)$ a list with $\widetilde O(|x|^3)$ programs such that at least 1 program prints $x$ and has length $\C(x) + O(1)$. This improves on the $O(|x|^{6+\eps})$ upper bound in~\cite{zim:c:shortlistshortproof} and is close to the $Ω(|x|^2)$ lower bound from~\cite[theorem 4]{bmvz:j:shortlist}. In the companion paper ``Online matching games in bipartite expanders: applications to data structures," the $1$-expander is used to obtain dynamic dictionaries in which the query operation has non-adaptive memory access.

Authors: Bruno Bauwens, Marius Zimand

An explicit graph is given with left size $N$, left degree $\widetilde O(\log^2 N)$, right size $(1+o(1))K$ and $1$-expansion up to~$K$, meaning that every left subset of size $K' \le K$ has at least $K'$ neighbors. Let $\C(x)$ be the minimal length of a program that prints~$x$ (i.e., the central concept in Kolmogorov complexity). The $1$-expander is used to obtain an algorithm that on input $x$ computes in time $\poly(|x|)$ a list with $\widetilde O(|x|^3)$ programs such that at least 1 program prints $x$ and has length $\C(x) + O(1)$. This improves on the $O(|x|^{6+\eps})$ upper bound in~\cite{zim:c:shortlistshortproof} and is close to the $Ω(|x|^2)$ lower bound from~\cite[theorem 4]{bmvz:j:shortlist}. In the companion paper ``Online matching games in bipartite expanders: applications to data structures," the $1$-expander is used to obtain dynamic dictionaries in which the query operation has non-adaptive memory access.

New lower bounds on tensor rank of $(2,n,m)$ matrix multiplication with GPT-6

from arXiv: Computational Complexity

Authors: Jason Yang

The tensor rank of $2\times n$-with-$n\times m$ matrix multiplication is at least $(n+2)m$ if $n\ge 4$ and at least $\left\lceil \frac{24}{5}m \right\rceil$ if $n=3$. Both lower bounds apply over arbitrary fields.

Authors: Jason Yang

The tensor rank of $2\times n$-with-$n\times m$ matrix multiplication is at least $(n+2)m$ if $n\ge 4$ and at least $\left\lceil \frac{24}{5}m \right\rceil$ if $n=3$. Both lower bounds apply over arbitrary fields.

Torsion detection in clique complexes is conditionally $QMA_1$-hard

from arXiv: Computational Complexity

Authors: Adam Wesołowski

Quantum algorithms for topological data analysis compute Betti numbers, the ranks of the homology groups of a simplicial complex, which can be read off from the kernel of a combinatorial Laplacian. Deciding whether a Betti number of a clique complex is nonzero is $QMA_1$-hard, and remains so under a spectral gap promise on vertex-weighted graphs. Integral homology, however, contains information inaccessible to the Laplacian spectrum. A new part that appears in integral homology is torsion: cycles that become boundaries only after being traversed several times, as in a projective plane or a Klein bottle. We ask how hard it is to detect torsion, and we answer with a simple reduction. We attach to an arbitrary clique complex a fixed $31$-vertex triangulation of the projective plane. The $k$th mod-$2$ Betti number of the input then reappears as $2$-torsion two degrees up, while all rational homology disappears and every combinatorial Laplacian acquires a constant spectral gap. We conclude that detecting torsion in clique complexes of unweighted graphs is $NP$-hard, even under a constant gap promise, and that it is $QMA_1$-hard if mod-$2$ clique homology is.

Authors: Adam Wesołowski

Quantum algorithms for topological data analysis compute Betti numbers, the ranks of the homology groups of a simplicial complex, which can be read off from the kernel of a combinatorial Laplacian. Deciding whether a Betti number of a clique complex is nonzero is $QMA_1$-hard, and remains so under a spectral gap promise on vertex-weighted graphs. Integral homology, however, contains information inaccessible to the Laplacian spectrum. A new part that appears in integral homology is torsion: cycles that become boundaries only after being traversed several times, as in a projective plane or a Klein bottle. We ask how hard it is to detect torsion, and we answer with a simple reduction. We attach to an arbitrary clique complex a fixed $31$-vertex triangulation of the projective plane. The $k$th mod-$2$ Betti number of the input then reappears as $2$-torsion two degrees up, while all rational homology disappears and every combinatorial Laplacian acquires a constant spectral gap. We conclude that detecting torsion in clique complexes of unweighted graphs is $NP$-hard, even under a constant gap promise, and that it is $QMA_1$-hard if mod-$2$ clique homology is.

On the Complexity of Finding Fixed Points for Set-Valued Contractions

from arXiv: Computational Complexity

Authors: Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong

In this paper, we study the computational complexity of finding fixed points for set-valued contractions. We first formulate a computational problem for Nadler's fixed-point theorem: Projected-Nadler, and prove that it is $\mathsf{CLS}$-complete by showing its equivalence to Continuous-LocalOpt. We then establish a stronger converse for Nadler's fixed point theorem that can be applied as a tool to analyze the convergence rate of set-valued basic iteration procedure. Finally, we reduce large-margin triplet stationarity problem to Projected-Nadler. Together with its $\mathsf{CLS}$-hardness introduced in [arXiv:2509.16898], this yields $\mathsf{CLS}$-completeness of large-margin triplet stationarity.

Authors: Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong

In this paper, we study the computational complexity of finding fixed points for set-valued contractions. We first formulate a computational problem for Nadler's fixed-point theorem: Projected-Nadler, and prove that it is $\mathsf{CLS}$-complete by showing its equivalence to Continuous-LocalOpt. We then establish a stronger converse for Nadler's fixed point theorem that can be applied as a tool to analyze the convergence rate of set-valued basic iteration procedure. Finally, we reduce large-margin triplet stationarity problem to Projected-Nadler. Together with its $\mathsf{CLS}$-hardness introduced in [arXiv:2509.16898], this yields $\mathsf{CLS}$-completeness of large-margin triplet stationarity.

Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification

from arXiv: Computational Complexity

Authors: Jiarui Yao, Jiaxi Zhao, Xiangxin Zhou

In the best-arm identification problem, we are given $n$ stochastic arms with unknown means and wish to identify the arm with the largest mean with probability at least $1-δ$, using as few samples as possible. We consider independent Gaussian rewards with unit variance and means in $[0,1]$. Chen and Li [2016] conjectured that the instance-wise sample complexity of this problem is characterized by the gap entropy, up to an additive term arising from the two-arm problem. In this paper, we resolve their gap-entropy and almost instance-wise optimality conjectures. For an instance $I$, let $Δ_{[i]}$ be the gap between the largest and the $i$-th largest mean, let $H(I)=\sum_{i=2}^{n}Δ_{[i]}^{-2}$, and let Ent$(I)$ denote the entropy of the normalized complexities of its dyadic gap groups. For every $0<δ<0.1$, we show that the order-oblivious instance-wise lower bound is $ Θ (H(I)[\log(1/δ)+Ent(I)]). $ We also give a single $δ$-correct algorithm with expected sample complexity $ O ( H(I)[\log(1/δ)+Ent(I)] +D\log(e+\log(e+D))),D=Δ_{[2]}^{-2}, $ without prior knowledge of the gaps. Our lower bound removes the dyadic-gap and monotonicity restrictions of previous work, and our upper bound removes the additional polylogarithmic factor multiplying the two-arm term. Thus, a single algorithm attains the instance-wise lower bound up to an additive two-arm term. The main theorems have been formalized and proved in Lean 4.

Authors: Jiarui Yao, Jiaxi Zhao, Xiangxin Zhou

In the best-arm identification problem, we are given $n$ stochastic arms with unknown means and wish to identify the arm with the largest mean with probability at least $1-δ$, using as few samples as possible. We consider independent Gaussian rewards with unit variance and means in $[0,1]$. Chen and Li [2016] conjectured that the instance-wise sample complexity of this problem is characterized by the gap entropy, up to an additive term arising from the two-arm problem. In this paper, we resolve their gap-entropy and almost instance-wise optimality conjectures. For an instance $I$, let $Δ_{[i]}$ be the gap between the largest and the $i$-th largest mean, let $H(I)=\sum_{i=2}^{n}Δ_{[i]}^{-2}$, and let Ent$(I)$ denote the entropy of the normalized complexities of its dyadic gap groups. For every $0<δ<0.1$, we show that the order-oblivious instance-wise lower bound is $ Θ (H(I)[\log(1/δ)+Ent(I)]). $ We also give a single $δ$-correct algorithm with expected sample complexity $ O ( H(I)[\log(1/δ)+Ent(I)] +D\log(e+\log(e+D))),D=Δ_{[2]}^{-2}, $ without prior knowledge of the gaps. Our lower bound removes the dyadic-gap and monotonicity restrictions of previous work, and our upper bound removes the additional polylogarithmic factor multiplying the two-arm term. Thus, a single algorithm attains the instance-wise lower bound up to an additive two-arm term. The main theorems have been formalized and proved in Lean 4.

Certified local rank and uniqueness barriers for a 48-term matrix-multiplication decomposition

from arXiv: Computational Complexity

Authors: Abhinav Agarwal

We study replacements in fixed bilinear tensor decompositions, counting changes to complete rank-one summands, including output factors. The shortening frontier records the maximum rank defect of a fixed-size subset and determines the minimum length attainable within a change budget. For the rational 48-term Li--Wang--Hu decomposition \(D(2)\) of \(4\times4\) matrix multiplication over \(\mathbb{C}\), we prove rank radius at least 12, strong radius exactly 11, and border radius at least 8. Every shorter complex decomposition therefore changes at least thirteen original summands. An exact rational twelve-term replacement attains the equal-length barrier. The proofs combine exhaustive support reductions with saturated projected kernels and zero-corner completion arguments controlling arbitrary minimal competitors. A reduced-incidence argument transfers kernel certificates to tensor-space neighborhoods. A Laurent normal form gives strong radius exactly 11 for the sixteen-term core at every nonzero complex parameter. On a nonempty Zariski-open subset of the actual parameter curve, the rank radius is at least 12, the strong radius exactly 11, and the border radius at least 8. We also prove incomparability of the full Kothari--Moitra--Wein sufficient criterion and the Sylvester-equipped kernel criterion. These results describe local decomposition structure rather than a new rank bound for full matrix multiplication.

Authors: Abhinav Agarwal

We study replacements in fixed bilinear tensor decompositions, counting changes to complete rank-one summands, including output factors. The shortening frontier records the maximum rank defect of a fixed-size subset and determines the minimum length attainable within a change budget. For the rational 48-term Li--Wang--Hu decomposition \(D(2)\) of \(4\times4\) matrix multiplication over \(\mathbb{C}\), we prove rank radius at least 12, strong radius exactly 11, and border radius at least 8. Every shorter complex decomposition therefore changes at least thirteen original summands. An exact rational twelve-term replacement attains the equal-length barrier. The proofs combine exhaustive support reductions with saturated projected kernels and zero-corner completion arguments controlling arbitrary minimal competitors. A reduced-incidence argument transfers kernel certificates to tensor-space neighborhoods. A Laurent normal form gives strong radius exactly 11 for the sixteen-term core at every nonzero complex parameter. On a nonempty Zariski-open subset of the actual parameter curve, the rank radius is at least 12, the strong radius exactly 11, and the border radius at least 8. We also prove incomparability of the full Kothari--Moitra--Wein sufficient criterion and the Sylvester-equipped kernel criterion. These results describe local decomposition structure rather than a new rank bound for full matrix multiplication.

Asymmetric Weighted Earliness-Tardiness: Scheduling with a Nonrestrictive Common Due Date

from arXiv: Computational Complexity

Authors: Nicholas G. Hall, Hans Kellerer, Miao Song

Single-machine asymmetric weighted earliness--tardiness (AWET) scheduling asks how to sequence jobs around a common synchronization date when early and late completion incur unrelated job-dependent penalties. At the boundary nonrestrictive date $d=\sum_jp_j$, a compact V-shaped schedule reduces the continuous-time problem to a quadratic choice of a nonempty early set. We establish four complementary results for this model. First, the positive-integer problem is strongly NP-complete by a unary-polynomial reduction from Restricted Exact Cover by 3-Sets. Second, unrestricted AWET admits a polynomial-time $(3+2\sqrt2+\varepsilon)$-approximation based on an anchored semidefinite relaxation and deterministic marginal thresholding. Third, when the earliness and tardiness ratio orders are strict reversals, the problem is weakly NP-complete but has an exact two-resource pseudopolynomial dynamic program. Fourth, for fixed total refinements whose ratio permutation is separable, an exact separating-tree recurrence and coordinated geometric trimming yield an FPTAS. The proofs use different manifestations of the same canonical objective: scale-separated prefix penalties, positive-semidefinite minimum-kernel covariance, a dominant completed load square, and a bounded four-coordinate decomposition interface. Together, the results show that the decisive issue is not merely whether the two ratio orders agree, but whether their interaction can be controlled by a global certificate or compressed into a bounded constructive interface.

Authors: Nicholas G. Hall, Hans Kellerer, Miao Song

Single-machine asymmetric weighted earliness--tardiness (AWET) scheduling asks how to sequence jobs around a common synchronization date when early and late completion incur unrelated job-dependent penalties. At the boundary nonrestrictive date $d=\sum_jp_j$, a compact V-shaped schedule reduces the continuous-time problem to a quadratic choice of a nonempty early set. We establish four complementary results for this model. First, the positive-integer problem is strongly NP-complete by a unary-polynomial reduction from Restricted Exact Cover by 3-Sets. Second, unrestricted AWET admits a polynomial-time $(3+2\sqrt2+\varepsilon)$-approximation based on an anchored semidefinite relaxation and deterministic marginal thresholding. Third, when the earliness and tardiness ratio orders are strict reversals, the problem is weakly NP-complete but has an exact two-resource pseudopolynomial dynamic program. Fourth, for fixed total refinements whose ratio permutation is separable, an exact separating-tree recurrence and coordinated geometric trimming yield an FPTAS. The proofs use different manifestations of the same canonical objective: scale-separated prefix penalties, positive-semidefinite minimum-kernel covariance, a dominant completed load square, and a bounded four-coordinate decomposition interface. Together, the results show that the decisive issue is not merely whether the two ratio orders agree, but whether their interaction can be controlled by a global certificate or compressed into a bounded constructive interface.

Multi-Stage NeRF for Efficient 3D Coronary Artery Reconstruction from Two Narrow-Angle Angiographic Projections

from arXiv: Computational Geometry

Authors: Deyu Meng, Mojtaba Lashgari, Yiying Wang, Abhirup Banerjee

X-ray coronary angiography is the clinical gold standard for coronary artery disease during real-time cardiac interventions, but provides only 2D projections of inherently 3D vessels. Existing learning-based 2D-to-3D reconstruction methods typically require wide angular coverage or multiple views, assumptions that are rarely satisfied in routine practice where only two projections with narrow angular separation are available. To address these challenges, we propose NeCA++, a multi-stage self-supervised neural radiance field (NeRF) framework tailored to clinically realistic acquisition constraints. The framework decomposes reconstruction into two stages that progressively refine spatial support and representation capacity. In the first stage, a coarse 3D representation of the vasculature is reconstructed, restricting the subsequent optimisation to regions with a higher likelihood of vessel presence, termed an active region. Afterward reconstruction is restricted to this region while higher-resolution representations are progressively activated to recover fine vascular details. This multi-stage strategy focuses learning on anatomically plausible regions, mitigates gradient dilution under extreme sparsity, and stabilises global topology before recovering fine vascular branches. Furthermore, two vessel-specific regularisations are introduced: a ray-aligned constraint to reduce projection-induced ambiguity, and a bimodal density penalty to enable early vessel-background separation. Extensive experiments across three datasets (ImageCAS, ASOCA, and Synthetic RCA) and four angular configurations demonstrate consistent superiority over state-of-the-art baselines, particularly under clinically realistic narrow-angle settings, while achieving reconstruction within 58 seconds per case.

Authors: Deyu Meng, Mojtaba Lashgari, Yiying Wang, Abhirup Banerjee

X-ray coronary angiography is the clinical gold standard for coronary artery disease during real-time cardiac interventions, but provides only 2D projections of inherently 3D vessels. Existing learning-based 2D-to-3D reconstruction methods typically require wide angular coverage or multiple views, assumptions that are rarely satisfied in routine practice where only two projections with narrow angular separation are available. To address these challenges, we propose NeCA++, a multi-stage self-supervised neural radiance field (NeRF) framework tailored to clinically realistic acquisition constraints. The framework decomposes reconstruction into two stages that progressively refine spatial support and representation capacity. In the first stage, a coarse 3D representation of the vasculature is reconstructed, restricting the subsequent optimisation to regions with a higher likelihood of vessel presence, termed an active region. Afterward reconstruction is restricted to this region while higher-resolution representations are progressively activated to recover fine vascular details. This multi-stage strategy focuses learning on anatomically plausible regions, mitigates gradient dilution under extreme sparsity, and stabilises global topology before recovering fine vascular branches. Furthermore, two vessel-specific regularisations are introduced: a ray-aligned constraint to reduce projection-induced ambiguity, and a bimodal density penalty to enable early vessel-background separation. Extensive experiments across three datasets (ImageCAS, ASOCA, and Synthetic RCA) and four angular configurations demonstrate consistent superiority over state-of-the-art baselines, particularly under clinically realistic narrow-angle settings, while achieving reconstruction within 58 seconds per case.

Low-Dimensional Embeddings for Gaussian Kernels on Manifolds

from arXiv: Computational Geometry

Authors: Soumik Dutta, Kunal Dutta

The Gaussian kernel is a widely used similarity measure underlying kernel methods such as kernel PCA and spectral clustering, but computing Gaussian kernel distances for many pairs of points can be expensive. Using Random Fourier Features (RFF), Chen and Phillips [ALT 2017] showed that for points in a $d$-dimensional Euclidean ball in ${\mathbb R}^N$, $t=Ω((d/\varepsilon^2)\log(dR/\varepsilon))$ features suffice to preserve all pairwise Gaussian kernel distances within a $(1\pm\varepsilon)$ factor with high probability. We establish a uniform relative-error embedding theorem for the more general setting of an arbitrary positive-reach submanifold $\mathcal M\subset{\mathbb R}^N$ of intrinsic dimension $d$. We show that $t=O((d/\varepsilon^2)\log(\operatorname{vol}(\mathcal M)^2N^{2d}/(\operatorname{vol}(B_1^d(0))^2\operatorname{rch}(\mathcal M)^{2d}\varepsilon^{2d+1}δ)))$, or approximately $O((d^2/\varepsilon^2)(\log N+\log(1/(\varepsilonδ))))$, RFFs suffice, with probability $1-δ$, to preserve the Gaussian kernel distance between every pair of manifold points up to relative error $\varepsilon$. Thus the bound depends only logarithmically on the ambient dimension and on manifold parameters such as volume and reach, while retaining the $1/\varepsilon^2$ Euclidean rate. We also prove a topological consequence: under the same RFF embedding, persistent homology is preserved in the sense that weighted Cech and Rips filtrations built from Gaussian kernel power distance are $(1\pm\varepsilon_\star)$-interleaved, where $\varepsilon_\star$ accounts for both distance distortion and kernel-weight approximation.

Authors: Soumik Dutta, Kunal Dutta

The Gaussian kernel is a widely used similarity measure underlying kernel methods such as kernel PCA and spectral clustering, but computing Gaussian kernel distances for many pairs of points can be expensive. Using Random Fourier Features (RFF), Chen and Phillips [ALT 2017] showed that for points in a $d$-dimensional Euclidean ball in ${\mathbb R}^N$, $t=Ω((d/\varepsilon^2)\log(dR/\varepsilon))$ features suffice to preserve all pairwise Gaussian kernel distances within a $(1\pm\varepsilon)$ factor with high probability. We establish a uniform relative-error embedding theorem for the more general setting of an arbitrary positive-reach submanifold $\mathcal M\subset{\mathbb R}^N$ of intrinsic dimension $d$. We show that $t=O((d/\varepsilon^2)\log(\operatorname{vol}(\mathcal M)^2N^{2d}/(\operatorname{vol}(B_1^d(0))^2\operatorname{rch}(\mathcal M)^{2d}\varepsilon^{2d+1}δ)))$, or approximately $O((d^2/\varepsilon^2)(\log N+\log(1/(\varepsilonδ))))$, RFFs suffice, with probability $1-δ$, to preserve the Gaussian kernel distance between every pair of manifold points up to relative error $\varepsilon$. Thus the bound depends only logarithmically on the ambient dimension and on manifold parameters such as volume and reach, while retaining the $1/\varepsilon^2$ Euclidean rate. We also prove a topological consequence: under the same RFF embedding, persistent homology is preserved in the sense that weighted Cech and Rips filtrations built from Gaussian kernel power distance are $(1\pm\varepsilon_\star)$-interleaved, where $\varepsilon_\star$ accounts for both distance distortion and kernel-weight approximation.

Flip Graphs for Eight Points in Three Dimensions Are Connected

from arXiv: Computational Geometry

Authors: Marc Khoury

We prove that every configuration of four through eight points in three-dimensional space, with no four points coplanar, has a connected full geometric flip graph under $2 \leftrightarrow 3$ flips. Every point remains fixed and present throughout the sequence. The proof brings each tetrahedralization into placing form at a convex hull vertex: the tetrahedra not incident to that vertex fill the convex hull of the remaining points. This reduction allows us to establish connectivity by induction, using the connectivity of regular tetrahedralizations. The main geometric tool is radial projection, which turns the tetrahedra incident to a hull vertex into a planar triangulation. When this planar triangulation is regular, varying its lifting heights produces legal spatial flips that progressively shrink the region occupied by the incident tetrahedra and reach placing form. Planar lifting criteria and compatibility constraints between the projections at different hull vertices resolve the remaining small cases. For eight points, at most 35 flips are needed to reach placing form.

Authors: Marc Khoury

We prove that every configuration of four through eight points in three-dimensional space, with no four points coplanar, has a connected full geometric flip graph under $2 \leftrightarrow 3$ flips. Every point remains fixed and present throughout the sequence. The proof brings each tetrahedralization into placing form at a convex hull vertex: the tetrahedra not incident to that vertex fill the convex hull of the remaining points. This reduction allows us to establish connectivity by induction, using the connectivity of regular tetrahedralizations. The main geometric tool is radial projection, which turns the tetrahedra incident to a hull vertex into a planar triangulation. When this planar triangulation is regular, varying its lifting heights produces legal spatial flips that progressively shrink the region occupied by the incident tetrahedra and reach placing form. Planar lifting criteria and compatibility constraints between the projections at different hull vertices resolve the remaining small cases. For eight points, at most 35 flips are needed to reach placing form.

Planar-faced and high-Jacobian two-refinement hexahedral templates

from arXiv: Computational Geometry

Authors: Hua Tong, Yongjie Jessica Zhang

Automatically generating high-quality conforming hexahedral (hex) meshes from general input boundaries remains a challenging problem, despite the numerical advantages hex elements offer in simulation. Grid-based adaptive refinement, followed by hanging-node removal, is the most robust fully automatic choice. Among two-refinement methods, primal templates have better mesh quality than dual templates but depend on a strong balancing condition that over-refines the grid; neither family guarantees planar quadrilateral (quad) faces. This paper generalizes recent primal three-refinement templates to a two-refinement scheme under a moderate balancing condition, a relaxation of the strong one. 32 special and five fundamental patterns resolve all 144 symmetry-reduced configurations, followed by either a fast greedy algorithm or an integer linear programming (ILP) algorithm that trades extra runtime for a further reduction in element count. The scheme is the first two-refinement method in which all hexes have planar faces, and its meshes feed directly into a recent quality-guaranteed hex mesh reconstruction algorithm. At comparable element counts, it attains a similar Hausdorff ratio (HR) and a higher minimum scaled Jacobian (min SJ) than its three-refinement counterpart.

Authors: Hua Tong, Yongjie Jessica Zhang

Automatically generating high-quality conforming hexahedral (hex) meshes from general input boundaries remains a challenging problem, despite the numerical advantages hex elements offer in simulation. Grid-based adaptive refinement, followed by hanging-node removal, is the most robust fully automatic choice. Among two-refinement methods, primal templates have better mesh quality than dual templates but depend on a strong balancing condition that over-refines the grid; neither family guarantees planar quadrilateral (quad) faces. This paper generalizes recent primal three-refinement templates to a two-refinement scheme under a moderate balancing condition, a relaxation of the strong one. 32 special and five fundamental patterns resolve all 144 symmetry-reduced configurations, followed by either a fast greedy algorithm or an integer linear programming (ILP) algorithm that trades extra runtime for a further reduction in element count. The scheme is the first two-refinement method in which all hexes have planar faces, and its meshes feed directly into a recent quality-guaranteed hex mesh reconstruction algorithm. At comparable element counts, it attains a similar Hausdorff ratio (HR) and a higher minimum scaled Jacobian (min SJ) than its three-refinement counterpart.

Computing the minimal perimeter polygon for digital objects in the triangular tiling

from arXiv: Computational Geometry

Authors: Petra Wiederhold

This work presents an algorithm, together with its correctness proof, to determine the minimum perimeter polygon (MPP) for digital objects given as regular complexes in the triangular plane tiling. Such objects are edge-adjacency-connected sets of triangle tiles that have no end tiles, and the point set union of all their tiles forms a simple polygon. Nevertheless, the boundary paths of the objects are not assumed to be simple. Then the MPP is a weakly simple polygon that coincides with the relative convex hull (i.e., geodesic hull) of a set $A$ with respect to a simple polygon $B$, where $A\subset B$, but $A$ is not necessarily a polygon, in fact it is generally not connected. Our MPP algorithm relies on constructing and iteratively constraining cones of visibility through forthcoming boundary tiles, it uses the structure of the canonical boundary path, the MPP frontier is the shortest polygonal curve following this path. We also propose a boundary tracing algorithm to obtain such paths from the objects.

Authors: Petra Wiederhold

This work presents an algorithm, together with its correctness proof, to determine the minimum perimeter polygon (MPP) for digital objects given as regular complexes in the triangular plane tiling. Such objects are edge-adjacency-connected sets of triangle tiles that have no end tiles, and the point set union of all their tiles forms a simple polygon. Nevertheless, the boundary paths of the objects are not assumed to be simple. Then the MPP is a weakly simple polygon that coincides with the relative convex hull (i.e., geodesic hull) of a set $A$ with respect to a simple polygon $B$, where $A\subset B$, but $A$ is not necessarily a polygon, in fact it is generally not connected. Our MPP algorithm relies on constructing and iteratively constraining cones of visibility through forthcoming boundary tiles, it uses the structure of the canonical boundary path, the MPP frontier is the shortest polygonal curve following this path. We also propose a boundary tracing algorithm to obtain such paths from the objects.