Theory of Computing Report

When you start thinking deeply about a mathematics problem you may enter the "zone", a period of intense focus where you think solely about the problem and potential solutions, and more importantly block out all other thoughts and even lose track of time. Mathematicians don't own the zone, actors, musicians, athletes and many others have their own version of the zone. But for math, when working on an open problem, you have no idea how difficult a solution may be, or if a solution exists at all. Most of the time you will fail (if not you need to try harder problems). Failure is not wasted time. You may find a counterexample, a partial solution and always you will come out with a better understanding of the problem. Then days, months or years later, some new proof idea comes from a paper, a talk or just the back of your head, and back in the zone you go. And when you do succeed you get a feeling not unlike scoring a goal in a soccer game. You should see my proof dance.

With AI generated and assisted proofs, we may think of outsourcing the zone to ChatGPT and Claude. We may prove more and stronger theorems, but you'll understand the results just a little bit less and mathematics will become a little less fun. 

By Lance Fortnow

Authors: Nikita Gaevoy

Resolution with symmetries is a natural extension of the Resolution proof system that allows to use symmetries of the formula to simplify the proof. Symmetries can be global (applied to the whole input formula), local (applied to a subformula), or dynamic (applied to newly derived clauses as well). The framework of Resolution with (global) symmetries was introduced by Krishnamurthy (1985) and further extended by Arai and Urquhart (2000) to local symmetries. Later, Szeider (2005) generalized this approach to homomorphisms and introduced the notion of Resolution with dynamic symmetries. While proving superpolynomial proof-size lower bounds for Resolution with dynamic symmetries remains an open problem already for two decades, the power of proof systems with global and local symmetries is well studied: exponential lower bounds have been proven for these proof systems, as well as exponential separations between all of them. However, these systems are too general to reflect practical applications since it is computationally too hard to find and efficiently exploit arbitrary symmetries. In this work, we introduce the notion of small symmetries: symmetries that can operate on a limited number of variables at the same time. Resolution with small symmetries gives hopes both for practical applications and for theoretical study of dynamic symmetries. We show that proof systems with both local and global small symmetries form strict hierarchies w.r.t. the size of symmetries. We prove exponential separations between proof systems with symmetries of different sizes and types. It turns out that even lower levels of these hierarchies are exponentially separated from Resolution and stronger proof systems, such as constant-depth Frege. As a byproduct of our constructions, we obtain an exponential separation between the classical systems SRCI and SRII that was not known before.

Authors: Marcel K. Goh, Hamed Hatami

We construct a point-line incidence problem over the reals whose randomized communication complexity is constant, but whose deterministic communication complexity is linear even when the players have access to an equality oracle. This is the strongest possible separation between these two measures, and it improves on an earlier $O(1)$-versus-$Ω(\sqrt{n})$ separation of Göös, Harms, and Riazanov. Because point-line incidence problems have constant sign rank, our construction also bears on a question of Harms and Zamaraev, who asked whether constant sign rank together with constant randomized communication complexity forces constant equality-oracle complexity. This was already refuted by Göös, Harms, Imbach, and Sokolov with a logarithmic lower bound; our example improves the separation to linear, which is optimal. The proof draws on a construction in the recent disproof of the sum-product conjecture over the reals by Bloom, Sawin, Schildkraut, and Zhelezov, using totally real number fields of large degree and small discriminant.

Authors: Peter Bürgisser

We study the logical relation of the P-NP separation conjecture in the Blum-Shub-Smale-model over the complex numbers with the P-NP separation conjecture in Valiant's algebraic model. This amounts to comparing Hilbert's Nullstellensatz Problem, that is, deciding feasibility of a given system of polynomial equations over the complex numbers, with the problem of evaluating the permanent of a given complex matrix. We compare the respective uniform models of computations and prove that $P_C\ne NP_C$ in the Blum-Shub-Smale-model over $C$ implies the separation $VP^0(u)\ne VNP^0(u)$ of the uniform versions of Valiant's constant-free complexity classes over $C$. For the nonuniform models we show the analogous implication: the separation $P^0_C(nu)\ne NP^0_C(nu)$ of the nonuniform, constant-free Blum-Shub-Smale classes over $C$ implies the separation $VP^0\ne VNP^0$ of Valiant's constant-free complexity classes over $C$. In the reverse direction, we conjecture that $VNP_C\not\subseteq\overline{VP}_C$ implies that $P_C(nu)\ne NP_C(nu)$.

Authors: Nikolas Gärtner, Victor Magron, Frank Vallentin

In this paper, we analyze the bit complexity of deciding whether a given polynomial can be represented as a sum of squares of polynomials. We show that the weak membership problem for the sum-of-squares cone lies in $\mathrm{P}$. Furthermore, we give a polynomial-time algorithm which computes, for a given polynomial and positive parameter $ε$, an $ε$-relaxed closest sum-of-squares polynomial.

Authors: Qisheng Wang

We consider the problem of estimating the fidelity of an unknown quantum state to a known reference state to within additive error $\varepsilon$. We show that the sample complexity is $O(r^2/\varepsilon^2)$ with optimal $\varepsilon$-dependence when the reference state is of rank $r$, improving the previous best $O(r^2\log^2(1/\varepsilon)/\varepsilon^4)$ due to Utsumi, Nakata, Wang, and Takagi (QIP 2026). We also provide a lower bound of $Ω(r/\varepsilon^2)$, improving the previous best $Ω(r/\varepsilon+1/\varepsilon^2)$, with implications to quantum query complexity. Moreover, we further consider the case where the unknown state is of rank at most $r$ while the reference state can be arbitrary, for which the sample complexity is shown to be $O(r^2/\varepsilon^4)$. As an application, we present an approach to tolerant quantum state certification, generalizing the exact certification studied in Bădescu, O'Donnell, and Wright (STOC 2019).

Authors: Barna Saha, Yinzhan Xu, Christopher Ye

Several fundamental problems in computational geometry admit algorithms with running time $f(d) \cdot n^{2-Θ(1/d)}$ for $n$ points in $d$ dimensions, making them among the most prominent examples of barely subquadratic computation. Notable members of this class include Furthest Pair, Bichromatic Closest Pair, (Bichromatic) Maximum Innter Product, and Hopcroft's Problem. Chen [Theory Comput. 2020] proved that, assuming the Strong Exponential Time Hypothesis (SETH), these problems require $n^{2-o(1)}$ time when the dimension satisfies $d=2^{Θ(\log^* n)}$. We extend this lower bound to all efficiently constructible dimensions $d=ω(1)$. Thus, assuming SETH, the dependence of the best known algorithms on the dimension is essentially unavoidable. The proof utilizes techniques in OpenAI's recent disproof of the Erdos unit distance conjecture. The proof was initially discovered by ChatGPT 5.5 Pro. The authors have validated and substantially edited the proof to improve the presentation.

Authors: Raphaël Tinarrage

We analyze the decrease of simplex diameters under iterated refinement of spherical Delaunay complexes. Unlike in ordinary subdivision, the refined Delaunay complex need not be a subdivision of the previous one, so mesh contraction is not automatic. We derive explicit contraction bounds for several families of Steiner points, including Delaunay analogues of barycentric and edgewise subdivision. The proof reduces the problem to sharp covering estimates for Euclidean simplices. These estimates are obtained through a strengthening of Maurey's empirical method via pivotal sampling and a dimension-dependent version of the approximate Carathéodory theorem. Theoretical results and numerical experiments show that Delaunay refinements achieve stronger contraction than their subdivision counterparts.

Authors: David Eppstein, Zahra Hadizadeh

We construct a convex polygon for which the minimum-weight Steiner triangulation requires an interior Steiner point. This provides a counterexample to a 1994 conjecture of Eppstein that minimum-weight Steiner triangulation of convex polygons needs only Steiner points on the boundary of the polygon.

Authors: Satoshi Kanno, Yoshi-aki Shimada

Topological information is widely used in data analysis, network design, and machine learning, and topological constraints naturally arise when optimizing or generating objects with prescribed homological structure. However, directly controlling Betti numbers and persistent homology is difficult because they are discrete and combinatorial. We propose a differentiable framework for topology-constrained optimization based on Hodge-spectral relaxations of homological constraints and low-pass spectral filters. From soft graphs and soft clique complexes, we construct Hodge-Laplacian-type spectral relaxations that unify graph clique complexes and Vietoris--Rips filtrations of point clouds. In the hard limit, the penalty-regularized ambient operator recovers the ordinary Hodge Laplacian on the active subcomplex, while in the soft regime it serves as a differentiable low-frequency spectral surrogate. Homological information is represented by zero and near-zero modes, and differentiable topological objectives are defined using heat filters, resolvent filters, and polynomial Laplacian moments. For point clouds, we show that the proposed Hodge spectral-filter losses yield more spatially distributed gradients, smoother scale-normalized behavior under persistence-pairing changes, and geometry-aware update directions than persistent-homology-based losses. For graph clique complexes, Laplacian moments control normalized first-Betti-type quantities and can be combined with ordinary graph-feature objectives. We also discuss connections to trace-based normalized Betti-number estimation, polynomial spectral methods, and possible quantum trace estimation.

Authors: Anna Brötzner, Omrit Filtser, Bengt J. Nilsson, Christian Rieck, Christiane Schmidt

Motivated by applications for robust guarding, we consider a variant of the multiple-watchmen problem that ensures that every point within a polygon $P$ is seen from more than one direction: we search for two routes $W_1,W_2$, such that every point $p\in P$ is contained in a segment $\overline{w_1w_2}\subseteq P$ such that $w_1\in W_1$ and $w_2\in W_2$. We call such routes segment watchman routes. We show that finding the two routes that are optimal with respect to the min-max criterion is weakly NP-hard even in simple polygons, and that finding the routes that are optimal with respect to the min-sum criterion is NP-hard in polygons with holes. Moreover, we present sufficient conditions for routes to be segment watchman routes, and provide a polynomial-time $2$-approximation under both the min-max criterion and the min-sum criterion, both in simple polygons. Finally, we show how to generalize our results for $k$ watchmen.

Authors: Yuanhao Wang, Wei Wang

Let $n$ and $p$ denote the numbers of vertices and labels, respectively, in an undirected edge-labeled graph. Previous work showed that, under the Exponential Time Hypothesis (ETH), there is no deterministic algorithm with running time \[ (np)^{o\left(\frac{\log n}{(\log\log n)^2}\right)}. \] In this paper, we give a deterministic reduction that strengthens this conditional running-time lower bound to \[ (np)^{o\left(\frac{\log n}{\log\log n}\right)}. \]

Authors: Thekla Hamm, Bart M. P. Jansen, Faezeh Motiei

We study generalizations of the Steiner Tree problem motivated by the design of power networks. While Steiner Tree asks for a single minimum-cost tree connecting given terminal vertices, a power network typically consists of multiple trees, each connecting a subset of the terminals, to avoid electrical overloads. The cost of installing depends on both the cable lengths and the cost of digging underground trenches for putting the cables where the digging costs can be shared. These leads to variants of Steiner Tree where the goal is to compute a minimum-cost set of Steiner trees with a common root, that together connect all terminals while balancing the power demand of the terminals in each tree. Two important variants arise depending on whether the network is intended for low-voltage or high-voltage power. In the low-voltage case, power loss imposes a bound on the maximum depth of each tree, while no such restriction applies in the high-voltage case. We study the parameterized complexity of several power network design problems, parameterized by the number of terminals. While Steiner Tree is fixed-parameter tractable under this parameterization, most of our variants are W[1]-hard. For low-voltage networks, we present an XP-algorithm for planar inputs based on structural bounds on the treewidth of solution subgraphs. We also give a reduction from Grid Tiling showing tightness under ETH. The XP-algorithm extends to the high-voltage setting and general graphs, albeit at a cost in the running time. For high-voltage networks, we show the problem remains W[1]-hard even on planar graphs. Finally, we explore a variant of the cost model for sharing digging costs in which both problems become fixed-parameter tractable.

Authors: Yu Chen, Zihan Tan

We study the following distance realization problem: given a metric $D$ on a set $T$ of terminals, does there exist an (edge-weighted) outerplanar graph $G$, such that $T\subseteq V(G)$, and for every pair $t,t'\in T$, $\textsf{dist}_G(t,t')=D(t,t')$? We first prove that there is no ``local characterization'', forming a contrast with trees and Okamura-Seymour instances. Our main result is an efficient algorithm for this problem whose running time is polynomial in $|T|$. Both our proof and our algorithm utilize a recent new approach of analyzing graph structures, by viewing graphs as paths and their intersections, which we believe is of independent interest.

Authors: Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov, Miltiadis Stouras, Ola Svensson

We initiate a resource-aware theory of \textit{language generation in the limit} under the minimal constraint of space efficiency. In our framework, a learner observes an adversarial positive stream from a target language $K$ and must eventually output a hallucination-free hypothesis language $L \subseteq K$ while omitting at most $Δ$ strings of $K$. We focus on $\mathcal{C}_{s,k}$, the collection of languages recognized by DFAs with at most $s$ states over an alphabet of size $k$, as the natural hypothesis class for memory-bounded learners. In the exponential-space regime, we prove that a learner can exactly identify the target $K$. Under a stricter memory budget, we characterize the strongest possible generation guarantees. In particular, we present a streaming algorithm using $\mathrm{poly}(s,k)$ space that converges to a hypothesis with generation gap $Δ= O(k^{2s-2})$. Moreover, the learned hypothesis captures every string in $K$ of length at least $2s-1$. We complement this result with a near-matching lower bound through a reduction from a standard communication complexity problem. Specifically, achieving generation gap $Δ\le k^{(1-\varepsilon)s}$ requires $k^{Ω(\varepsilon s)}$ memory. Together, these results reveal a sharp transition between polynomial-space generation and exponential-space exact identification.

Authors: Shimon Kogan, Merav Parter

The multi-source reachability problem asks to compute the reachable sets from a given subset of source vertices. For $n$-vertex digraphs $G=(V,E)$ and a subset of sources $S \subseteq V$ with $|S|=n^σ$ for some $σ\in [0,1]$, we present a near-optimal deterministic algorithm that solves this problem in $\tilde{O}(n^{ω(σ)})$ time, where $ω(σ)$ is the rectangular matrix multiplication exponent for multiplying an $n^σ\times n$ matrix by an $n \times n$ matrix. For dense graphs, this yields reachability from up to $n^{0.32}$ sources in near-linear time, breaking the super-quadratic time barrier and improving over the state-of-the-art $n^{1+2/3ω(σ)}$-time randomized algorithm of Elkin and Trehan [arXiv:2401.05628, 2024].

Authors: Felix Buld, Andreas S. Schulz

We study scheduling with testing on a single machine and on identical parallel machines to minimize the total \emph{weighted} completion time in the adversarial model. In this setting, each job is equipped with a weight, an upper bound on its processing time, and a testing time. An algorithm can either execute a job for an amount of time equal to the upper bound or test it first to reveal a potentially lower processing time used to schedule the job later. We establish the first constant-competitive algorithms for this problem with job-dependent weights that reflect each job's relative importance. For single-machine scheduling, we present a deterministic algorithm with a competitive ratio of 2.3166 and show that a randomized variant has a competitive ratio of 2.1523. These guarantees match the best-known upper bounds in the unweighted setting. Combining these algorithms with list scheduling yields competitive ratios of 2.7763 and 2.5110 for identical-parallel-machine scheduling, improving the previously best-known bounds even in the unweighted case.

Authors: Jakob Raupach, Tom-Lukas Breitkopf, Anton Herrmann, André Nichterlein

We explore the parameterized complexity of Bounded Density Vertex Deletion (BDVD): given a graph $G$, an integer budget $k$, and a target density $τ_ρ$, the task is to determine whether the density (i.e. number of edges divided by number of vertices) of the densest subgraph of $G$ can be reduced to at most $τ_ρ$ by deleting at most $k$ vertices. Our primary focus is on structural graph parameters related to treewidth, as the parameterized complexity of BDVD with respect to treewidth was left as open question by Bazgan et al. [JCSS, 2025]. We resolve this question by showing W[1]-hardness with respect to various parameters, including treedepth and feedback vertex number. These results imply W[1]-hardness with respect to treewidth. We obtain positive results for parameters larger than treedepth and feedback vertex number, namely we show BDVD is in FPT parameterized by the max leaf number or vertex integrity. Under the assumption that the target density $τ_ρ$ is a fixed constant the parameterized complexity landscape of BDVD changes drastically, allowing a fixed-parameter tractable algorithm even for parameters smaller than treewidth, namely cliquewidth. Altogether, our results provide a refined complexity landscape for Bounded Density Vertex Deletion, sharply distinguishing between tractable and intractable parameter regimes under structural parameterizations.

We study depth-$5$ algebraic circuits over small finite fields with restricted fan-in of the top product gates. We show that there exists an explicit degree-$d$ polynomial $P(\mathbf{x})$ such that any $\Sigma \Pi^{[\mathrm{poly(d)}]} \Sigma \Pi \Sigma$ circuit, computing $P(\mathbf{x})$, over a small finite field, requires size $2^{\Omega(\sqrt{d})}$. Our work builds upon and strengthens the work of [Kumar-Saptharishi'19], who showed $2^{\Omega(\sqrt{d})}$ lower bounds against $\Sigma \Pi^{[\mathcal{O}(\sqrt{d})]} \Sigma \Pi \Sigma$ circuits over small finite fields. It is known that proving $2^{\omega(d^{1/3} \log n)}$ lower bound for $\Sigma \Pi^{[a]} \Sigma \Pi$ circuits with $a = 2^{\mathcal{O}(d^{1/3} \log d)}$, over fields of characteristic $0$, implies VP $\neq$ VNP. In pursuit of this, we also prove superpolynomial lower bounds over small finite fields for $\Sigma \Pi^{[a]} \Sigma \Pi$ circuits where $a = 2^{\mathcal{O}(d^{\lambda} \log d)}$, for any constant $\lambda < 1/3$. We use evaluations of the shifted partial derivatives to prove our lower bounds. We follow the same outline as [Kumar-Saptharishi'19], but with a more delicate analysis of the complexity measure. We use a family of the Nisan-Wigderson polynomials as a hard polynomial. We show that over small finite fields, setting the parameters of our measure and the hard polynomial with care, the method of shifted partial derivatives can yield lower bounds well beyond the homogeneity restriction on depth-$4$ circuits. We also show an exponential gap between depth-$3$ and homogeneous depth-$4$ circuits over small finite fields. Previously, only a superpolynomial gap was known using [Chillara-Mukhopadhyay'17] and depth reduction of polynomials in VP until homogeneous depth-$4$. We use the complexity measure of [Grigoriev-Karpinski'98], and we use the Product of the Inner Product polynomial to show the separation.

Authors: Dean Doron, Tal Leonov, Jonathan Mosheiff, Henrique Navas, Nicolas Resch, João Ribeiro

We prove that random linear codes have nearly optimal discrepancy properties in a broad range of regimes. Our main results are two general theorems: one controlling all translates of a fixed test, and another controlling large families of Fourier-pseudorandom tests. Two motivating applications follow. First, random linear codes match unstructured random codes for list-decoding from errors above capacity. If $C\subseteq\mathbb F_q^n$ is a random linear code of rate $1-\frac1n\log_q |B_ρ|+ε$, where $B_ρ$ is a radius-$ρ$ Hamming ball, then with high probability $$ |C\cap B|=(1\pm o(1))\frac{|C||B|}{q^n} $$ simultaneously for all radius-$ρ$ Hamming balls $B\subseteq\mathbb F_q^n$. This extends the classical result that such codes have covering radius at most $ρn$ whp (Blinovsky, 1987). Second, over prime fields, random linear codes match unstructured random codes for zero-error list-recovery above capacity. For prime $q>2$ and $2\le \ell\le q-1$, a random linear code of rate $1-\log_q\ell+ε$ satisfies, with high probability, $$ |C\cap S|=(1\pm o(1))\frac{|C|\ell^n}{q^n} $$ simultaneously for all rectangles $S=S_1\times\cdots\times S_n$ with $|S_i|=\ell$. As a consequence, there are abundant $n$-party linear ramp secret sharing schemes over $\mathbb F_q$ with privacy threshold about $n/(2\log q)$ and reconstruction threshold about $5n/(2\log q)$, resilient to balanced local leakage; prior existence results required thresholds above $n/2$ even in this case. The translate result, hence the list-decoding application, holds over arbitrary finite fields, even growing with $n$. The list-recovery and leakage applications hold over prime fields under moderate growth, e.g. $q\le n^{1/5-o(1)}$. The proofs use a refined second-moment analysis tracking intersection sizes as random generators are added to $C$.

Authors: Rosemary U. Adejoh, Andreas Jakoby, Sneha Mohanty, Christian Schindelhauer

We establish that the two-dimensional ray tracing problem with thin lenses and plane mirrors is Turing-complete, thereby resolving an open question posed by Reif et al. in 1994 as to whether three-dimensional space is necessary for computational universality in optical systems. To this end, we consider the standard approximation of reflection and refraction, namely the ABCD model for paraxial optics, which describes ray propagation through lenses (refraction) via a 2 x 2 matrix, combined with the geometric reflection model for plane mirrors. In the absence of mirrors, two-dimensional ray tracing using any combination of lenses in this ABCD matrix model can be described by a single 2 x 2 matrix-vector product, where the matrix has real entries and determinant 1. Conversely, we show that any such matrix with determinant 1 can be represented as a composition of exactly three appropriately spaced thin lenses. When mirrors are combined with lenses, the ray tracing problem can be described by a flowchart using only two variables, which establishes Turing computability for rational-valued inputs, spaces and matrix entries. Building on this observation, we present a construction of ray tracing that simulates a reversible Turing machine. We begin with a restricted version of the reversible flowchart problem, in which only two variables and certain linear functions are permitted. We prove that this restricted variant is Turing-complete. We then show that such a flowchart admits a geometric realization using lenses and mirrors in our model, thereby establishing the main result: Turing-completeness of the two-dimensional ray tracing problem with ABCD-model lenses and mirrors.

Authors: Jie Wang

Wang~\cite{Wang2026} introduced the Stochastic-Oracle Turing Machine (SOTM) framework and defined token complexity as the minimum expected cost of interacting with a stochastic oracle needed to attain a specified solution quality for a task. This paper develops an analogous notion for certifying the reliability of a stochastic oracle on a given domain. Certification token complexity is the minimum expected token cost required, with controlled error probability, to distinguish oracles that meet a target reliability level from those that fall below a lower reliability threshold. We construct an SPRT-based certification SOTM that queries the oracle, computes binary correctness scores, and stops when the accumulated log-likelihood evidence crosses a decision threshold. The SOTM halts almost surely, satisfies the desired two-sided error guarantee over the reliability regions to be certified, and yields an explicit upper bound on certification token complexity in terms of the reliability thresholds, the error bound, and the expected per-turn token cost. We then establish a matching information-theoretic lower bound: even with adaptive queries, every error-bounded certification SOTM must incur the same leading-order expected token cost as the SPRT-based construction as the prescribed error bound tends to zero. Together, these bounds characterize the leading-order certification token complexity in the small-error regime.

Authors: Louis Desruisseaux, Simon Ducharme, Gurleen Padda, Dave Touchette

For many information processing tasks, de Finetti-style theorems can often simplify the analysis in worst-case input scenarios for which the task exhibits some permutation-invariance symmetry, as they can allow for a reduction from an analysis on worst-case inputs to that of i.i.d. inputs. If further information is available on the inputs, it might be advantageous to reflect this information in the de Finetti reduction. In our work, we focus on a form of such constraint, based on the type of the input. This allows us to obtain a conceptually simple proof of a new de Finetti reduction for classical probability distributions, derived from elementary properties from the method of types. We apply our constrained de Finetti reduction to the compression of quantum interactive communication protocols with classical inputs, and prove that the prior-free quantum information cost equals the worst-case input amortized quantum communication cost.

Authors: Fabien Feschet, Jacques-Olivier Lachaud

Full convexity is an interesting alternative to classical digital convexity since it guarantees connectedness and even simple connectedness in digital spaces Z d , for any dimension d. This paper aims at giving a better understanding of the monotonicity properties of fully convex digital sets, since earlier works showed that the question was difficult for thin fully convex sets. To decipher the hierarchy of fully convex sets ordered by inclusion, we study how we can peel a fully convex set progressively while keeping its full convexity. We provide a characterization of peelable points and fast algorithms to identify them. Furthermore we show that fully convex set can be peeled one point at a time till reduced to the empty set, similarly to digitally convex sets in the classical sense. The peeling of a fully convex set can be seen as an analog to homotopic thinning processes, but with an additional geometric property.

Authors: Barbara Giunti, Elizabeth Munch

In this paper, we provide a new construction for studying parameterized persistence, called a canopy. We give two versions of this construction: the A-canopy, retaining all information about points on the diagonal of the persistence diagram; and the D-canopy, encoding the information of the "standard" persistence diagram. We do this by making a simple but major modification in the persistence bundle representation information: namely, rather than tracking a point in the persistence diagram, we instead track some choice of pairs of simplices that created said point. This viewpoint is a combinatorial version of tracking the chain complex information rather than just the output of persistence. We show how to construct the canopies from any filtered filtration function, proving, using the algebraic structure of filtered chain complexes, that different choices of pairs result in homeomorphic structures. Finally, we showcase the power of our approach by using canopies to define vines even in the presence of points with multiplicity; to discuss monodromy; and to obtain some immediate results linking non-trivial monodromy in the persistent homology transform with the existence of non-Hausdorff points in the canopy.

Authors: Sanjeev Khanna, Aaron Putterman, Junkai Song

We settle the classic question of the parallel complexity of computing a matroid basis, as first posed in the seminal work of Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988). Our algorithm runs in $O(n^{1/3}\log^{1/3}n)$ rounds, matching the lower bound of KUW up to a $\log^{2/3}(n)$ factor.

Authors: Juul Sanders, Sebastiaan Brand, Arend-Jan Quist, Tim Coopmans

The decision diagram (DD) data structure enables fast linear-algebra calculations by bringing vectors into a normal form and subsequently merging equivalent ones, yielding a minimally-sized DD modulo the equivalence relation. A fruitful application area is quantum-circuit simulation, where the vectors represent quantum states. The Local Invertible Map Decision Diagram (LIMDD) type, merges LIM-equivalent (typically Pauli-gate equivalent) vectors, can efficiently simulate Clifford circuits as well as some high-T-count circuits, and has theoretically been proven exponentially faster for simulation than other well-developed data structures, including other common DD variants. However, these exponential advantages have not fully materialized yet in existing implementations, for which the normal-form procedure, which is a highly complex algorithm, is either absent or only partially implemented. We here present a novel normal-form algorithm for Pauli-LIMDDs, achieving a worst-case speedup from $O(n^3)$ to $O(n^2)$ for an $n$-qubit DD node with a single child node while keeping the $O(n^3)$ run time in case of two distinct children nodes. We implement the algorithm as part of QolDDer, our Pauli-LIMDD simulator for quantum circuits, written from scratch in C/C++. The implementation realizes the theoretically-proven advantages of Pauli-LIMDDs on Clifford circuits, is significantly faster than the existing LIMDD simulators on such circuits, and on a public quantum-circuit data set often outperforms them by an order of magnitude. In the future, we envision that our work will enable further application and development of LIMDD variants, not only for quantum design tasks, but also for analysis of linear-algebra-based systems in general.

Authors: Nicolas Gast, Bruno Gaujal, Adrien Obrecht

In this paper we consider a M/G/1 queue for which we want to minimize the expected response time. We show how to compute indices from $n$ samples of the job size distribution such that the corresponding index policy is asymptotically optimal as $n$ grows. This construction is based on a discretization of the bounded support of the job size distribution and a shift of the samples to their nearest discrete point to the right. We show that the Gittins index of the empirical distribution of these shifted samples is close to the Gittins index of the original distribution. This translates to the asymptotic optimality of the corresponding index policy for minimizing the expected response time. Numerical comparison with other approaches further confirm the efficiency of our approach.

Authors: Minghao Chen, Jiale Zheng

Spectral filtering recently delivered substantial pruning for \emph{static} subgraph matching: Laplacian interlacing rejects candidates whose neighborhoods cannot host the query. We study whether such aggregate structural tests can accelerate \emph{continuous} subgraph matching (CSM) over dynamic graphs, and answer in three parts. First, lazily maintained spectral bounds are infeasible exactly where spectral pruning has value: we characterize the tightest safe rule over a formalized perturbation relaxation and show that even it loses essentially all pruning power within four touching updates. Second, exact maintenance is affordable when selective: pruning utility and recomputation cost are anti-correlated across vertices -- hubs provably never prune -- so recomputing small-neighborhood spectra on touch sustains exact local spectra at microseconds per update, complete by construction. Third, integrated into a decoupled CSM benchmark against an identical-minus-spectra control, the tests remove up to $51\%$ of candidates or safely skip up to $47\%$ of update enumerations, yet enumeration intermediates remain unchanged -- beyond the gates' skipped first-level bindings, typically zero -- across two engines, four real graphs, two stream types, and $77$ solved queries; a constructed radius-stratified workload confirms the instrument detects the exception when one exists ($-99.9\%$ intermediates, $748\times$ faster). Aggregate tests accelerate what scales with candidate sets -- construction, list scans -- never adjacency-guided exploration. We distill an intermediate-invariance methodology for evaluating CSM filters and release a reusable dynamic local-spectra index.

Authors: Tim Dortmann, Markus Vieth, Bertil Schmidt

Efficient genomic k-mer indexing depends on approximate membership query (AMQ) structures that must deliver high throughput, low false-positive rates (FPR), and modest memory footprints. The Super Bloom filter (SBF) is attractive for this scenario because minimizer-guided sharding and the Findere scheme exploit the redundancy of overlapping k-mers. However, those same features cause high per-k-mer compute cost, severe register pressure, and irregular memory accesses, which hinder an effective GPU implementation. We present cuSBF, an open-source, header-only CUDA library that implements SBF for sequence-native workloads. cuSBF's design merges sectorized shards, cooperative shared-memory tiling, warp-level shard sharing, and segmented warp reductions, turning super-k-mer locality into scalable GPU parallelism. Across real genomic workloads on RTX PRO 6000 Blackwell and GH200 systems, cuSBF achieves the highest throughput among all evaluated sequence-capable baselines. On the RTX PRO 6000, it surpasses the cuCollections blocked Bloom filter baseline by up to 9.1x for insertion and 7.7x for query, while reaching up to 92x and 234x speedups over the multi-threaded CPU Super Bloom reference implementation. It also outperforms GPU-based dynamic AMQs (Cuckoo, Two-Choice, Quotient filters) by 1.5-3400x depending on workload characteristics. A parameter sweep identifies (s = 28, m = 16, H = 4) as Pareto-optimal for k = 31, yielding significantly lower FPR than cuCollections at matched memory budgets. Crucially, cuSBF's architecture-aware design sustains 85% streaming multiprocessor utilization even for out-of-cache filters - proving that sequence locality, not raw bandwidth, is the key to GPU-accelerated genomic indexing.

Authors: Enoch Peserico, Michele Scquizzato

In any real system a newly computed datum begins its existence in the processor rather than in external memory, and thus does not inevitably incur a cold miss. This was captured by early I/O models, but not by the Sleator-Tarjan one that has come to underpin competitive analysis of paging. If one corrects the Sleator-Tarjan model by charging no cost for the first access to newly computed data, optimal offline algorithms such as LFD remain optimal, but no online paging algorithm can be competitive, even if randomized, even with arbitrary resource augmentation, even against request sequences that are not tailored against it but are instead representative of widely used computational techniques. The proofs are simple, and appear robust against any reasonable assumption/model adjustment, including virtually all tools developed to make competitive analysis less pessimistic. In other words, while competitive analysis does predict the good performance exhibited in practice by online paging algorithms such as LRU, these predictions seem just a fortuitous artifact of an incorrect assumption that has crept into the underlying model several decades ago. And there are implications beyond paging, too: for example, the same issue undermines the Ideal Cache model on which the popular Cache-Oblivious and Cache-Adaptive algorithmic frameworks are based.

Authors: Martin Darmüntzel, Christian Rosenke, Mark Scheibner

Flood-It is a single-player game played on a precolored graph $G$, where the objective is to make $G$ monochromatic using as few flooding moves as possible. In each move, a color $c$ is selected and all vertices reachable from a fixed pivot vertex via a monochromatic path are recolored with $c$. In the free variant, the pivot may be chosen anew in every move. Deciding whether a graph can be made monochromatic in at most $k$ moves is NP-complete for both variants, fixed and free. This hardness persists even under strong structural restrictions such as split graphs and trees. The Free Flood-It variant is generally considered more difficult than its fixed-pivot counterpart, as it remains hard on several graph classes where the latter becomes tractable, including co-comparability and AT-free graphs. Cographs, that is, $P_4$-free graphs, are among the few classes on which even Free Flood-It is solvable in polynomial time and therefore serve as our starting point. We consider the ten natural one-vertex extensions of $P_4$ -- referred to as jewels -- and study the complexity of both flooding games on the $1024$ graph classes obtained by forbidding subsets of these graphs as induced subgraphs. Our main contribution is a polynomial-time algorithm for Free Flood-It on graphs that are free of the three jewels bull, gem, and $P_5$, covering $128$ of the $1024$ classes. In addition, we prove that both variants remain NP-complete on thin-spider graphs, which exclude the eight jewels banner, co-banner, chair, gem, house, kite, $P_5$, and $C_5$, thereby establishing hardness for $256$ additional classes. Combined with known algorithms and hardness results, our work determines the complexity of both Flood-It variants for $896$ of the $1024$ considered graph classes.

David Richter, a mathematician at Western Michigan University, recently found himself with a surfeit of ceramic orthogonal polyhedra and, knowing of my own interest in orthogonal polyhedra, generously offloaded two of them to me. They fit nicely in my office together with the paper and crochet orthogonal polyhedra I already had:

The blue one is an orthogonal realization of Boy’s surface, an immersion of the projective plane into three-dimensional space with three-way symmetry and a single triple crossing point. The idea to make an orthogonal version comes from Jean Pierre Petit’s Le Topologicon, where its relation to the usual curved version can maybe be seen more clearly than in my photographs.

The model hides a hidden graph embedding: the uncolored edges form the boundaries of a hemi-dodecahedron, an embedding of the Petersen graph with six pentagonal faces, each adjacent to all five others.

The other ceramic model, colored yellow, green, and red, is an orthogonal realization of the permutohedron or, almost the same thing, the Cayley graph of the four-element symmetric group generated by the three swaps of consecutive elements. Abstractly, it’s the same embedded graph as the paper kirigami model behind it in the family portrait, which I constructed and wrote about in 2009, but what this one loses in orthogonal nonconvexity it makes up for in bilateral symmetry.

Here are a few more views of it:

When viewed top-down their shapes almost look like writing to me. You can see a signature and date in the hollow of the Boy’s surface.

Richter also has a couple of papers on orthogonal polyhedra: “Generic Orthotopes” (arXiv:2210.12012) and “Ehrhart Polynomials of Generic Orthotopes” (arXiv:2309.09026).

(Discuss on Mastodon)

By David Eppstein

My teacher and friend Dimitri Bertsekas passed away earlier this month. I just learned about this over the weekend, and I’m still processing my thoughts.

Dimitri was a hero of mine for so many reasons. I took my first and only class on optimization with him, and I was riveted by his clean presentation of convex analysis and mastery of the overhead projector. He took a liking to me, and I made it a point to find him for a chat whenever I’d visit MIT. He was always generous with his time and excited to exchange ideas, but he wouldn’t hesitate to harshly scold me when I’d present some result new to me that he had in fact written about twenty years earlier.

This was unavoidable because Dimitri did foundational work across mathematical optimization, penning landmark results in stochastic gradient descent, convex optimization, distributed optimization, dynamic programming, and reinforcement learning.

His work in reinforcement learning remains underrated. His collaboration with John Tsitsiklis, compiled in their book Neurodynamic Programming, was the first to show that most reinforcement learning algorithms were effectively approximating dynamic programming. Our contemporary, model-free mindset, rooted in Markov decision processes, derives from these initial insights. As far as actual practice goes, their book is more important to the modern way we implement reinforcement learning than Sutton and Barto’s.

Dimitri was also a passionate mathematical communicator. I own more of his books than any other mathematics researcher, but he wrote more than any other mathematics researcher in my field. Is there too much material? You could make the case! However, that he has definitive texts covering a broad range of optimization theory is remarkable.

In many ways, Dimitri was an original math blogger. He wrote exactly what he wanted to write, and he wrote frequently. He got fed up with publishers getting in the way of his process, so he started his own publishing company, Athena Scientific, shipping stacks of books out of his garage in Belmont, Massachusetts. This allowed him to write countless new editions and revisions of his work, reflecting trends in practice and incorporating new insights and simplified arguments. Though you’ll see plenty of repetition across his volumes, he knew that no book was a final draft. Each volume was a step towards broader understanding.

A decade ago, when he retired from MIT, I wrote a post of appreciation for his scholarly and pedagogical work. I’m going to reprint it here today, as it includes one of my favorite passages in his books about the tension between theory and practice. Right now, in our frenzied agentic era, we’re leaning heavily on only practice and vulgar empiricism to push out as many papers and products as we can before the bubble pops. Is there a role for theory at all anymore?

Dimitri argued that optimization theory is always a mix of qualitative and quantitative. The qualitative helps us understand what we know and don’t know. By gathering feedback from practice and constructing a working narrative, theorists can help engineers develop a language to describe what is possible and what can be improved. Theory provides a narrative scaffolding that helps us understand what to build and what to attend to when things break. Building stories of connections helps us streamline our processes and try things we might not have thought of.

There’s an ebb and flow between the theory and practice. I will revisit this ten years from now and see where the theories land.

Until then, rest in peace, Dimitri. Know you changed the way I think.

The following initially appeared as The Role of Convergence Analysis on June 10, 2016 at the old argmin blog.

This year marks the retirement of Dimitri Bertsekas from MIT. Dimitri is an idol of mine, having literally written the book on every facet of optimization. His seminal works on distributed optimization, dynamic programming, and Lagrangian methods remain the best references available. I had the privilege of taking Dimitri’s convex analysis course in grad school, and he would frequently burst into class beaming because he had stayed up until 2AM the night before simplifying an argument of Rockafellar’s down to elementary calculus.

My last post on Lagrangians was based on Chapter 3 of Dimitri’s Nonlinear Programming Book. Chapter 2 also happens to feature one of my favorite passages about the delicate balance between theory and practice in optimization. One of the trickiest parts about optimization (and a point I intend to repeatedly hammer on this blog) is realizing how many of the theorems are “qualitative” rather than “quantitative.” I wanted to just quote Dimitri’s text in full here, as I don’t think I could write it better. Best wishes to you in retirement!

The Role of Convergence Analysis by Dimitris Bertsekas

The following subsection gives a number of mathematical propositions relating to the convergence properties of gradient methods. The meaning of these propositions is usually quite intuitive but their statement often requires complicated mathematical assumptions. Furthermore, their proof often involves tedious ϵ−δ arguments, so at first sight students may wonder whether “we really have to go through all this.”

When Euclid was faced with a similar question from King Ptolemy of Alexandria, he replied that “there is no royal road to geometry.” In our case, however, the answer is not so simple because we are not dealing with a pure subject such as geometry that may be developed without regard for its practical application. In the eyes of most people, the value of an analysis or algorithm in nonlinear programming is judged primarily by its practical impact in solving various types of problems. It is therefore important to give some thought to the interface between convergence analysis and its practical application. To this end it is useful to consider two extreme viewpoints; most workers in the field find themselves somewhere between the two.

In the first viewpoint, convergence analysis is considered primarily a mathematical subject. The properties of an algorithm are quantified to the extent possible through mathematical statements. General and broadly applicable assertions, and simple and elegant proofs are at a premium here. The rationale is that simple statements and proofs are more readily understood, and general statements apply not only to the problems at hand but also to other problems that are likely to appear in the future. On the negative side, one may remark that simplicity is not always compatible with relevance, and broad applicability is often achieved through assumptions that are hard to verify or appreciate.

The second viewpoint largely rejects the role of mathematical analysis. The rationale here is that the validity and the properties of an algorithm for a given class of problems must be verified through practical experimentation anyway, so if an algorithm looks promising on intuitive grounds, why bother with a convergence analysis. Furthermore, there are a number of important practical questions that are hard to address analytically, such as roundoff error, multiple local minima, and a variety of finite termination and approximation issues. The main criticism of this viewpoint is that mathematical analysis often reveals (and explains) fundamental flaws of algorithms that experimentation may miss. These flaws often point the way to better algorithms or modified algorithms that are tailored to the type of practical problem at hand. Similarly, analysis may be more effective than experimentation in delineating the types of problems for which particular algorithms are well-suited.

Our own mathematical approach is tempered by practical concerns, but we note that the balance between theory and practice in nonlinear programming is particularly delicate, subjective, and problem dependent.

Subscribe now

By Ben Recht

I’ve been getting emails from journalists asking me to comment on the new White House executive order on quantum computing. Alas, I don’t have time for a long response or interviews since I’m at a beautiful science camp in the California mountains, and heading soon to STOC’2026 in Salt Lake City. But I gave anyone who asked me the following statement, which I thought might be of interest to readers of this blog as well.

“I hope that at least some of the new funds made available from this Executive Order will go to basic, curiosity-driven academic research — the kind that led to the idea of quantum computing in the first place, and to the main quantum algorithms and other advances that everything builds on today — and not only to large organizations that have gotten good at capturing federal funds by repeating the requisite buzzwords.”

By Scott

Authors: Ming Yang

Classical simulations of quantum correlations can fail because no low-communication local hidden-variable model exists, or because no single noncontextual hidden state can explain all compatible measurement contexts. This manuscript studies a third regime: genuine global Kochen-Specker contextuality, where local subsystems are noncontextual and the tested multipartite blocks are generalized-Bell-local, but the whole empirical model admits no global noncontextual hidden-variable explanation. We propose a coordination-cost framework in which communication, memory, and local computation are treated as different ways for a classical simulator to maintain a global classical explanation from locally available information. We introduce coordination bits, global contextual covering numbers, scaling laws for task families, and an abstract lifting theorem showing how classical simulation lower bounds for KS-contextual seed families can be transferred to genuinely global-KS models. As worked examples, we analyze a polarization-path Hardy obstruction and postselected KCBS-type tasks.

Authors: Eduardo Yuji Sakabe, Felipe S. Abrahão, Santiago Hernández-Orozco, Ricardo Gudwin, Hector Zenil

The Block Decomposition Method (BDM) was introduced as an alternative to popular lossless compression methods such as LZW for estimating algorithmic complexity from the principles of algorithmic probability and classical information theory. It extends the Coding Theorem Method (CTM) from small objects to larger ones by combining local estimates of algorithmic complexity with a global account of repetition based on Shannon entropy. Here, we introduce a version of BDM in which dependencies between blocks are utilized to reduce the length of the description based on reusable program code in the decomposition of an object, and on conditional descriptions capable of accounting for shared structure between observations. We formalize this allocation of descriptive resources as algorithmic attention. Repeated or related components need not be described independently, and the resulting reduction in description length is governed by the amount of shared algorithmic information. We formulate this extension as a reuse optimization problem, show that exact optimization is NP-hard, derive conditions under which it improves upon independent descriptions, relate the achievable gains to algorithmic mutual information, prove the relationship with the previous BDM version, and provide a roadmap for its implementation using CTM-derived complexity and conditional complexity estimates.

Authors: Avishay Tal, Weiqiang Yuan

We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant $k$-junta testing with high precision can be solved using $\mathrm{poly}(k)$ quantum queries, whereas any classical algorithm requires at least $k^{Ω(\log k)}$ queries. The problem of tolerant $k$-junta testing is as follows: given parameters $(k, ε_1, ε_2)$, with $0\le ε_1<ε_2 \le 1/2$, and black-box access to a Boolean function $f$ (defined on $n$ variables), distinguish whether $f$ is $ε_1$-close to some $k$-junta or $ε_2$-far from every $k$-junta. We show the quantum advantage for a range of parameters close to $1/2$, for example, $ε_1 = 1/2-1/k$ and $ε_2 = 1/2-1/(2k^2)$. The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most $ε_1$ to $k$-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick $k$ out of $n$ coordinates, and for each fixing of the $k$ coordinates, the $2^{n-k}$ values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to $k$-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making $k^{o(\log k)}$ queries.

Authors: Chenyuan Jia, Qingqing Peng, Ke Liu, Guanghui Wang, Guiying Yan

The minimum distance problem (MDP) for low-density parity-check (LDPC) codes is a central problem in coding theory and is closely related to the analysis of low-weight codewords and error-floor behavior. Although the unrestricted MDP is computationally intractable, its complexity under degree constraints that commonly occur in LDPC code design has remained less clear. In this paper, we study the MDP for left regular and biregular Tanner graphs. We prove that the problem is $\mathrm{NP}$-complete and $\mathrm{W}[1]$-complete for $J$-left regular Tanner graphs for every fixed $J\geq 3$, and also for $(3,3)$-regular bipartite graphs. We further establish $\mathrm{W}[1]$-completeness for $(J,K)$-regular instances for every fixed $J,K\geq 3$. The reductions are based on a degree-preserving transformation framework consisting of hyperedge decomposition, check node splitting, and controlled variable replication. These transformations transfer hardness between different degree distributions while preserving explicit bijections among nonzero codewords, even covers, and nonempty $(a,0)$-trapping sets. The results delineate the computational limits of exact LDPC code analysis under natural regularity constraints.

Authors: Tianhang Lu, Runtian Ren, Shengcai Liu

This paper studies learning-augmented online weighted vertex cover with advice and a parameter $λ\in (0,1)$. We consider two graph cases: bipartite graphs and general graphs. In both settings, the online algorithm must maintain a feasible vertex cover under irrevocable decisions. We show that these problems admit the same robustness--consistency tradeoffs as learning-augmented ski rental. For the bipartite graph model, we give a randomized algorithm that is $\frac{1}{1-e^{-λ}}$-robust and $\fracλ{1-e^{-λ}}$-consistent. For the general graph model, we give a deterministic algorithm that is $(1+\frac{1}λ)$-robust and $(1+λ)$-consistent. We prove that the tradeoffs above are optimal in both settings. We also validate the proposed algorithms through experiments on synthetic and real-world datasets.

Authors: Liyan Chen, Matthew M. Hong, Yael Tauman Kalai, Zoe Xi

We show that every language in PSPACE decidable by a Turing machine in time $T(n)=n^{O(\log n)}$ admits a doubly efficient interactive proof system: the prover runs in time polynomial in T(n), and the verifier runs in time polynomial in n. This extends the best previously known regime for such proof systems from $T(n)=n^{O(\sqrt{\log n / \log\log n})}$, established by Berger, Goyal, Hong, and Kalai (FOCS 2025), to $T(n)=n^{O(\log n)}$. Beyond improving the range of T, our protocol is substantially simpler than previous doubly efficient proofs for time-bounded PSPACE. Earlier constructions proceed indirectly: they first build batch interactive proofs and then invoke them as a black box to obtain doubly efficient protocols. In contrast, we give a direct construction. This not only simplifies the proof but also points to a more promising route for future improvements.

Authors: Mithil Ramteke

We study exact nonnegative matrix factorization (NMF) of small exact-rank-r matrices via a cone-ray pipeline combining the truncated SVD, the polyhedral cone of nonnegative preimages, the Double Description Method (DDM, via Fukuda's cddlib), and an alternating linear program (alt-LP) for slack minimisation. Under a uniform-support restriction the factorisation constraint Q P^T = I_r reduces to entrywise nonnegativity of an r x r witness matrix M_T = R_T^{-1} (R_K^T)^{-1} for an r-subset pair (T, K) of cone rays; this closed-form witness recovers an exact NMF in microseconds when feasible. We characterise feasibility by ranking r-subsets via geometric near-orthogonality ("obtuseness") and walking the top of each list. A 100-trial Monte Carlo at m=n=10 exposes a clean saturation curve: success 44/32/8, 79/85/58, and 79/87/59 of 100 at top-5/200/400 for r=4,5,6 -- beyond top-200 the failures are structural, not budget-limited. Enlarging m,n at fixed r hurts: at m=n=15 success collapses to 37/7/0/0/0 for r=4..8. On Olivetti faces (400x4096) the DDM step itself times out. Our main contribution is a hybrid that breaks this ceiling: at each pair we first try the closed-form M_T, and when it is infeasible we augment both supports by k=2 maximally angularly-separated rays and solve for mu,nu>=0 by a short slack-LP alternation. On the same m=n=10 Monte Carlo this lifts success from 79/85/58 to 99/95/75 at r=4,5,6, with cone reconstruction error at or near machine precision. We close with the four scaling walls the pipeline faces and concrete next steps.

Authors: Annesha Sen, Shivam Singh, S. P. Tiwari

Mapper is a well-known tool in topological data analysis, which visualizes and summarizes high-dimensional data. However, its output is sensitive to choices of lens functions, cover parameters, and clustering strategies, making evaluation challenging. Most works that have attempted to evaluate the Mapper algorithm have done so visually. In this paper, we review a roadmap for assessing Mapper algorithms along three complementary axes: stability, cluster quality, and topological shape preservation. We analyze Mapper and its variants on synthetic datasets and the UCI Digits dataset. These modes include topological explosion at high resolutions. Our findings indicate that these axes of evaluation are often in tension and that no single Mapper variant performs optimally across all three. This review provides practical guidelines for choosing Mapper variants and identifies open challenges toward a principled Mapper analysis.

Authors: Annesha Sen, Shivam Singh, S. P. Tiwari

Topological Data Analysis uses tools from algebraic topology to study the shape and structure of data. The Mapper algorithm provides a graph-based summary of high-dimensional datasets by combining a filter function, a cover of the filter range, and clustering on the corresponding pullback sets. Several variants of Mapper have been proposed, including Conventional Mapper, F-Mapper, and Shape Fuzzy C-Means Mapper. In this article, we introduce Gustafson-Kessel Fuzzy Mapper Graphs, a geometry-adaptive extension of Shape Fuzzy C-Means Mapper. The proposed method replaces spherical fuzzy covers with ellipsoidal covers induced by the Gustafson-Kessel fuzzy clustering framework, making it more suitable for high-dimensional datasets with anisotropic and non-spherical geometry. We develop a stability framework for the graphs produced by Gustafson-Kessel Mapper and Shape Fuzzy C-Means Mapper. We prove that the membership functions depend smoothly on the fuzzifier, establish a precise condition for the existence of edges, and show that the graph is locally stable under small perturbations of the fuzzifier. We further describe the critical-event structure of graph changes in terms of threshold crossings of the membership functions and show that the graph is constant between consecutive critical events. When the threshold-crossing set is finite, this yields an eventual freezing threshold. Finally, we empirically show that Gustafson-Kessel Mapper can produce more stable graphs than Shape Fuzzy C-Means Mapper on high-dimensional and geometrically complex datasets.

Authors: Michael T. M. Emmerich

We study fixed-cardinality subset selection for the exact integral bi-objective $R_2$ indicator with a uniform continuum of weighted Tchebycheff scalarizing functions. The indicator measures the area under the lower envelope of scalarizing losses over weight space, rather than a finite sample average over weight vectors. For a sorted bi-objective Pareto-front approximation, represented by points ordered by increasing first objective and decreasing second objective, we derive an exact adjacent-neighbor decomposition of this integral objective into boundary terms, unary diagonal corrections, and selected-neighbor transition terms. This yields an exact Bellman dynamic program with $O(kn^2)$ running time for selecting $k$ of $n$ candidate points. We then prove that the transition matrix is Monge. This gives a divide-and-conquer implementation with $O(kn\log n)$ running time and, more strongly, a staircase matrix-search implementation with $O(kn)$ running time under constant-time arithmetic comparisons. The matrix-search proof is presented through a lower-envelope sweep over single-crossing transition functions and includes the triangular feasibility condition $i

Authors: Prashant Gokhale, Mikhail Khodak, Sandeep Silwal

We consider the problem of sequentially approximating functions of each element in a slowly-varying sequence, i.e. one where the magnitude $α_i$ of the difference between the elements at positions $i$ and $i-1$ is small. Recent work on implicit trace estimation shows that when $α_t$ is small, reusing queries to past sequence elements can reduce the overall cost [Dharangutte \& Musco, NeurIPS~2021; Woodruff et al., NeurIPS~2022]. We introduce a framework generalizing this to a variety of linear and nonlinear functions on diverse vector spaces, obtaining novel sequential estimation results for matrix powers, spectral densities, Monte Carlo integration, and a boundary value problem from partial differential equations~(PDEs). Furthermore, we develop a novel algorithm for use with this framework that locally scales the estimation budget with $α_t$, obtaining sharper path-length-style variation bounds of form $\mathcal O(\sum_{i=1}^mα_i)$ on the cost of estimating a sequence of length $m$. This improves upon the previous implicit trace estimation bound of $\mathcal O(m\cdot\max_iα_i)$ [Dharangutte \& Musco, NeurIPS~2021], which is achieved by fixing the query budget using the worst-case $α_i$ and is thus inefficient for stable sequences with rare bursts. Lastly, while all past work assumes a known bound on $α_i$, we show in certain cases how the changes can be estimated on-the-fly with (nearly) no added cost. In summary, our framework makes the sequential approximation toolkit general-purpose and adaptive while improving upon state-of-the-art-guarantees for dynamic trace estimation.

Authors: Arthur Braida, Elie Bermot, Simon Apers

Quantum tunneling is expected to provide a computational speedup in quantum computing, a phenomenon that Adiabatic Quantum Optimization (AQO) aims to leverage. While some academic proofs of concept have been studied, such as the "Hamming weight with a spike" (HWS) problem, the algorithmic gains of this effect remain underexplored. In this work we extend the analysis underlying HWS to more general potentials. In the first half of the work, we establish (discrete) log-concavity of the ground state as a key structural property in this context. We devise a framework for establishing log-concavity of the ground state for a large family of discrete, 1-dimensional Schrödinger operators. The family includes convex potentials, but also certain potentials with local minima. In the convex case, this provides a discrete version of a continuous result by Brascamp and Lieb ('76). We demonstrate the utility of our result by establishing new spectral gap bounds, going beyond related results by Jarret and Jordan ('14) for convex potentials. In the second half of the work, we use our results on log-concavity to extend the perturbative analysis of HWS by Reichardt ('04) to the larger family of potentials with log-concave ground state. As a concrete instantiation, we use our result to extend the HWS analysis from a linear potential (which is exactly solvable) to a quadratic potential (which is no longer solvable). Our result strongly suggests the broader applicability of tunneling to convex potentials with spikes

Authors: Alexander Barvinok

We consider expectations of the type $E\ \exp \left\{\sum_{i=1}^m φ_i \right\}$, where $φ_i: {\Bbb R}^n \longrightarrow {\Bbb C}$ are functions, each depending on a few coordinates of a point in ${\Bbb R}^n$, and the expectation is taken with respect to the standard Gaussian or symmetric exponential probability measures. We prove sufficient conditions, in terms of the Lipschitz constants of $φ_i$ and the combinatorics of their dependencies, for the integral to be separated from 0, and, consequently, to be amenable to a computationally efficient approximation. We discuss applications to computing volumes of bodies and statistics on integer points in polyhedra in ${\Bbb R}^n$.

Authors: Rajesh Jayaram

Multi-vector (MV) embeddings have become a powerful paradigm in neural information retrieval (IR), achieving high retrieval accuracy by representing data with multiple vectors and scoring them via the non-linear Chamfer similarity. Despite their widely perceived superiority over single-vector (SV) embeddings which use inner product similarity, to date there is no formal proof that SV similarities cannot approximate MV similarities with the same representation size. Specifically, we ask the following: for any bounded dataset size $n \leq 2^{poly(m)}$, what is the smallest dimension $D$ so that given any collection of MV embeddings $Q_1,\dots,Q_n,X_1,\dots,X_n \subset \mathbb{R}^d$ containing at most $m$ vectors each, there always exist $q_1,\dots,q_n$, $d_1,\dots,d_n \in \mathbb{R}^{D}$ satisfying $|\langle q_i, d_j \rangle - \texttt{Chamfer}(Q_i,X_j)| \leq ε$ for all $i,j$? Recently, the MUVERA algorithm demonstrated that $D = m^{O(1/ε^2)}$ is possible. If improved to $D = md$, this would imply that MV embeddings are no more expressive than SV embeddings. In this paper, we rule out this scenario. Specifically, we prove the existence of a collection of MV embeddings in $\mathbb{R}^d$, each containing at most $m$ vectors, which require single-vector dimension of $D =(ε^2 m)^{Ω(1/ε)}$ to approximate, establishing a strong separation in representation size between MV and SV embeddings. Our proof leverages the Pattern Matrix Method by constructing a hard instance whose Chamfer similarity matrix encodes the $NAND_k$ boolean function. Our results confirm a long-held belief in the IR community: at a fixed representation size, multi-vector embeddings can express similarities which cannot even be approximately represented by single vector embeddings.

Authors: Nader H. Bshouty

In this paper, we study the problems of abelian group property testing in two models. In the partially specified model (PS-model), the algorithm does not know the group size but can access randomly chosen elements of the group, along with the Cayley table of these elements, which provides the result of the binary operation for every pair of selected elements. In the stronger fully specified model (FS-model), the algorithm knows the size of the group and has access to all its elements and the Cayley table. In property testing of abelian group property, given a finite set $G$ and oracle access to a binary operation $*:G^2\to G$, we aim to distinguish whether $(G,*)$ is an abelian group or is $ε$-far from any abelian group over $G$. Using a novel approach, we present a tester in the PS-model (and consequently in the FS-model) that runs in time $\tilde O(\sqrt{|G|}+1/ε)$, improving upon the Goldreich-Tauber tester, which runs in time $O(|G|/ε)$. Additionally, our tester improves another tester by Goldreich and Tauber that runs in time $O(|G|^2)$ and makes $\tilde O(|G|+1/ε)$ queries. We further extend our result to testing subclasses of abelian groups ${\cal G}$ that are closed under isomorphism. Specifically, if one can decide in time $T$ whether an abelian group of the form $Z_{m_1}\times \cdots\times Z_{m_r}$ belongs to ${\cal G}$, then there exists a tester for ${\cal G}$ that runs in time $T+\tilde O(\sqrt{|G|}+1/ε)$ and makes $O(\sqrt{|G|}+1/ε)$ queries. This result gives testers that run in time $O(\sqrt{|G|}+1/ε)$ for subclasses such as abelian groups of rank at most $k$, abelian $p$-groups, and vector spaces over~$Z_p$.