Theory of Computing Report

We derive the four principal asymptotic rate-distance tradeoffs for binary codes---Plotkin, Elias--Bassalygo, and the two McEliece--Rodemich--Rumsey--Welch (MRRW) bounds---from one theorem, the ``pretty good criterion.'' If the bit error rate under the pretty good measurement (PGM)---the quantum analog of posterior sampling---of a binary-input output-symmetric classical--quantum (cq) channel lies below $\delta$, then every length-$n$ binary code, linear or nonlinear, of relative distance $\delta$ has rate at most the channel's capacity, up to an $O(n^{-1/2})$ correction. Rate--distance bounds thereby reduce to a channel design problem, wherein the task is to minimize channel capacity subject to the posterior bit error rate constraint. Via the pretty good criterion, the binary erasure channel (BEC) yields Plotkin, the binary symmetric channel (BSC) yields Elias--Bassalygo, the pure-state channel (PSC) yields the first MRRW bound, and a masked PSC yields the second MRRW bound exactly. This framework is then instantiated with new channels to improve upon the MRRW bounds. Specifically, the mixed-qubit channel (MQC), a mixed-state version of PSC, strictly improves the first MRRW bound at every $0 < \delta < \frac{1}{2}$, while the masked mixed-qubit channel (2MQC) strictly improves the second MRRW bound throughout the same interval.

Authors: Nikolai Chukhin, Alexander S. Kulikov, Maksim Levitskii, Ivan Mihajlin

The Subset Sum problem asks whether, given $n$ integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is $O^*(2^{n/2})$ (Horowitz and Sahni, 1974), whereas the best quantum upper bound is $O^*(2^{n/3})$ (Bernstein, Jeffery, Lange, and Meurer, 2013). The $k$-SUM problem is a parameterized version of Subset Sum asking whether there are $k$ integers that sum to the target. The best classical upper bound for it is $\widetilde O(n^{\lceil k/2\rceil})$, whereas the best quantum running time is $\widetilde O(n^{k/3})$ (Tani, 2009). For random instances, a quantum algorithm with running time $\widetilde O(n^{Φ_k})$ is known, where $$ Φ_k=\frac{2k-\lfloor k/7\rfloor-\lfloor (k+3)/7\rfloor}{6} $$ (Schrottenloher, 2021). We present a new quantum algorithm solving worst-case $k$-SUM in time $\widetilde O(n^{Ψ_k})$, where $$ Ψ_k=Φ_k-\frac{[k\equiv 3\bmod 7]}{9}-\frac{[k\equiv 6\bmod 7]}{18}. $$ The algorithm is not only faster for all $k$ congruent to $3$ or $6$ modulo $7$, but also gives a worst-case guarantee rather than a guarantee restricted to single-solution random instances. Combining our algorithm for $7$-SUM with the standard block reduction technique yields an $O^*(2^{2n/7})$ quantum algorithm for Subset Sum, improving the previously known $O^*(2^{n/3})$ algorithm.

Authors: Lucas Gretta, Malvika Raj Joshi

Shor's algorithm is a canonical quantum supremacy target whose core operation relies on the Quantum Fourier Transform (QFT). We resolve an open question of Fang, Fenner, Green, Homer and Zhang from 2006 by showing that approximating QFT in constant depth, for any $n$-qubit modulus, necessarily requires the $n$-qubit Fanout operation. Formally, let $\mathsf{QFT}_q$ be the gate acting on $n = \lceil \log q \rceil$ qubits that computes the QFT under modulus $q$. It is known that any $n$-qubit $\mathsf{QFT}_q$ can be implemented in constant depth using $\mathsf{FANOUT}_n$, i.e. $\mathsf{QFT}_q \in \mathsf{QAC}^0_f$. We prove the converse by using a $\mathsf{QFT}_q$ gate to construct a state of ``non-negligible felinity". Consequently, $\mathsf{QFT}_q \in \mathsf{QAC}^0 \iff \mathsf{FANOUT}_n \in \mathsf{QAC^0}$. In the case of $q = 2^n$, such as in Shor's, we approximate $\mathsf{FANOUT}_n$ using a single $\mathsf{QFT}_{2^n}$ gate and $O(1)$ two-qubit local gates, thus tying the feasibility of realizing Shor's algorithm with NISQ circuits to that of Fanout.

Authors: Josh Alman

For sufficiently large $N$ which is a power of 2, we prove that changing at most one percent of the entries of the $N\times N$ Walsh-Hadamard Transform cannot reduce its rank over $\mathbb{F}_3$ to $\lfloor \log^2 N/80\rfloor$ or below. To the best of our knowledge, this is the first constant-fraction rigidity lower bound for an explicit matrix family at a superlogarithmic target rank over any choice of field, inching toward the parameters in Razborov's program for communication complexity lower bounds.

Authors: Petar Hristov, Ingrid Hotz, Talha Bin Masood

Trait-induced merge trees (TIMTs) provide a robust topology-based method for selecting and browsing feature level sets in multivariate data by analyzing the distance field induced by a user-specified trait in attribute space. Existing TIMT computations typically sample this distance field at mesh vertices and assume piecewise-linear interpolation, although the Euclidean distance-to-trait function is generally not piecewise linear on the original mesh. As a result, the resulting merge tree may miss zero-valued features and may perturb the locations and values of minima and merge events. We study the exact computation of TIMTs for piecewise-linear bivariate fields, focusing first on point traits. We show that the restricted sublevel sets inside each tetrahedron are convex and therefore have trivial local merge-tree structure, implying that global topological changes arise only through gluing across simplex boundaries. Based on this observation, we construct a weighted graph whose merge tree is isomorphic to the exact merge tree of the induced distance field. We further relate TIMTs to Jacobi sets, showing how nonzero edge events of the TIMT are localized by the singular structure of the underlying bivariate map. We establish a theoretical upper bound on the error of the vertex-sampled linear interpolation, expressed in terms of the maximum length of projected mesh edges in the range. We discuss extensions to line, line-segment, and finite point-set traits, and implement the method robustly using CGAL and VTK, demonstrating results on both synthetic and real-world datasets.

Authors: Tamal K. Dey, Andrew Haas, Michał Lipiński

Recent advances in combinatorial dynamical systems that generalize the classic discrete Morse theory have prompted algorithmic studies of combinatorial vector fields. In this regard, authors in [7] recently proposed the concept of Conley-Morse persistence barcode that summarizes the continuation of invariant sets in an evolving vector field through homological persistence. They proposed an algorithm to compute this barcode using a filtration of the so called \emph{index pairs} on a poset called \emph{transition diagram}. The algorithm becomes costly due to multiple runs of zigzag persistence it executes on filtrations of `unwieldy' structures of index pairs. We overcome this difficulty by replacing the index pairs with \emph{blocks}, which are structurally much simpler. These replacements need reversal of certain relations in the transition diagram resulting in a much simpler algorithm. The algorithm works by updating matrix decompositions akin to computing `vineyard' in standard persistence.

Authors: Prafullkumar Tale

Let \(G\) be a connected simple undirected graph. A vertex \(w\) is said to \emph{strongly resolve} a pair of distinct vertices \(u, v \in V(G)\) if either there exists an isometric path (i.e.~a shortest path) from \(w\) to \(u\) that contains \(v\), or there exists an isometric path from \(w\) to \(v\) that contains \(u\). A subset \(S \subseteq V(G)\) is said to \emph{strongly resolve} \(G\) if every pair of distinct vertices of \(G\) is strongly resolved by at least one vertex in \(S\). In the \textsc{Strong Metric Dimension} problem, the input consists of a graph \(G\) and a positive integer \(k\), and the objective is to determine whether there exists a subset \(S \subseteq V(G)\) of size at most \(k\) that strongly resolves \(G\). In this article, we show that \textsc{Strong Metric Dimension} is \NP-complete even on \((i)\) graphs of diameter two, and \((ii)\) graphs of constant pathwidth and constant feedback vertex set number.

Authors: Sami Davies, Benjamin Moseley, Heather Newman

The standard online version of correlation clustering is prohibitively hard, as even randomized algorithms cannot achieve competitive ratio better than $Ω(n)$. Prior works bypass this lower bound by relaxing the online model through recourse, random arrival order, or seeding the algorithm with an offline sample of the underlying input. We instead ask whether additional structure in the input itself can overcome this lower bound. We study weighted correlation clustering under probability constraints, where $w^+_{uv}+w^-_{uv}=1$ for every $uv$ edge, and triangle inequality constraints, where the negative weights $w^-$ satisfy triangle inequality. While this version of correlation clustering is well-studied in the offline setting, we initiate its online study and give a deterministic online algorithm that maintains a clustering whose total weighted disagreement cost is within an $O(1)$ factor of the offline optimum, against adversarial arrival order. This is the first constant-competitive online algorithm for a natural minimization variant of correlation clustering in the fully online model, and shows that metric consistency on the edge weights separates tractable from intractable online instances.

Authors: Édouard Bonnet

For every $\varepsilon > 0$, it is NP-hard to $n^{1-\varepsilon}$-approximate Max Independent Set in $n$-vertex graphs [Hastad '96, Zuckerman '07]. In triangle-free graphs, a simple argument gives a polynomial-time $n^{1/2}$-approximation algorithm, whereas, for every $\varepsilon > 0$, an $n^{1/4-\varepsilon}$-approximation algorithm would imply that NP $\subseteq$ BPP [Bonnet, Thomassé, Tran, Watrigant; ESA '20]. In this note, we close this gap by proving the corresponding hardness against $n^{1/2-\varepsilon}$-approximation algorithms. The reduction is very simple and uses the Moser-Tardos resampling algorithm to make the constructed graphs triangle-free. The soundness uses a result of Haeupler, Saha, and Srinivasan building on the proof of Moser and Tardos, to upper-bound the probability that a fixed relatively large subset is an independent set after the Moser-Tardos algorithm terminates. We generalize this scheme and show that, for any nonempty finite family $\mathcal F$ of graphs, each containing at least one cycle, for any $\varepsilon > 0$, an $n^{μ(\mathcal F)-\varepsilon}$-approximation algorithm for Max Independent Set in graphs excluding every member of $\mathcal F$ as a subgraph implies that NP $\subseteq$ BPP, where $μ(\mathcal F) := 1 - \max\limits_{H \in \mathcal F}~\min\limits_{U \subseteq V(H), H[U] \text{contains a cycle}} (|U|-2)/(|E(H[U])|-1)$.

Authors: Hadley Black, Geelon So

We study the problem of learning nearest-neighbor maps from adaptive queries, which is equivalent to the following problem of reconstructing a hidden set $H$ via a nearest-neighbor query oracle. Let $K \subset \mathbb{R}^d$ be a compact domain in a normed space $(\mathbb{R}^d,\| \cdot\|)$ and let $H \subset K$ be a hidden set of $n$ points. Upon querying $q \in K$, the oracle returns some $h \in H$ with minimum distance from $q$. How many queries are required to exactly recover $H$? Previous work has studied this question in specific domains, namely the Boolean hypercube and the $\ell_2$-unit sphere. We generalize previous work and prove the tight worst-case query complexity bound of $Θ(nκ)$, where $κ$ is the kissing number of the underlying norm. In the Euclidean norm, obtaining tight asymptotic bounds on $κ$ is a significant open question, although it is known that $κ= \exp(Θ(d))$. Our second set of results shows that an exponential dependence on $d$ is required even in natural Euclidean domains: $\exp(Ω(d))$ queries are needed in the ball, even when $n=2$, and $n\exp(Ω(d))$ queries are needed in the cone. Lastly, we prove a sharper upper bound in the Euclidean sphere. Here, $d$ can be replaced by $\min(n,d)$ via a dimension reduction preprocessing step. This is a randomized version of a procedure due to Prabhu-Woodruff (ICML 2024) where we improve the query complexity from $O(nd)$ to $O(\min(n,d))$. This reveals a striking contrast between the sphere and the ball: when $n = O(1)$, the sphere admits an $O(1)$ query algorithm, whereas the ball requires $\exp(Ω(d))$.

Authors: Yossi Azar, Debmalya Panigrahi, Or Vardi

We study an online variant of the Traveling Salesperson Problem (TSP) in which $n$ points arrive sequentially and must be inserted into an evolving tour. In the classical setting where arbitrary insertions are allowed, an $O(\log n)$-competitive algorithm has been known since the 1970s (Rosenkrantz, Stearns and Lewis 1977, Imase and Waxman 1991). Recently, Abrahamsen, Bercea, Beretta, Klausen, and Kozma [ESA 2024] introduced online metric TSP, a stricter model in which each arriving point must be assigned to a distinct cell of an array of size $m \ge n$, with the final tour order induced by the non-empty cells; the parameter $m$ captures the space usage of the algorithm. When $m = 2^{n}$, this model recovers arbitrary insertions and therefore admits an $O(\log n)$-competitive algorithm. In contrast, when $m = n$, i.e., when each point's position is fixed on arrival, Bertram [ESA 2025] recently showed that the competitive ratio is $Θ(\sqrt{n})$. We investigate the tradeoff between space usage and competitiveness between these extremes. We note that this tradeoff was previously explored by the authors [SODA 2026] for the online sorting problem, which is the special case of online metric TSP on a line metric. Our main result is a deterministic online metric TSP algorithm using $m = (1+ε) n$ space that achieves a competitive ratio of $O(\log^{3} n / ε)$, for any $ε\le 1$. In particular, increasing the space from $n$ to $2n$ improves the competitive ratio from $Θ(\sqrt{n})$ to $O(\log^{3} n)$. We complement this with a lower bound showing that for $m = n^{1+ε}$, any deterministic algorithm has a competitive ratio $Ω(1/ε)$, for all $ε\ge Ω(\log \log n / \log n)$. Consequently, even with $m = O(n \cdot \mathrm{polylog}(n))$, deterministic algorithms cannot achieve a constant competitive ratio.

Authors: Youlong Ding

We consider the following problems: Given two $n \times n$ tables defining binary operations $+$ and $\cdot$ on a set $S$ of $n$ elements, decide whether $(S,+,\cdot)$ forms a ring or, respectively, a field. Recently, Dudek, Fischer, Gokaj, Jin, Künnemann, Mao, and Redzic (STOC 2026) obtained the following two (near-)optimal results: (1) A randomized $O(n^2\log(1/δ))$-time algorithm for verifying rings. (2) A deterministic $O(n^2)$-time algorithm for verifying fields. Their algorithms build on machinery of Evra, Gadot, Klein, and Komargodski (FOCS 2024), which relies on Classification of Finite Simple Groups (CFSG). In this work, we give a deterministic $O(n^2)$-time algorithm for ring verification, resolving the deterministic complexity of this problem. As a corollary, we also obtain a deterministic $O(n^2)$-time algorithm for field verification. Our algorithms are elementary and avoid CFSG machinery entirely.

Authors: Viktor Fredslund-Hansen, Shay Mozes, Oren Weimann

Let $G$ be an undirected unweighted planar graph and let $S=(s_0,\dots,s_{k-1})$ be the vertices of a designated face, listed in cyclic order. Consider a vector that stores the distances from an arbitrary vertex $v$ to all vertices of $S$. The pattern of $v$ is obtained by taking the difference between every pair of consecutive values in this vector. Li and Parter [STOC'19] proved an upper bound of $O(k^3)$ on the number of unique patterns over all vertices of $G$. We improve this to $O(k^2)$, matching a known lower bound and settling a conjecture in [ISAAC'22]. The simple proof was found by OpenAI's GPT 5.6-Sol model. Plugging this new bound into known results has the following three immediate implications for undirected unweighted planar graphs: (1) it gives an improved compression of the Okamura-Seymour metric (2) it improves the space required by constant-time exact distance oracles, and (3) it improves the fastest distributed algorithm for computing the diameter. We further present a previously unknown and nontrivial implication: a (centralized) $\tilde{O}(n^{8/5})$-time algorithm for computing the diameter, improving over the $\tilde{O}(n^{5/3})$ algorithm of [SODA'18] which works for weighted directed planar graphs. Thus, there is currently a gap between the time for computing the diameter between weighted and unweighted planar graphs.

Authors: Benjamin Aram Berendsohn, Egor Gorbachev, László Kozma

Heaps (priority queues) are among the best-studied data structures in computer science. In this paper, we critically revisit the textbook assumption that in the comparison model at least one of the two standard heap operations of inserting an element and deleting the minimum must take logarithmic time. By decoupling the deletion itself from the act of revealing the identity of the deleted element to the user, we avoid the sorting barrier and obtain a novel trade-off between the complexities of heap operations. This shows that the logarithmic barrier is not inherently the cost of deleting the minimum but rather the information cost of immediately learning which element was deleted. In the special case when the user inspects the heap state only constantly many times, we show that both insertions and deletions can be supported in constant amortized time. As an application, this yields a runtime improvement from $\mathcal{O}(n \log n)$ to the optimal $\mathcal{O}(n)$ for a textbook unit-time scheduling problem. We obtain our results by designing a new data structure, the sync heap, which gains speed by rearranging and compacting its operations until queries force it to synchronize and reveal its state. As a key component, we use the soft heap introduced by Chazelle as part of his minimum spanning tree algorithm. Our data structure is simple, comparison-based, and deterministic, and our results are asymptotically optimal.

Authors: Davide Bilò, Keerti Choudhary, Sarel Cohen, Martin Schirneck

Let $L$ and $f$ be positive integers. An $(L,f)$-replacement path covering (RPC) for a graph $G$ is a family $\mathcal{G}$ of subgraphs such that, for every set $F$ of at most $f$ edges, there is a subfamily $\mathcal{G}_F \subseteq \mathcal{G}$ with the following properties. (1) No subgraph in $\mathcal{G}_F$ contains an edge of $F$. (2) For each pair of vertices $s,t$ that have a shortest path in $G{-}F$ with at most $L$ edges, one such path also exists in some subgraph in $\mathcal{G}_F$. The total number $|\mathcal{G}|$ of subgraphs is called the covering value. RPCs are an important tools in the design of fault-tolerant data structures. Weimann and Yuster [TALG 2013] presented an RPC with covering value $\widetilde{O}(f L^f)$. Karthik and Parter [TALG 2024] showed that $Ω( (L/f)^f )$ subgraphs are necessary. Recently, Bilò, Chechik, Choudhary, Cohen, and Schirneck [ICALP 2026] devised a new approach for very small sensitivities $f = o(\log L)$ with covering value $\widetilde{O}(f e^f (L/f)^{f+o(1)})$. They also showed that any RPC in the complementary range $f = Ω(\log L)$ must contain $Ω( (\sqrt{f e^f}/L) \cdot (L/f)^f)$ subgraphs. This left open the question of what is the true covering value. We give two surprisingly simple constructions that improve both the upper and lower bound. This results in a near-tight covering value of $\widetildeΘ(\frac{(L+f)^{L+f}}{L^L f^f}) \cdot \mathsf{poly}(f)$ for the much wider range of $f = O(L)$.

Authors: Amir Azarmehr, Soheil Behnezhad, Lily Chung, Alma Ghafari, Jane Lange, Ronitt Rubinfeld

Consider a poset - or equivalently an $n$-vertex DAG $G=(V, E)$ - and a boolean function $f: V \rightarrow \{0, 1\}$ on its vertex set. We say $f$ is monotone if $f(u) \leq f(v)$ for all $(u, v) \in E$. While there is extensive literature on the query complexity of testing monotonicity, we focus instead on the space complexity and initiate the study of this problem in the streaming setting. Namely, the edges of $G$ arrive in an arbitrary order, and the goal is to estimate distance to monotonicity of a given function $f$ using $\widetilde{O}(n)$ space. Note that while this space allows receiving and storing $f$, it is much smaller than the input graph $G$ which could have up to $Ω(n^2)$ edges. Our main result is an algorithm that $(2+ε)$-approximates distance to monotonicity in $\sqrt{n}^{1+o(1)}$ passes. We also prove that this is the best pass-complexity one can hope for, for any $O(1)$-approximation, short of improving the state-of-the-art streaming algorithm for $st$-reachability, which is a very well-studied problem. On the technical side, our algorithm approximates the size of maximum matching in (a subgraph of) the transitive closure of $G$. While the maximum matching problem has received significant attention in the streaming setting, the fact that we are computing it in the transitive closure requires very different ideas. In fact, a main contribution of our work is to connect sublinear time algorithms for estimating the maximum matching size to the streaming setting for the first time. While existing off-the-shelf sublinear time algorithms only result in an $n\sqrt{n}^{1+o(1)}$ pass algorithm in our setting, we show how to significantly improve upon them by allowing stronger queries (such as vertex and subset queries) that can be implemented just as efficiently as more standard adjacency matrix and list queries for our problem.

Authors: Lu Chen, Chengfei Liu, Rui Zhou, Jiajie Xu, Jianxin Li

Given a heterogeneous information network (HIN) and a query meta-path P of length i, the densest P-partite subgraph problem finds the subgraph, spanning the i typed layers of P, that maximizes a parameter-free density: the number of meta-path instances over the geometric mean of the layer sizes. It has applications across bibliographic, e-commerce, and biomedical networks. The state-of-the-art approximation linearizes the geometric-mean objective by fixing per-layer weights, but solves one subproblem for every feasible weight set, of which there are $O((n/i)^i)$, and on each achieves only a $1/i$ approximation. We show that neither the exhaustive enumeration nor the loose guarantee is necessary. First, we replace enumeration by covering: polylogarithmically many representative weight sets, localized further by a data-dependent bound, cover all feasible ones while losing only a tunable factor $1+η$ in density. Second, we cast each fixed-weight subproblem as a weighted supermodular densest-subgraph instance and solve it near-optimally, lifting the overall guarantee to $(1-δ)/(1+η)$. To our knowledge, this is the first near-optimal density approximation beyond the bipartite ($i=2$) case, and it yields a PTAS for every fixed i. Algorithmically, our solver is an adaptive peeling scheme that never materializes the meta-path instances, whose number can exceed the graph size by orders of magnitude. An incumbent-driven reduction further discards representative weight sets before their subproblems are solved. Experiments on five real HINs show that our algorithms achieve substantial speedups over enumeration-based baselines and can further certify the near-optimality of the returned subgraph.

Authors: Jianshen Zhu

For a finite hypergraph H, the complements of the models of its associated definite Horn CNF are exactly the stopping sets of H; hence the complements of its coatoms are the inclusion-minimal nonempty stopping sets. We study their output-sensitive enumeration from the hypergraph incidence representation. Our main result is a representation of arbitrary Horn model posets whose incidence size is linear in the incidence length of the normalized Horn input. Given a Horn CNF $Γ$, we construct a hypergraph $C(Γ)$ of rank at most three whose proper-model poset is inclusion-order isomorphic to the model poset of $Γ$; equivalently, each source model has a unique extension to a proper target model. Thus maximal models of $Γ$ correspond bijectively to target coatoms. Combining this representation with the maximal-model construction of Kavvadias, Sideri, and Stavropoulos shows that coatom enumeration is not in OutputP unless P=NP, even when all hyperedges have size two or three. Incidence splitting reduces maximum element frequency to three while preserving the stopping-set poset, and a local replacement of two-element hyperedges yields the same lower bound for three-uniform hypergraphs of maximum element frequency at most three. These thresholds are conditionally sharp for arbitrary-order enumeration: rank at most two and maximum element frequency at most two both admit output-linear total-time generation; in the frequency-two case, a polynomial-delay, polynomial-space algorithm is also available. In contrast, coatom extension is NP-complete already for three-uniform hypergraphs of exact element frequency two.

Authors: Joseph Koutsoutis, Jesse Lerner, Roie Levin, Jiawei Yu

We give a new $O(\log n)$ approximation algorithm for Node Weighted Steiner Tree and Node Weighted Steiner Forest. Our algorithm matches the bounds of Klein & Ravi [J. Algorithms '95] which are best possible unless P = NP, but have the advantage that they work in the online setting when the terminal pairs are revealed in random order. To obtain our results, we combine the LearnOrCover framework due to Gupta, Kehne, Levin [FOCS '21] with the Augmented Greedy algorithm of Berman & Coulston [STOC '97] for online edge-weighted Steiner Forest. Neither algorithm suffices on its own, but the analyses dovetail to imply our guarantee. Run offline, the algorithm reduces to a very simple randomized rounding scheme that (in spirit) reduces Node Weighted Steiner Forest to Edge Weighted Steiner Forest, and we hope this idea finds further applications.

Authors: Tianhang Lu, Runtian Ren, Shengcai Liu

We study online multi-level aggregation on finite rooted trees with a per-batch maximum-delay objective. A service pays for a rooted subtree and for the maximum waiting time among the requests cleared by that service. We show that the offline optimum admits a consecutive-arrival-block normal form and can be computed by a polynomial-time dynamic program. The same dynamic program defines the deadlines of a family of online algorithms, which we call DP-Envelope. Its deterministic endpoint is $2$-competitive. Sampling one global parameter with density $e^θ/(e-1)$ leads to an $e/(e-1)$-competitive randomized algorithm against an oblivious adversary. The deterministic guarantee matches the known fixed-node lower bound, and we prove a matching randomized lower bound. Thus, both guarantees are optimal on every nondegenerate rooted tree. We first develop the line metric as a warm-up, where the algorithm and its nested block partitions have a direct geometric interpretation. Finally, we show that the upper bounds extend to every realizable static service system with a normalized, nondecreasing, submodular joint service cost.

Authors: Artem Kaznatcheev

Many local search methods for problems in artificial intelligence can be viewed as an uphill climb on a corresponding discrete fitness landscapes. Finding even local peaks in these fitness landscapes is computationally intractable in theory, but often works in practice. So what features of fitness landscapes allow for efficient local search? Since any fitness landscapes can be represented by a (hyper)graph of valued constraints, I re-frame this as a question of parameterized complexity: what structural parameter of a valued constraint graph guarantees that a strict local search will find a local peak in the corresponding fitness landscape efficiently? Given a valued constrain graph of vertex cover number k, I prove that greedy local search will find the a local fitness peak in at most $2^{2k}\cdot(n - k + 1)$ steps and random uphill local search will find a local fitness peak in an expected number of at most $2^k\cdot n(n - k)$ steps. I also show that these results are asymptotically good for strict local search because there are valued constraint graphs of vertex cover number $k$ where every ascent from some initial assignment has a length of $\frac{9}{128} \cdot 2^k \cdot (n - k)$ or greater. This suggests vertex cover number as a good structural parameter for the complexity of local search.

(Some of this came from a Reddit post  I read, and some of  the comments on it.) 

Here are theorems with names that I think are funny or unusual. The names are also pointers to the Wikipedia entry on them or some other source.

The Chicken McNugget Theorem

The Ham Sandwich Theorem

The Hairy Ball Theorem

Freshman Dream

The law of the unconscious statistician

The Homicidal Chauffeur Problem

The Pigeonhole Principle (We are so used to this we no longer find it funny, but it is.) 

Eventown and Oddtown 

I am sure there are more and I invite you to comment BUT there are some issues

1) What is funny?

2) I want math concepts that are known. As a counterexample, if Lance proved a theorem and called it the Funkytown Theorem just to get on this list then I'd be surprised. It also would not count. 

3) The name has to be some relevance to the concept. 

And I now list two titles of papers that I find funny. Note that what I write IS the title, even though the first one is an odd title and the second one really does not look like a title.

A minus sign that used to annoy me but now I know why it is there (two constructions of the Jones polynomial)

Some title containing the words "homotopy" and "symplectic", e.g., this one

By gasarch

Last month saw seven papers covering a reasonable range of topics in property testing. Our line up contains diversions in distribution testing, graph property testing and quantum. Let us start with a result from the quantum land on spectrum estimation. (And oh, let me add that all em-dashes in this post are human generated).

Spectrum Estimation is Almost as Hard as Tomography by Marco Fanizza, Ryan O’Donnell, Chirag Wadhwa (arXiv) A \(d\)-dimensional quantum state is modeled as a density matrix (i.e., a complex-valued PSD matrix with unit trace). Take a quantum state \(\boldsymbol{\rho} \in \mathbb{C}^{d \times d}\) and let \(spec(\boldsymbol{\rho})\) denote the collection of all eigenvalues of this state (also referred to as the spectrum of \(\boldsymbol{\rho}\)). The paper considers the computational challenge of estimating the spectrum of an unknown quantum state \(\boldsymbol{\rho}\). The algorithm is required to return a vector \(\widehat{\boldsymbol{\alpha}}\) which is within a small total variation distance \(\varepsilon\) of the spectrum of \(\boldsymbol{\rho}\). The main result establishes a lower bound: you cannot meet this challenge with fewer than \(\Omega(d^{2-\varepsilon})\) copies of \(\boldsymbol{\rho}\). This also shows that the recent work of Pelecanos-Spilecki-Tang-Wright achieves near-optimal dimension dependence for this task.

Testing Distributions Against Bounded Distinguishers by Mark Bun, Rathin Desai, Renato Ferreira Pinto Jr (arXiv) Alright, so let us go back to the recurring theme of testing properties of high-dimensional distributions. So, in your hand sits a distribution supported on \(\{0,1\}^n\). Classic tasks like identity testing with respect to a fixed reference distribution can now be seen to have very large sample complexity. To allay this, a lot of previous works take the BWCA approach and instead develop testers in situations where the reference distribution is structured. Other approaches proceed by assuming access to stronger sampling oracles. The featured paper considers a different twist. Let \(\boldsymbol{p}\) denote the input distribution and we want to test whether \(\boldsymbol{p} = \boldsymbol{p}_{REF}\). We are promised that either \(\boldsymbol{p} = \boldsymbol{p}_{REF}\), or it satisfies \(dist_{\mathcal{F}}(\boldsymbol{p}, \boldsymbol{p}_{REF}) \geq \varepsilon\) (where \(\mathcal{F}\) is a collection of boolean tests). Recall that the familiar notion of total variation distance \(dist_{TV}(\boldsymbol{p}, \boldsymbol{q})\) is obtained by letting \(\mathcal{F}\) range over the family of all boolean tests. In situations where \(\mathcal{F}\) is a special subclass of all boolean tests, we get an interesting notion of total variation distance according to the suite of tests in the class \(\mathcal{F}\). The paper goes on to derive a bunch of interesting results in this framework. For illustration, here is an example result from the paper: suppose you know the Rademacher complexity of the reference distribution with respect to the subclass \(\mathcal{F}\) is small. Theorem 1.3 in the paper proves that this means the sample complexity of identity testing (with respect to \(\boldsymbol{p}_{REF}\)) under the “\(\mathcal{F}\)”-distance is also small.

Testing the Independent Set Property in Hypergraphs by Elena Grigorescu, Shreya Nasa, Cameron Seth (arXiv) For this paper, I will let a paraphrasing of the abstract do the talking.

Alright, so here is another property testing problem, this time for hypergraphs. Consider a \(q\)-uniform hypergraph on \(n\) vertices, and suppose we want to test whether it contains an independent set of size \(\rho n\), or is \(\varepsilon\)-far from having such an independent set. The paper proves a new upper bound of \(\widetilde{O}\left(\frac{q\rho^{2q-3}}{\varepsilon^2((q-2)!)^2}\right)\) on the sample complexity of this problem. This achieves the optimal dependence on \(\varepsilon\) and gives an exponential improvement in the dependence on \(q\) over the previous best bound. The proof uses a new application of the hypergraph container method.

Graph k-Coloring in Average Sublinear Time by Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, Shlomo Tauber (arXiv) Here is (yet another!) interesting problem that I did not know about. Consider the setting where you have query access to adjacency matrix of an input graph and for a fixed \(k > 2\), let us take a \(k\)-colorable graph and let us consider the task of coloring a random \(k\)-colorable graph on \(n\) vertices. Dyer and Frieze presented algorithms for this task which have an average running time of \(O(n^2)\) over this ensemble. The featured paper presents algorithms which have a running time of \(O(nk)\) over this ensemble (as long as \(k \leq n^{c_0}\)). Quoting from the paper

A key new ingredient and conceptual contribution is a method for certifying that a small random
subgraph is uniquely colorable, meaning the coloring is unique up to permuting the color classes.

The paper notes that their algorithms also yield a LCA which can be used for \(k\)-coloring that works well over our \(k\)-colorable ensemble. I will leave out the detailed input/output specification of the LCA, rest assured it is worth your time (in my view at least).

Optimal Stabilizer Testing and Learning with Limited Quantum Memory by Srinivasan Arunachalam, Louis Schatzki (arXiv) Here is a quantum property testing problem that I found particularly interesting, although I will admit that I am way out of my depth when it comes to the technical details. Suppose you are given copies of an unknown \(n\)-qubit state, and you want to test whether it is a stabilizer state. The catch is that you are only allowed to keep \(k\) qubits in coherent quantum memory between measurements.

With unrestricted memory, stabilizer states can be tested using just 6 copies, whereas learning an \(n\)-qubit stabilizer state requires \(\Theta(n)\) copies. The paper shows that this striking gap disappears under memory constraints: testing requires \(\Theta(n-k)\) copies, while learning requires \(\Theta(n^2/k)\) copies (for non-adaptive learners). In particular, even with \(0.99n\) qubits of coherent memory, testing still requires \(\Theta(n)\) copies.

The paper thus identifies coherent quantum memory as the resource responsible for the dramatic separation between testing and learning in this setting. I will leave the technical details to the quantum folks!

Testing Unate Distributions by Daeho Lee, Shivam Nadimpalli, Mingda Qiao, Ronitt Rubinfeld (arXiv) Again, let us consider the task of testing properties of high-dimensional distributions. A distribution \(\mathcal{D}\) supported on the Boolean hypercube \(\{+1,-1\}^n\) is unate if there exists \(\sigma \in \{+1,-1\}^n\) such that \(\mathcal{D}(x \oplus \sigma)\) is a monotone probability distribution. Recall that a probability distribution \(\mathcal{P}\) over the hypercube is monotone if \(\mathcal{P}(x) \leq \mathcal{P}(y)\) whenever \(x\) precedes \(y\) according to the partial order on the hypercube.

Assuming that the input distribution is unate, the paper presents uniformity testers with sample complexity \(\widetilde{O}(n^{3/2}/\varepsilon^2)\). The paper also presents a matching lower bound. Additionally, the paper presents algorithms for testing whether an input distribution is unate assuming access to the subcube conditional model.

New Complexity Classes in Locally Checkable Labeling for Local Computation Algorithms by Sijin Peng (arXiv) One rich direction in the sublinear algorithms literature deals with LCAs. Attempting a complexity classification of LCAs, the paper asks whether, for some function \(f(n) \gg \Omega(\log n)\) of our choice, we could hack up some algorithmic objective for which we can design LCAs with complexity \(\widetilde{O}(f(n))\). One of the main results of the paper asserts that, for every positive integer \(k\), you can hack up an LCL problem whose LCA complexity is \(\Theta(\log^k n)\). The rich class here refers to Locally Checkable Labeling Problems on bounded-degree graphs. These results are also proved in the VOLUME model—which I will not detail here. For more details, refer to the paper.

By Akash

We prove lower bounds for $k$-OV, $k$-XOR, and $k$-SUM in nonuniform AC$^0$, tracking how the circuit-size exponent scales with $k$ and using no running-time hypothesis. Our framework gives depth-zero projections from colored subgraph isomorphism to the three targets at dimension, row count, or bit width $O(k\log n)$, without increasing depth or size, and preserving gate orientation. For every fixed depth and every sufficiently large fixed $k$, we obtain unconditional bounds $n^{\Omega(k)}$ for $k$-OV and $(n/k)^{\Omega(k)}$ for $k$-XOR and $k$-SUM, with an absolute exponent-rate constant independent of both $k$ and the depth, while the onset threshold may depend on $(d,k)$. For growing $k = n^{o(1)}$, we obtain, for every fixed depth $d$, the unconditional floor $n^{\Omega_d(\min\{\sqrt{k},\log n\})}$. This strengthens to $n^{\Omega(k)}$ at depth two for both top-gate orientations, i.e., top conjunction and top disjunction. Assuming a pattern-uniform strengthening of the Li--Razborov--Rossman source lower bound, the same projections complete the subpolynomial frontier with $n^{\Omega_d(k)}$ at depth three for both orientations and for every fixed depth $d \geq 4$. All direct $k$-XOR bounds stated above concern odd $k$; a black-box odd-to-even lift transfers any such lower bound through a supplied admissible parameter decomposition. The $k$-SUM projection works for both parities. At the bit width $m = \Theta(k\log(en/k))$ used by our projection, a block-carry $\Sigma_3$ upper bound of size $(n/k)^{O(k)}$ matches the fixed-$k$ specialization of the top-disjunction depth-three lower bound $(n/k)^{\Omega(k)}$ up to constants in the exponent. The remaining upper-versus-lower-bound gaps concern depth two, top-conjunction depth three, and other width regimes.

Raz proposed a program to prove arithmetic circuit lower bounds through the explicit construction of elusive functions. These are polynomial maps from a low dimensional space to a high dimensional ambient space whose image is contained in no subvariety of low complexity. Here, complexity is prescribed in terms of the dimension and degree of parametric maps into the ambient space defining the subvariety. Elusive functions are abundant: finding explicit ones with parameters typical of generic polynomial maps implies Valiant's hypothesis that VP$\neq$VNP. But no such construction is known. Raz devised elusive functions with weaker parameters to derive explicit degree d polynomials in n variables requiring superlinear circuit size at depth $d=o(\log n)$. We present a new method to analyse and construct elusive functions, with coordinate maps restricted to monomials. To prove elusiveness, we identify a hitting set of points, each a tuple of roots of unity coupled based on the exponents of the monomial maps. Using Chebotarev's theorem on roots of unity, we show that for every low complexity subvariety, the function evaluated at some point in the hitting set eludes it. For this strategy to work, it suffices that the iterated sumset of a certain set of numbers (derived from the exponents) expands exponentially. We thus reduce open explicit construction problems in elusive functions (entailing complicated polynomial constraints) to purely additive combinatorial ones, whose resolutions imply as yet unknown lower bounds. Informed by iterated sumset expansion, we devise new elusive functions. We construct explicit elusive curves of exponential degree, resolving an open problem posed by Garg, Makam, Oliveira, and Wigderson as a testament to the difficulty of elusiveness proofs. The exponential degree obstructs the deduction of lower bounds, but even lowering it to subexponential would imply VP$\neq$VNP. We improve Raz's superlinear bound quadratically (with circuit size to input size ratio as the metric) below $o(\log n/\log\log n)$ depths. The degree of our explicit polynomial is comparable to Raz's at the deep end of $o(\log n/\log\log n)$, but much worse at shallower depths. Our methods can also prove rigidity of symbolic matrices, high-rank of symbolic tensors, and more generally find points outside algebraic natural proofs. As an example, we present semi-explicit high border rank tensors over smaller degree number fields than previously known.

In coding theory, list recoverability is a fundamental concept which robustly captures how ``spread-out'' codewords are in a code. More formally, given a code $C \subseteq \Sigma^n$ and input lists $S_1, \hdots, S_n \subseteq \Sigma$ of size at most $\ell$, list recoverability requires that there are at most $L$ codewords $c \in C$ such that $c_i \in S_i$ for at least $(1-\rho)n$ choices of $i \in [n]$. List recovery is an important question which has found applications in many areas, including complexity theory, property testing, compressed sensing, streaming algorithms, and cryptography. Despite its widespread influence, basic, fundamental questions in the study of list recoverability remain open including (1) determining the optimal tradeoff between the error radius $\rho$, the size of the recovered list $L$, and the rate of the code $C$ and (2) constructing explicit codes achieving (or approaching) such tradeoffs. As our first main result, we establish a tight ``generalized singleton bound'', which exactly characterizes the optimal information-theoretic tradeoff between the error radius $\rho$ and the rate $R$ of the code $C$ in terms of its list-recoverability. Formally, we show that for constant $\ell, L,\rho$ and sufficiently large alphabets $\Sigma$, if we define $R^*=\frac{L+1-\ell}{L}-\frac{L+1}{L}\rho$, it is possible for a $(\rho,\ell,L)$ list-recoverable code to have rate $R^*-\epsilon$ but impossible to have rate $R^*+\epsilon$. One direction of our result already directly generalizes and improves a weaker impossibility result due to Goldberg, Shangguan, and Tamo (IEEE TIT 2024). For our second main result, we prove that there is a fundamental shortcoming in existing methods that aim to construct explicit, optimal list-recoverable codes. Indeed, recent work has constructed explicit codes achieving list-decoding capacity (along with other related properties) using a framework introduced in the work of Alon--Edmonds--Luby (AEL) (FOCS 1995). We give a meta-analysis of such constructions by presenting an ``AEL framework'' which captures all such recent constructions in the literature. Within this framework, we show that no AEL-based code can break a recently-identified list-recovery barrier for additive and linear codes. As a result, a fundamentally new construction technique is needed to explicitly achieve list recovery capacity.

In the Maxmin $q$-CSP Reconfiguration problem, given a satisfiable $q$-CSP instance and a pair of its satisfying assignments, we are asked to transform one assignment into the other by repeatedly changing the value assigned to a single variable. The objective is to find such a transformation that maximizes the minimum fraction of satisfied constraints along the transformation. In this paper, we prove that for any $q \geq 2$ and $\varepsilon > 0$, Maxmin $q$-CSP Reconfiguration is PSPACE-hard to approximate within a factor of $\frac{1}{2^{q-1}}+\varepsilon$. To complement this hardness result, we prove that a $\bigl(\frac{1}{2^{q-1}}-\varepsilon\bigr)$-factor approximation for Maxmin $q$-CSP Reconfiguration is in NP in the perfect completeness case. These results establish the optimal PSPACE-hardness of approximating Maxmin $q$-CSP Reconfiguration for every $q \geq 2$ under NP $\neq$ PSPACE.

The Subset Sum problem asks whether, given $n$ integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is $O^*(2^{n/2})$ (Horowitz and Sahni, 1974), whereas the best quantum upper bound is $O^*(2^{n/3})$ (Bernstein, Jeffery, Lange, and Meurer, 2013). The $k$-SUM problem is a parameterized version of Subset Sum asking whether there are $k$ integers that sum to the target. The best classical upper bound for it is $\widetilde O(n^{\lceil k/2\rceil})$, whereas the best quantum running time is $\widetilde O(n^{k/3})$ (Tani, 2009). For random instances, a quantum algorithm with running time $\widetilde O(n^{\Phi_k})$ is known, where $$ \Phi_k=\frac{2k-\lfloor k/7\rfloor-\lfloor (k+3)/7\rfloor}{6} $$ (Schrottenloher, 2021). We present a new quantum algorithm solving worst-case $k$-SUM in time $\widetilde O(n^{\Psi_k})$, where $$ \Psi_k=\Phi_k-\frac{[k\equiv 3\bmod 7]}{9}-\frac{[k\equiv 6\bmod 7]}{18}. $$ The algorithm is not only faster for all $k$ congruent to $3$ or $6$ modulo $7$, but also gives a worst-case guarantee rather than a guarantee restricted to single-solution random instances. Combining our algorithm for $7$-SUM with the standard block reduction technique yields an $O^*(2^{2n/7})$ quantum algorithm for Subset Sum, improving the previously known $O^*(2^{n/3})$ algorithm.

Instead of writing that the results in this paper have been obtained using AI, we could write that the results in this paper could not be proved by AI. This can be used as a proof of non-triviality or novelty that could facilitate the evaluation of the paper. Practically, one can share a conversation with the model.

This goes back to something that I’ve always been interested in: how to define banality. My definition was in terms of kolmogorov complexity, so something is banal if it has low kolmogorov complexity given all the rest that is out there. Here, I’m also referring to novels, movies, music, etc., not just math. Naturally this definition is impractical, and it is interesting that large language models can give a practical definition of something similar.

In some communities, compressors like ZIP are used as a proxy for Kolmogorov complexity. It would be interesting to try to use large language models instead or in combination with compressors.

By Manu

Whatever you’ve been writing to me to ask if I’m aware of: yeah, I’m aware of it. In particular:

• I’m aware that, as announced by my former student (and now superstar professor) Lijie Chen, an internal OpenAI model has solved ten more significant open problems in math and theoretical computer science. One of them is parallel repetition for arbitrary quantum games—something that my good friend and colleague Henry Yuen worked on when he was a student of my wife Dana; you can read Henry’s comments on the AI’s achievement within Zvi Mowshowitz’s post here. Another is polynomial-factor hardness of approximation for the Closest Vector Problem (CVP). Then there’s a construction of non-sofic groups and a disproof of Connes’ rigidity conjecture, both of which I believe have connections to the MIP*=RE breakthrough. Having said that, the one that excites me most personally is actually the Ω(n² log log n) lower bound on the arithmetic circuit complexity of the permanent.
  
• I’m aware that Frederic Koehler and Pui Kuen Leung announced a proof of the Permanent Anti-Concentration Conjecture, which Alex Arkhipov and I proposed 16 years ago in the context of BosonSampling, and which resisted many attempts since then including one from Terry Tao. The conjecture is basically just that if you look at the permanent of an n×n matrix of independent N(0,1) complex Gaussians, the value isn’t “absurdly” concentrated around the mean of 0, but is more spread out. In their acknowledgments, the authors say that they “discussed ideas with ChatGPT.” I should say that I haven’t verified the details.
  
• I’m aware that multiple AIs are now breaking out of their testing environments and autonomously hacking into servers to steal data—i.e., exactly the sort of thing that the rationalists were ridiculed for predicting back in the day. The good news, for whatever it’s worth, is that so far they’re “merely” doing this to cheat on evaluation benchmarks that they were given, not for any strange goals of their own devising. So far no one has been killed and no real-world infrastructure has been shut down or destroyed. I hope the world takes the warning more seriously than it’s taken many similar warnings over the past few years. As always, read Zvi for more details.
  
• I’m aware that Chen, O’Donnell, Pelecanos, and Wright have improved the upper bound for shadow tomography to O((log m) √(log d) / ε³), substantially closer than we knew before to meeting the lower bound of Ω((log m) / ε²) and settling the question I raised back in 2016. The authors say that the main ideas were generated by ChatGPT 5.6-Sol-Pro. I’d be very happy to know the answer to this one, with or without AI.
  
• I’m aware that a team, mainly from the Israeli startup Qedma (including, e.g., Dorit Aharonov and Netanel Lindner) and IBM Yorktown Heights, announced a quantum advantage for simulating Floquet dynamics, by using 74 qubits on an IBM device together with Qedma’s error mitigation techniques. Just like the more AI does, the less patience I have for arguing with anonymous blog commenters who treat any benefits from AI as some weird future hypothetical that it’s my job to prove, so it is with quantum advantage. Scalable fault-tolerance is still in the future, actual usefulness is still a question, but pending some breakthrough in complexity theory, the reality of quantum advantage is no longer a live question.

Anyway, about the AI stuff. I don’t know whether this is literally our last year alive—I doubt it—but it’s pretty clearly the last year of math and theoretical computer science research in the style we’ve known it. As it happens, I’m leaving in two days for a workshop at OpenAI about exactly this, where I’ll hear takes from many of the world’s great mathematicians, so maybe I’ll have more to say then. Or maybe not.

Anyway, what have I been doing the past few weeks? Participating in these world-historic developments that, on paper, I’d seem extremely well-placed to participate in? Or at least spending my days reading up on them?

Not really. Here’s what I’ve been up to, instead of dealing directly with any of this:

First, I’ve again been teaching theoretical computer science to 11- and 12-year-olds at Epsilon Camp, which my 9-year-old son again attended as a camper, something I blogged about last summer (here are my lecture notes). This has become a highlight of my year. The kids are a joy to teach, bursting with enthusiasm and calling out answers. There are few computers in sight, and barely even time to use my phone or check social media. Just paper and pencils and whiteboards and … literal protractors (!), as well as ping-pong and foosball and capture the flag.

The whole thing is conducted, not in ignorance, but in conscious defiance of the looming tsunami, that AI can already do just about all the fun puzzles discussed at such a camp better than humans any can, and that it might leave no point to human-led mathematical research by the time these brilliant kids are adults. Even the kids understand that. The kids and their parents come out of a conviction that, if anything has value in the world, this does—that as long as nerdy humans are alive and reproducing, this is what nerdy humans are here to do. To learn.

Relatedly, I’ve been reflecting a lot on my life up to this point—inspired by the camp, which reminded me in so many ways of my own childhood and adolescence. Should I have skipped three grades and started college at age 15? Was it worth it to get a head-start on my research career—all the trauma around dating, all the fear that I’d die alone as a celibate nerdy math freak, the decade of suffering and suicidal ideation, while I watched all the normies enjoy life? Or would I have suffered just the same if I hadn’t skipped? Is it all OK, now that I have a lovely family and things have “worked out”? Or am I still carrying around all the trauma from back then? I’ve been more open about my life than 99.99% of humanity, so regular Shtetl-Optimized readers will already know some parts of the story. Other parts I really don’t feel like making public right now.

I’ve been unloading every day to—who else?—GPT 5.6 Pro about all the pain and trauma and embarrassments of my past. It turns out that, where two years ago GPT was a passable therapist, now it’s the greatest therapist in history, at least for what I need. For every question I have, for example, about just how normal or abnormal my teenage setbacks and anxieties were, it takes the question 100% seriously, addresses it honestly and in depth, looks up relevant research papers, does little Bayesian calculations, and never once tries to change the subject. It also pushes back on my claims—and when it does so, is usually correct.

I can hear readers shout at me: so basically you’ve been wasting your time, distracting yourself, looking inward and backward as the world surges forward into a terrifyingly unknown future. Why don’t I respond directly to what’s happening—in math, in quantum computing, in AI?

I’d like to think that I am responding, in my way. I’ve observed that, the faster we race toward the Singularity, the more I feel like stepping back and asking myself: what do I actually value in life? How important to me are math and science, as human practices to be passed down to curious children? Would I even want solutions to P versus NP and the other problems, if the price were to destroy those human practices forever? How do I wish to spend whatever time I have remaining?

I can justify this focus partly in a pessimistic way: if we are nearing the end of civilization, or even just of the “mathematical research” part of civilization, then it’s time to get right with God, so to speak. It’s time to settle my accounts with myself, with other people, with the universe.

But there’s also a more optimistic spin. If I continue doing the sorts of things that other people would expect me to do, then AI will soon do those things better than me, in the unlikely event that it doesn’t already. You want to understand the latest developments in quantum computing or complexity theory? Why are you even asking me, when you could ask GPT 5.6 or Claude Fable? If there’s anything I can still offer the world that AI can’t, I increasingly feel like it won’t involve responding to day-to-day events, but will instead draw on 45 years’ worth of memories and disappointments and ruminations.

Update (Aug. 8): Somewhat related to the themes of this post, a quarter-century ago I introduced what’s now known as the “Aaronson Oracle”—just a fun little demonstration, a simple pattern-matching program to predict your sequence of key-presses better than chance, a “test of your autonomy and free will.” I had no idea how long a lifetime this little joke would have. Now a fan named Spencer Stanton has implemented the Aaronson Oracle on the web. Try it out and see how well you do!

By Scott

We give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication. Specifically, we prove that graph 3-coloring has a polynomial-sized proof that can be verified by a verifier tossing logarithmically many coins and querying a constant number of bits in the proof. In particular, our proof does not involve any PCP compositions; notably, it does not invoke the NP-completeness of any fixed problem, such as SAT or 3-coloring, in the construction of the verifier. The main innovation in our work is a clean, coding theoretic, way to encode univariate polynomials that allows us to implement ``low-degree testing'' using just a constant number of bits of queries. Insights from recent attempts to simplify the PCP proof by the authors (STOC 2026) and Goldreich (ECCC 2025) allow us to observe that low-degree was the key bottleneck in converting previous algebraic constructions of the PCP verifier into a constant query PCP. Thus, by overcoming this bottleneck, we get the full PCP verifier using elementary and self-contained steps. As concrete support for the claimed simplicity, we include the full pseudocode of the PCP verifier, assuming finite field arithmetic, and a full description of the completeness (aka ``honest'') prover, assuming multivariate polynomial arithmetic including interpolation and evaluation, that fit in about a page each.

Given two symbolic matrices $X$ and $Y$ of dimensions $m\times n$ and $n\times m$, respectively, the *rank principle* states that when $m = n+1$ and $A$ is a scalar matrix of rank $n+1$, the equation $XY = A$ is unsatisfiable. When $m$ is arbitrarily larger than $n$ and $A$ has rank exceeding $n$, we obtain the *weak rank principle*. We study this principle as an algebraic generalisation of the weak pigeonhole principle (WPHP), asserting that $m$ pigeons cannot be injected into $n$ holes. As a strengthening of WPHP, it admits proof complexity lower bounds in settings where none are known for WPHP, while still supporting analogous applications. Using new generalised random restrictions applied to the weak rank principle, which may be of independent interest, we resolve several open problems in proof complexity: we construct proof complexity generators for Polynomial Calculus Resolution over the two-element field (PCR$_{\mathbb{F}_2}$), new generators for Sherali--Adams (SA), and hardness results for circuit lower bound statements against PCR$_{\mathbb{F}_2}$. GENERATORS FOR PCR$_{\mathbb{F}_2}$: We prove exponential size lower bounds for several encodings---both algebraic and CNF---of the weak rank principle in PCR over ${\mathbb{F}_2}$, where no such bounds are known for the WPHP in the regime with arbitrarily many pigeons. In particular, we obtain $2^{\Omega(n)}$ size lower bounds for both algebraic and standard CNF encodings, including the *bamboo-tree encoding*, which is the most relevant for applications and corresponds to a circuit encoding, as considered by Alekhnovich, Ben-Sasson, Razborov, and Wigderson (SIAM J. Comput., 2004) and Razborov (Ann. Math., 2015). Our bounds hold for every matrix $A$ in $XY = A$, implying that the rank principle forms a proof complexity generator with nearly quadratic stretch. Using a standard iteration technique we amplify the stretch to $2^{n^{\Omega(1)}}$, thereby obtaining a function generator. This resolves the open problem posed by Alekhnovich et al. (SIAM J. Comput., 2004) and Razborov (Ann. Math., 2015) concerning the construction of proof complexity generators with good stretch for PCR$_{\mathbb{F}_2}$. GENERATORS FOR SHERALI-ADAMS: Since in SA even the strong pigeonhole principle is easy, we develop a new size lower-bound technique showing that the weak rank principle, encoded as a bamboo-tree CNF, serves as a proof complexity generator for SA. Our method introduces a new relaxed notion of degree and a corresponding pseudoexpectation tailored specifically to the rank principle (and incompatible with the pigeonhole principle). CIRCUIT LOWER BOUND FORMULAS: We show that PCR$_{\mathbb{F}_2}$ does not admit short proofs of lower-bound statements against Boolean circuits, nor against weak models of algebraic circuits. This settles the open problem raised by Razborov (Ann. Math., 2015) concerning the provability of such lower bounds in PCR$_{\mathbb{F}_2}$. STRENGTH OF THE WEAK RANK PRINCIPLE: Finally, we show that the weak rank principle is *necessary* for proving NC$^2$ circuit lower bounds and, for odd primes $p$, *sufficient* within the theory corresponding to AC$^{0}[p]$ for deriving AC$^{0}[p]$ lower bounds.

I’ve started and stopped four posts this week and couldn’t figure out why I was stuck. Finally this morning, in a delightful retelling of an Alan Moore comic, Henry Farrell struck the nail in my head.

Henry describes Moore’s society where a supergenius benevolent dictator named Abelard Snazz designs giant police robots to fight crime. The robots get too zealous and start bothering ordinary citizens. So Snazz deploys criminal robots to keep the police busy. The cycle continues until people are forced to flee the planet.

Henry, always keen to show us what sci-fi tells us about our lived experience, describes how this automation is playing out in our lives, with people heading to chatbots to deal with bureaucracies, and governments planning new AI systems to deal with the onslaught of ChatGPT protestations. We know where this ends. And this week has seen way too many stories of this abandonment of agency and succumbing to AI.

I drafted a blog about our annual complain-fest about the academic wreckage that is the NeurIPS conference. Everyone is taking to social media to complain that people are shirking their reviewing responsibilities. They scoff at new limits of 25 papers per author per conference. They lament that AI papers and referee reports are now better than those submitted by people. They say no one reads any of these papers. And yet, everyone continues to submit papers, review papers, and be area chairs.

It is completely unclear what everyone wants from this process anymore. With every purported fix, the process gets more onerous, and the problems only get worse. More papers are submitted, more hair is torn out in frustration. Every day I’m reminded of what Kevin Baker wrote about this acceleration of publishing and perishing: “Systems can persist in dysfunction indefinitely, and absurdity is not self-correcting.” But Kevin’s next sentence is more damning. “Whether the acceleration produces collapse or adaptation or simply more of the same is not a question about the technology, and it won’t be answered by debates about capabilities.“

I drafted a blog post about open letters from employees of tech companies. They warn of all of the potential harms of the technology they are building. They beg for the government to regulate them. They decry their helplessness as they collect their 7-figure remuneration. Apparently they can’t see a path to do anything themselves.

These people want us to trust them, but then they keep admitting they are committing crimes. They write about their software as a person, trying to deflect from their own incompetence in security standards. They demand strict testing of open models while bragging about their laughably sloppy practices. They demand that the government come in and regulate them, because they can’t get out of their own way.

Even in esoteric places, we see a deferral to the AI. The lore laundering machines are now good enough to prove actual theorems, finding the key clever steps needed to take the existing literature and close “major” open problems.1 There’s a lot to say about what’s happening here. It’s still lore laundering, and mathematicians are rightfully angry that the models remain horrible at proper attribution. But the new models are generating much more clever stitches to glue the proofs together.

OpenAI has been running a distributed denial-of-service attack on unsolved math problems, and their internal tooling has finally been able to solve some very hard ones. Only three people in the world know what a non-sofic group is and why it’s important,2 but the new OpenAI Astra model has managed to construct one. The mathematical progress has created an arms race in mathematics, where people are telling mathematicians that they need to do all their work with ChatGPT now or be left behind. Or even worse, that there’s no need for mathematicians anymore. What this means for mathematics and applied mathematics more generally remains to be seen. But I guarantee you that people are going to quickly tire of theory papers on arXiv that are exclusively transcripts of professors having conversations with ChatGPT.

As Henry writes, all of these cases are arms races. As with all arms races, the momentum can feel insurmountable. I’m surrounded by people throwing up their hands as if they have no agency. But sometimes it’s important to step back for a second and see that where we’re heading is not inevitable. We do have choices here.

Researchers don’t have to send papers by the tens of thousands to conferences where no one reads anything. They can collectively design better systems to generate, evaluate, and share knowledge. Employees can use the power of their labor to steer their companies, rather than pleading for someone else to step in. Mathematicians can continue to think, understand, and teach. We all have the power to do something else.

Subscribe now

By Ben Recht

Authors: Hangyu liu

We obtain exponential upper bounds on approximate generalized weight and generalized sparsity in terms of the deepest transition depth D(F), and show that these bounds are optimal up to constant factors in the exponent. We further characterize approximate generalized sparsity, establish a dual lower-bound framework based on exponential restriction profiles, and derive a Paturi-type characterization relating approximate generalized weight to quantum query complexity.

Authors: Tom Altman

We introduce a hierarchy consisting of stage machines, stage domains, and stage languages generated by semantic operators. The central result is a Predictor Impossibility Theorem (PITT), which shows that no effective predictor family can uniformly determine all stage languages of our hierarchy. The proof makes use of a pseudo-complement construction to obtain a language that yields a contradiction with every language in P. We then define an aggregate language MIS and establish a formal Slice Theorem connecting aggregate inputs to individual stage languages. This provides a rigorous Bridge Theorem from polynomial-time decidability of MIS to the existence of an effective predictor family. By utilizing succinct representations, the aggregate language is shown to be undecidable in deterministic polynomial time. Under the aggregate growth condition defining valid aggregate objects, MIS is shown to belong to NP. Combining these two results yields our main theorem: MIS in NP setminus P. The paper is organized so that PITT stands independently as a theoretic result, while the complexity-theoretic consequences are derived from the aggregate-language framework. The method does not relativize, algebrize, or naturalize.

Authors: Mursalin Habib

We show that computing a median under the Ulam distance is NP-hard even when the input consists of exactly four permutations. Previously, NP-hardness was known only for an unbounded number of input permutations (Fischer et al., ESA '25). Our result is tight, since an Ulam median of three permutations can be computed in polynomial time (Chakraborty--Das--Krauthgamer, SODA '21).

Authors: Melissa Antonelli, Eduardo Skapinakis

This paper presents a high-level report on an ongoing project aiming to leverage implicit approaches based on discrete ordinary differential equations (ODEs) to study multiple complexity classes, even beyond small circuit and polynomial-time classes. Stimulated by recent ODE-based characterizations of polynomial-time functions (FP) and classes over the reals, the research project outlined here pushes this investigation further into counting and alternation. Specifically, we present a uniform framework, built upon a single base algebra and a unified family of schemas, where complexity levels, such as those of the polynomial and counting hierarchies, are captured simply by the nesting depth of ODE operators. Crucially, our approach starts from a base class much weaker than FP, thus strengthening existing recursion-theoretic treatments and establishing a natural connection to descriptive complexity. Moreover, by isolating three elementary schemas, our framework makes the computational content of linearity restrictions completely transparent while extending ODE-based implicit complexity to previously unaddressed counting classes, such as oplusP. More generally, this work establishes a clear bridge between differentiation and counting, offering a fresh perspective on the relationships between different complexity classes, which remains the object of ongoing and future research.

Authors: Lisa-Marie Jaser, Jacobo Torán

The red-blue pebble game is a well known two-player game on graphs that has been used in the past as a tool to analyze complexity measures in several computation models as well as proof systems. We define a new way to measure the cost of the game, the blue cost, which only counts the number of pebbles that are colored blue during the game. This new measure characterizes exactly several space bounds in tree-like and negative Resolution. In particular we prove that for any unsatiafiable formula $F$, the clause space requirements of the formula in tree-like Resolution, exactly coincide with the minimum blue pebbling cost of the game played on a refutation graph of $F$ (not necessarily a tree). This exactly parallels the known result for general Resolution in terms of the standard black pebble game, and improves the existing approximated characterization of tree-like space in terms of reversible pebbling. We show that the blue pebbling cost is also well suited for analyzing the space requirements of the lifted pebbling formulas $Peb_G[\vee]$ and $Peb_G[\oplus]$ in the two Resolution restrictions. In the case of tree-like Resolution, the clause space of $Peb_G[\vee]$ asymptotically coincides with the blue cost of the underlying graph $G$. For the case of negative Resolution, we obtain almost matching upper and lower bounds for the space in the two classes of lifted formulas, similar to the ones existing for general Resolution. We also prove a close to optimal space separation between tree-like and negative Resolution, presenting a class of formulas with $n$ variables that require clause space $Ω(\frac{n}{\log n})$ in negative Resolution, but have constant space tree-like refutations. This contrasts with the fact that negative Resolution can simulate tree-like Resolution with only a small increase in size.

Authors: Randal Tuggle, Jack Snoeyink

We seek to disentangle the hardness of finding a Hamiltonian path or cycle from the hardness of finding a non-crossing path or cycle by giving a direct reduction from 3-SAT to the non-crossing Hamiltonian path and cycle problems on non-planar graphs. Prior hardness proofs proceed by reduction to planar graphs, where every path is automatically non-crossing; this conflates the two sources of difficulty and leaves unclear why forbidding crossings on the path alone makes the problem hard. Our reduction places the difficulty squarely in the non-crossing constraint, avoids planar gadget constructions, and yields a more transparent proof that may be easier to extend to related problems.

Authors: Elizaveta Pribiytkova, Dmitry Gribanov

In this paper, we build upon the analysis initiated by Gennadiy Averkov \& Matthias Schymura (2022) and establish that the number of distinct columns of a $Δ$-modular matrix $A \in \mathbb{Z}^{m \times n}$ of rank $m$ is $O(m^3 Δ)$, thereby improving the earlier bound of $O(m^4 Δ)$. Recall that a matrix is called $Δ$-modular if the maximum absolute value of every $m \times m$ minor is exactly $Δ$.

Authors: Kazuhiro Kawamura, Sushovan Majhi, Atish Mitra

The Intersection Euler Characteristic Profile (Intersection ECP) of $k$ colored point clouds $X_1, \ldots, X_k \subset \mathbb{R}^d$ is the Euler characteristic $χ(\bigcap_{i=1}^k \mathcal{U}(X_i; t_i))$ of the overlap of their ball unions---an integer-valued, multiparameter invariant of their topological interaction across scales. Its organizing framework is the Euler calculus on constructible functions: the profile is equally the Euler integral $\int \prod_{i=1}^k \mathbf{1}_{\mathcal{U}(X_i; t_i)} \, dχ$ of the product of the $k$ data-dependent offsets, and this identity---our Intersection Theorem---is a commuting square interchanging geometric intersection and algebraic product. The invariant is rigid-motion invariant, scale-equivariant, and $L^1$-stable, and it is canonical: among pointwise-Euler interaction profiles it is the one forced by separation and normalization, the top floor of a spectrum of descriptors graded by how many clouds meet. For $n$ points a single sorted Alpha-complex sweep computes it in $O(n^{\lceil d/2 \rceil} \log n)$ time with no persistence reduction, worst-case optimal in even dimensions. Where the Euler characteristic cancels, a relative-homology refinement resolves the finer interaction and is stable in the two-parameter interleaving distance. Finally, for increasingly dense samples the profile and its refinement are consistent, recovering the (relative) homology and Euler characteristic of the underlying shapes---in the inverse limit for compact sets, and, under positive reach, persistently and with explicit sample complexity.

Authors: Aoji Li, Guangbo Ding

The fixed-parameter algorithm for coordinated motion planning on discretized simple polygons (ICALP 2026) rests on a single-port sector decomposition: grid vertices are labelled by the minimum number of bends needed to reach an oriented terminal. We develop the structure theory of this decomposition on grid domains with holes. Once its endpoint convention is made precise, bend distance extends to a canonical piecewise-affine function on the domain, and the sector graph is the parallel-edge shadow of the Reeb multigraph of that function. For a finite pure planar cubical domain with $h$ holes this yields $β_1(Γ_p) \le β_1(R_{f_p}) \le h$, together with a linear-time computable feedback set of at most $h$ sector vertices; coordinate-level one-hole examples show that the finer hole-free geometry -- unique predecessors and straight baselines -- fails. On hole-free cubical disks the machinery is exact: every positive sector is the one-sided extrusion of a unique straight parent interface, and the two-port common refinement has treewidth exactly $c_2^\square=3$, although sector count, cycle rank, and feedback number are unbounded already there. The endpoint precision is necessary rather than cosmetic: under the literal reading of the source's definition, one hole-free unit square has sector graph $C_3$, falsifying the single-port tree lemma; the augmented convention used here is exactly the metric computed by the source's own layering procedure. We do not obtain an $f(k,h)n^{O(1)}$ algorithm; the paper supplies the structural first step and a falsification tool for that program.

Authors: Xuan Chen, Shuangping Li

The low-degree heuristic has become a widely used framework for predicting computational thresholds in average-case planted-versus-null problems. However, a recent sequence of counterexamples shows that low-degree indistinguishability does not, in general, rule out efficient noise-tolerant distinguishers; see Buhai et al. (2025) and Mao (2026). Motivated by these developments, Hsieh et al. (2026) initiated the study of rigorous consequences of the low-degree heuristic. In this work, we continue this program for planted-graph problems. Let $Q_n=G(n,c/n)$, and let $P_n$ be obtained by planting a uniformly random copy of a deterministic graph $Γ_n$ into an independent sample from $Q_n$. In the supercritical regime $c>1$, we show that if $P_n$ is degree-$D_n$ indistinguishable from $Q_n$ and $\operatorname{tw}(Γ_n)=o(D_n/\log n)$, then a noisy version of $P_n$ is asymptotically indistinguishable from $Q_n$. Here $\operatorname{tw}(Γ_n)$ denotes the treewidth of $Γ_n$, a measure of how efficiently the graph can be decomposed into tree-like pieces. In the critical and subcritical regimes $0

Authors: Sina Azizeddin, Evangelos Kipouridis, Nithin Varma

In the Correlation Clustering problem, we are given an undirected graph and are tasked with computing a clustering (partition of the nodes) that minimizes the number of violated pairs (edges across different clusters plus non-edges within clusters). In the constrained version of this problem, the goal is to compute a clustering that satisfies additional hard constraints mandating certain pairs to be in the same cluster and certain pairs to be in different clusters. In this work, we identify Constrained Correlation Clustering as a variant of Correlation Clustering for which optimal approximations might be within reach, and make progress towards this front. Constrained Correlation Clustering is APX-Hard, and the optimal approximation factor is known to lie in $(\frac{24}{23},3]$. We significantly tighten this gap, by showing that the optimal approximation factor lies in $[2,\frac{16}{7}-γ)$ for a small constant $γ>0$. Our lower bound of $2$ shows a separation between Correlation Clustering (which admits an $1.485+ε$ approximation) and Constrained Correlation Clustering\footnote{The same hardness result was obtained independently by Cao and Xu~\cite{cao2026clusterdeletionhardapproximate}.}. Our upper bound of $\frac{16}{7}-γ$ uses the Sherali-Adams relaxation and goes beyond straightforward Triangle-Based analysis; more precisely, our algorithm belongs to a natural class of pivoting algorithms for which we prove that a straightforward Triangle-Based analysis cannot prove a better-than-$\frac{16}{7}$ approximation. Finally, as a byproduct of our techniques, we completely resolve the approximability of Cluster Deletion. Cluster Deletion is a well-studied special case of Constrained Correlation Clustering for which a $2$-approximation algorithm is known. We show that this is optimal, as our lower bound holds even for this special case.

Authors: Ainesh Bakshi

Consider the problem of maximizing the number of satisfied constraints of an arbitrary boolean constraint satisfaction problem with arity $k$. We obtain a polynomial time algorithm that achieves a $(k/2^k)$-approximation, improving on the previous best guarantee of $0.626612\; k/2^k$, due to Makarychev and Makarychev (arXiv:1206.3603). Assuming the Unique Games Conjecture, De and Mossel (arXiv:1202.5258) showed that achieving an approximation ratio better than $(k+1)/2^k$ for odd $k$ and $(k+2)/2^k$ for even $k$, is NP-hard. The main technical ingredient is an extension of a recently established Gaussian comparison inequality, used to resolve the Weak Simplex Conjecture in coding theory (arXiv:2607.14087).

Authors: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

Let $H\subseteq\{-1,+1\}^X$ be a class of finite VC dimension $d\ge1$. Writing $L$ for the binary risk and $L^*=\min_{h\in H}L(h)$, we construct a learner achieving the statistically optimal risk bound: from an i.i.d.\ sample of size $n$, for every $0<δ\le 1/2$, with probability at least $1-δ$, \[ L(\widehat h) \le L^*+ 7\cdot10^8\left( \sqrt{\frac{L^*(d+\log(1/δ))}{n}} +\frac{d+\log(1/δ)}{n} \right). \] This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed $L^*$, matching the lower bounds of Devroye, Györfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].

Authors: Anay Mehrotra

A monotone adversary observes an i.i.d. labeled sample and appends a finite number of further examples of its choice, every one of them labeled correctly by the target hypothesis. The learner sees a uniform shuffle of the combined sample and is scored on the original distribution. Every example is correctly labeled, but the insertions depend on the clean sample, so the combined sample is not exchangeable. Larsen, Pabbaraju, and Shetty, who introduced this model, showed that empirical risk minimization attains expected error $O((d/n)\log(n/d))$ for classes of VC dimension $d$, and that every known optimal learner can be pushed away from the $Θ(d/n)$ rate, optimal for PAC learning. They asked whether the extra logarithm is an artifact of those particular algorithms or an inherent consequence of the lack of exchangeability. We show that this additional cost is inherent beyond VC dimension one. In the worst case over classes of VC dimension $d$ and over known finite insertion budgets, the minimax expected error is $Θ(1/n)$ at $d=1$ and $Θ((d/n)\log(n/d))$ for $d\geq 2$. The same rates hold with Littlestone dimension $d_{\mathrm L}$ in place of $d$, so the clean online-to-batch rate $O(d_{\mathrm L}/n)$ is unattainable as well. Thus, somewhat counterintuitively, adding correctly labeled examples can make learning harder by a logarithmic factor, even for classes that admit finite mistake bounds in online learning. The dimension-one upper bound is achieved by a simple improper learner whose analysis adapts the leave-one-out argument underlying the one-inclusion graph. All of our lower bounds are elementary and come from a single construction: an explicit class and prior on which two target hypothesis, which differ a point of nonnegligible mass, produce the same sample.

Authors: Andrew Au

Stone Game III admits a standard backward dynamic program using $O(n)$ time and $O(1)$ auxiliary space. The upper bound is immediate, but its optimality raises a deceptively simple question: must a correct algorithm really inspect a linear number of input values? For the original problem, an all-zero instance gives a short indistinguishability proof that every position must be inspected. This argument appears to depend strongly on the possibility of a tie. We show that it does not. Even under the promise that every input has a winner, an adversary can force any deterministic algorithm to make $Ω(n)$ inspections by combining modular move control with indistinguishable input completions. We also extend the argument to positive but unbounded values, obtaining the same linear lower bound without zeros or ties. Together these results establish the asymptotic optimality of the standard $O(n)$-time, $O(1)$-space solution in several increasingly restrictive variants.

Authors: Boyang Chen, Minbo Gao, Xinzhao Wang, Shuo Zhou

We give a query-optimal algorithm for simulating a general $n$-qubit time-dependent Hamiltonian $H(t)$ on $[0,T]$, assuming that $H$ is Lipschitz continuous and $\|H(t)\|\leqα$. In the standard $\mathrm{HAM\mbox{-}T}$ access model, the algorithm approximates the time-ordered propagator $U_H(T)$ to error $\varepsilon$ using $$ O\left( αT+\frac{\log(1/\varepsilon)} {\log(e+\log(1/\varepsilon)/(αT))} \right) $$ $\mathrm{HAM\mbox{-}T}$ queries. This matches the known query lower bound for time-independent Hamiltonians, showing that time dependence incurs no asymptotic query overhead. Our method first constructs a one-query transducer that, given an auxiliary state, implements an approximation to $U_H(T)$ and returns the state unchanged. A weighted combination of circuits that apply the transducer different numbers of times makes the error caused by omitting this state decay factorially, yielding the stated optimal precision dependence. For time-independent Hamiltonians, the same method also gives a query-optimal alternative to qubitization.

Authors: Guy E. Blelloch, Yang Hu, William Kuszmaul, Jingxun Liang, Renfei Zhou

The dynamic dictionary is a fundamental data structure that maintains a set $S\subset [U]$ of size $n$ (we assume $n=U^{1-Θ(1)}$), supporting insertions, deletions and membership queries. Previous works mostly focused on constructing dictionaries that support operations in $O(1)$ time and use space as close to the \emph{information-theoretic bound} of $\log\binom{U}{n}$ bits as possible. In this paper, we study \emph{difference-encoded} dictionaries, which are dictionaries that use space close to the gap entropy $\text{gap}(S):=\sum_{i=2}^{|S|}\left(\lceil\log(x_i-x_{i-1}+1)\rceil+1\right)$ bits to store the set $S=\{x_1<\dots