Theory of Computing Report

“The next TCS+ talk will take place this coming Wednesday, March 18th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC). Chris Gartland from UNC Charlotte will speak about “”-Distortion of EMD over Grids“” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: The Earth Mover Distance (EMD) is a popular metric used in the comparison of probability distributions over a metric space, and low-distortion embeddings of this metric into is a commonly used approximation tool. We will discuss a general technique of using Sobolev-type inequalities to prove lower bounds for the -distortion of EMD. While the main focus will be on describing the specific Sobolev-type inequality for the planar grid , we will also mention results for the higher dimensional grids , . Based on joint work with Mikhail Ostrovskii, Yuval Rabani, and Robert Young.

“

By plustcs

A central goal in average-case complexity is to understand how average-case hardness can be amplified to near-optimal hardness. Classical results such as Yao’s XOR lemma establish this principle for Boolean functions, but these techniques typically apply only to artificially constructed functions, rather than to natural computational problems. In this work, we extend hardness amplification beyond the Boolean setting and extend the XOR Lemma to the sum of functions over the finite field $\mathbb{F}_p$, where $p$ is a prime. Specifically, we show that if a function $f \colon \{0,1\}^n \to \mathbb{F}_p$ fails to be computed on at least a $\delta$-fraction of inputs, then the $k$-wise sum $f^{+k}(x_1,\dots,x_k) = f(x_1) + \cdots + f(x_k)$ becomes almost optimally unpredictable: no efficient algorithm can compute it with success probability exceeding $\frac{1 + \varepsilon}{p}$ for suitable parameters $k,\delta,\varepsilon$. Our proof is based on the pseudo-average-min entropy characterization of unpredictability due to Zheng (2014) and Vadhan and Zheng (2012), which we simplify and quantitatively refine to make the dependence of the circuit blow-up on all parameters fully explicit. As an application, we obtain the first error-tolerant random self-reduction for a natural subgraph counting problem. Specifically, we show that any circuit that correctly counts triangles in an Erd?s--Rényi random graph with noticeable probability can be transformed into a worst-case circuit with only a quasi-linear overhead. We further extend the query lower bound framework of Shaltiel and Viola (2010) to the $\mathbb{F}_p$-valued setting, proving that any (possibly adaptive) black-box hardness amplification over $\mathbb{F}_p$ must make at least $\Omega(p\log(1/\delta)/\varepsilon^2)$ oracle queries. Our proof substantially simplifies the core \emph{fixed-set lemma} underlying previous analyses, offering a more modular and entropy-based argument.

Authors: Romain Peyrichou

Every formal grammar defines a language and can in principle be used in three ways: to generate strings (production), to recognize them (parsing), or -- given only examples -- to infer the grammar itself (grammar induction). Generation and recognition are extensionally equivalent -- they characterize the same set -- but operationally asymmetric in multiple independent ways. Inference is a qualitatively harder problem: it does not have access to a known grammar. Despite the centrality of this triad to compiler design, natural language processing, and formal language theory, no survey has treated it as a unified, multidimensional phenomenon. We identify six dimensions along which generation and recognition diverge: computational complexity, ambiguity, directionality, information availability, grammar inference, and temporality. We show that the common characterization "generation is easy, parsing is hard" is misleading: unconstrained generation is trivial, but generation under constraints can be NP-hard. The real asymmetry is that parsing is always constrained (the input is given) while generation need not be. Two of these dimensions -- directionality and temporality -- have not previously been identified as dimensions of the generation-recognition asymmetry. We connect the temporal dimension to the surprisal framework of Hale (2001) and Levy (2008), arguing that surprisal formalizes the temporal asymmetry between a generator (surprisal = 0) and a parser that predicts under uncertainty (surprisal > 0). We review bidirectional systems in NLP and observe that bidirectionality has been available for fifty years yet has not transferred to most domain-specific applications. We conclude with a discussion of large language models, which architecturally unify generation and recognition while operationally preserving the asymmetry.

Authors: Mathilde Bouvel, Valentin Féray, Xavier Goaoc, Florent Koechlin

Chirotopes are a common combinatorial abstraction of (planar) point sets. In this paper we investigate decomposition methods for chirotopes, and their application to the problem of counting the number of triangulations supported by a given planar point set. In particular, we generalize the convex and concave sums operations defined by Rutschmann and Wettstein for a particular family of chirotopes (which they call chains), and obtain a precise asymptotic estimate for the number of triangulations of the double circle, using a functional equation and the kernel method.

Authors: Manish Kumar, Othon Michail, Andreas Padalkin, Christian Scheideler

We study centralized reconfiguration problems for geometric amoebot structures. A set of $n$ amoebots occupy nodes on the triangular grid and can reconfigure via expansion and contraction operations. We focus on the joint movement extension, where amoebots may expand and contract in parallel, enabling coordinated motion of larger substructures. Prior work introduced this extension and analyzed reconfiguration under additional assumptions such as metamodules. In contrast, we investigate the intrinsic dynamics of reconfiguration without such assumptions by restricting attention to centralized algorithms, leaving distributed solutions for future work. We study the reconfiguration problem between two classes of amoebot structures $A$ and $B$: For every structure $S\in A$, the goal is to compute a schedule that reconfigures $S$ into some structure $S'\in B$. Our focus is on sublinear-time algorithms. We affirmatively answer the open problem by Padalkin et al. (Auton. Robots, 2025) whether a within-the-model sublinear-time universal reconfiguration algorithm is possible, by proving that any structure can be reconfigured into a canonical line-segment structure in $O(\sqrt{n}\log n)$ rounds. Additionally, we give a constant-time algorithm for reconfiguring any spiral structure into a line segment. These results are enabled by new constant-time primitives that facilitate efficient parallel movement. Our findings demonstrate that the joint movement model supports sublinear reconfiguration without auxiliary assumptions. A central open question is whether universal reconfiguration within this model can be achieved in polylogarithmic or even constant time.

Authors: Ezequiel Lopez-Rubio, Mario Pascual-Gonzalez

We present IsalGraph, a method for representing the structure of any finite, simple graph as a compact string over a nine-character instruction alphabet. The encoding is executed by a small virtual machine comprising a sparse graph, a circular doubly-linked list (CDLL) of graph-node references, and two traversal pointers. Instructions either move a pointer through the CDLL or insert a node or edge into the graph. A key design property is that every string over the alphabet decodes to a valid graph, with no invalid states reachable. A greedy \emph{GraphToString} algorithm encodes any connected graph into a string in time polynomial in the number of nodes; an exhaustive-backtracking variant produces a canonical string by selecting the lexicographically smallest shortest string across all starting nodes and all valid traversal orders. We evaluate the representation on five real-world graph benchmark datasets (IAM Letter LOW/MED/HIGH, LINUX, and AIDS) and show that the Levenshtein distance between IsalGraph strings correlates strongly with graph edit distance (GED). Together, these properties make IsalGraph strings a compact, isomorphism-invariant, and language-model-compatible sequential encoding of graph structure, with direct applications in graph similarity search, graph generation, and graph-conditioned language modelling

Authors: Mark Bun, Marco Gaboardi, Connor Wagaman

We resolve an open question of Jain, Raskhodnikova, Sivakumar, and Smith (ICML 2023) by exhibiting a problem separating differential privacy under continual observation in the oblivious and adaptive settings. The continual observation (a.k.a. continual release) model formalizes privacy for streaming algorithms, where data is received over time and output is released at each time step. In the oblivious setting, privacy need only hold for data streams fixed in advance; in the adaptive setting, privacy is required even for streams that can be chosen adaptively based on the streaming algorithm's output. We describe the first explicit separation between the oblivious and adaptive settings. The problem showing this separation is based on the correlated vector queries problem of Bun, Steinke, and Ullman (SODA 2017). Specifically, we present an $(\varepsilon,0)$-DP algorithm for the oblivious setting that remains accurate for exponentially many time steps in the dimension of the input. On the other hand, we show that every $(\varepsilon,δ)$-DP adaptive algorithm fails to be accurate after releasing output for only a constant number of time steps.

Authors: Paul Cazeaux, Mi-Song Dupuy, Rodrigo Figueroa Justiniano

We introduce the Block Sparse Tensor Train (BSTT) sketch, a structured random projection tailored to the tensor train (TT) format that unifies existing TT-adapted sketching operators. By varying two integer parameters $P$ and $R$, BSTT interpolates between the Khatri-Rao sketch ($R=1$) and the Gaussian TT sketch ($P=1$). We prove that BSTT satisfies an oblivious subspace embedding (OSE) property with parameters $R = \mathcal{O}(d(r+\log 1/δ))$ and $P = \mathcal{O}(\varepsilon^{-2})$, and an oblivious subspace injection (OSI) property under the condition $R = \mathcal{O}(d)$ and $P = \mathcal{O}(\varepsilon^{-2}(r + \log r/δ))$. Both guarantees depend only linearly on the tensor order $d$ and on the subspace dimension $r$, in contrast to prior constructions that suffer from exponential scaling in $d$. As direct consequences, we derive quasi-optimal error bounds for the QB factorization and randomized TT rounding. The theoretical results are supported by numerical experiments on synthetic tensors, Hadamard products, and a quantum chemistry application.

Authors: Oliver Kullmann, Edward Clewer

We present a study of minimal unsatisfiable subsets (MUSs) of 2-CNF Boolean formulas, building on the Abbasizanjani-Kullmann classification of minimally unsatisfiable 2-CNFs (2-MUs). We start by giving a linear-time procedure for recognising 2-MUs. Then we study the problem of finding one simple MUS. On the one hand we extend the results by Kleine Buening et al, which showed NP-completeness of the decision, whether a deficiency-1 MUS exists. On the other hand we show that deciding/finding an MUS containing one or two unit-clauses (which are special deficiency-1 MUSs) can be done in polynomial time. Finally we present an incremental polynomial time algorithm for some special type of MUSs, namely those MUSs containing at least one unit-clause. We conclude by discussing the main open problem, developing a deeper understanding of the landscape of easy/hard MUSs of 2-CNFs.

Authors: Matti Karppa

We introduce the Huffman-Bucket Sketch (HBS), a simple, mergeable data structure that losslessly compresses a HyperLogLog (HLL) sketch with $m$ registers to optimal space $O(m+\log n)$ bits, with amortized constant-time updates, acting as a drop-in replacement for HLL that retains mergeability and substantially reduces memory requirements. We partition registers into small buckets and encode their values with a global Huffman codebook derived from the strongly concentrated HLL rank distribution, using the current cardinality estimate for determining the mode of the distribution. We prove that the Huffman tree needs rebuilding only $O(\log n)$ times over a stream, roughly when cardinality doubles. The framework can be extended to other sketches with similar strongly concentrated distributions. We provide preliminary numerical evidence that suggests that HBS is practical and can potentially be competitive with state-of-the-art in practice.

Authors: Kangke Cheng, Shihong Song, Guanlin Mo, Hu Ding

In this paper, we investigate the learning-augmented $k$-median clustering problem, which aims to improve the performance of traditional clustering algorithms by preprocessing the point set with a predictor of error rate $α\in [0,1)$. This preprocessing step assigns potential labels to the points before clustering. We introduce an algorithm for this problem based on a simple yet effective sampling method, which substantially improves upon the time complexities of existing algorithms. Moreover, we mitigate their exponential dependency on the dimensionality of the Euclidean space. Lastly, we conduct experiments to compare our method with several state-of-the-art learning-augmented $k$-median clustering methods. The experimental results suggest that our proposed approach can significantly reduce the computational complexity in practice, while achieving a lower clustering cost.

Authors: Sang-il Oum, Marek Sokołowski

We study connectivity functions, that is, integer-valued symmetric submodular functions on a finite ground set attaining $0$ on the empty set. For a connectivity function $f$ on an $n$-element set $V$ and an integer $k\ge 0$, we show that the family of all sets $X\subseteq V$ with $f(X)=k$ admits a polynomial-size representation: it can be described by a list of at most $O(n^{4k})$ items, each consisting of a set to be included, another set to be excluded, and a partition of remaining elements, such that the union of some members of the partition and the set to be included are precisely all sets $X$ with $f(X)=k$. We also give an algorithm that constructs this representation in time $O(n^{2k+7}γ+n^{2k+8}+n^{4k+2})$, where $γ$ is the oracle time to evaluate $f$. This generalizes the low rank structure theorem of Bojańczyk, Pilipczuk, Przybyszewski, Sokołowski, and Stamoulis [Low rank MSO, arXiv, 2025] on cut-rank functions on graphs to general connectivity functions. As an application, for fixed $k$, we obtain a polynomial-time algorithm for finding a set $A$ with $f(A)=k$ and a prescribed cardinality constraint on $A$.

Authors: Matteo Stromieri, Emanuele Natale, Amos Korman

Target shape, not just size, plays a pivotal role in determining detectability during random search. We analyze intermittent Lévy walks in three dimensions, and mathematically prove that the widely observed Cauchy strategy (Lévy exponent $μ= 2$) uniquely achieves scale-invariant, near-optimal detection across a broad spectrum of target sizes and shapes. In a domain of volume $n$ with boundary conditions, expected detection time for a convex target of surface area $Δ$ optimally scales as $n/Δ$. Conversely, Lévy strategies with $μ< 2$ are slow at detecting targets with large surface area-to-volume ratios, while those with $μ> 2$ excel at finding large elongated shapes but degrade as targets become wider. Our results further indicate a continuous geometric transition: volume dictates detection near $μ= 1$, ceding dominance to surface area as $μ\to 2$, after which surface area and elongation couple to govern detection. Ultimately, 3D search introduces a pronounced sensitivity to target shape that is absent in lower dimensions. Our work provides a rigorous foundation for the Lévy flight foraging hypothesis in 3D by establishing the scale-invariant optimality of the Cauchy walk. Furthermore, our results reveal dimensionality-driven shape vulnerabilities and offer testable predictions for biological and engineered systems.

Authors: Mohsen Ghaffari, Christoph Grunau

This paper presents massively parallel computation (MPC) algorithms in the strongly sublinear memory regime (aka, scalable MPC) for orienting and coloring graphs as a function of its subgraph density. Our algorithms run in $poly(\log\log n)$ rounds and compute an orientation of the edges with maximum outdegree $O(α\log\log n)$ as well as a coloring of the vertices with $O(α\log\log n)$ colors. Here, $α$ denotes the density of the densest subgraph. Our algorithm's round complexity is notable because it breaks the $\tildeΘ(\sqrt{\log n})$ barrier, which applied to the previously best known density-dependent orientation algorithm [Ghaffari, Lattanzi, and Mitrovic ICML'19] and is common to many other scalable MPC algorithms.

Authors: Chirag Kaudan, Amir Nayyeri

We consider the following graph reconstruction problem: given an unweighted connected graph $G = (V,E)$ with visible vertex set $V$ and an oracle which takes two vertices $u,v \in V$ and returns the shortest path distance between $u$ and $v$, how many queries are needed to reconstruct $E$? Specifically, we consider bounded degree $Δ$ and bounded treelength $\mathrm{tl}$ connected graphs and show that reconstruction can be done in $O_{Δ,\mathrm{tl}}(n \log n)$ queries with a deterministic algorithm. This result improves over the best known algorithm (deterministic or randomized) for this graph class by a $\log n$ factor and matches the known lower bound for the class of graphs with bounded chordality, which is a subclass of bounded treelength graphs.

Authors: Christian Coester

The list update problem is one of the oldest and simplest problems in online algorithms: A set of items must be maintained in a list while requests to these items arrive over time. Whenever an item is requested, the algorithm pays a cost equal to the position of the item in the list. In the i.i.d. model, where requests are drawn independently from a fixed distribution, the static ordering by decreasing access probabilities $p_1\ge p_2\ge \dots \ge p_n$ achieves the minimal expected access cost OPT$=\sum_{i=1}^n ip_i$. However, $p$ is typically unknown, and approximating it by tracking access frequencies creates undesirable overheads. We prove that the Transposition rule (swap the requested item with its predecessor) has expected access cost at most OPT$+1$ in its stationary distribution. This confirms a 50-year-old conjecture by Rivest up to an unavoidable additive constant. More abstractly, it yields a purely memoryless procedure to approximately sort probabilities via sampling. Our proof is based on a decomposition of excess cost, and its technical core is a "sign-eliminating" combinatorial injection to witness nonnegativity of a constrained multivariate polynomial.

Fully funded PhD position at the Department of Information Technology, Uppsala University on the topic of scalable quantum program verification. The project is at the intersection of formal verification, programming languages and quantum computing and aims to develop mathematically grounded methods for reasoning about hybrid quantum-classical programs.

Website: https://uu.varbi.com/en/what:job/jobID:907722/
Email: ramanathan.s.thinniyam@it.uu.se

By shacharlovett

Authors: MIT Hardness Group, Josh Brunner, Erik D. Demaine, Della Hendrickson, Jeffery Li

We analyze the computational complexity of Tetris clearing (determining whether the player can clear an initial board using a given sequence of pieces) and survival (determining whether the player can avoid losing before placing all the given pieces in an initial board) when restricted to a single polyomino piece type. We prove, for any tetromino piece type $P$ except for O, the NP-hardness of Tetris clearing and survival under the standard Super Rotation System (SRS), even when the input sequence consists of only a specified number of $P$ pieces. These surprising results disprove a 23-year-old conjecture on the computational complexity of Tetris with only I pieces (although our result is only for a specific rotation system). As a corollary, we prove the NP-hardness of Tetris clearing when the sequence of pieces has to be able to be generated from a $7k$-bag randomizer for any positive integer $k\geq 1$. On the positive side, we give polynomial-time algorithms for Tetris clearing and survival when the input sequence consists of only dominoes, assuming a particular rotation model, solving a version of a 9-year-old open problem. Along the way, we give polynomial-time algorithms for Tetris clearing and survival with $1\times k$ pieces (for any fixed $k$), provided the top $k-1$ rows are initially empty, showing that our I NP-hardness result needs to have filled cells in the top three rows.

Authors: Dominik Hangleiter

Quantum computational advantage was claimed for the first time in 2019 and several experiments since then have reinforced the claim. And yet, there is no consensus whether or not quantum advantage has actually been achieved. In this article, I address this question and argue that, in fact, it has. I also outline next steps for theory and experiments in quantum advantage.

Authors: Mingji Xia

Fixing an arbitrary set $\mathcal{F}$ of complex-valued functions over Boolean variables yields a counting problem $\#\mathcal{F}$. Taking only functions from $\mathcal{F}$ to form a tensor network as the problem's input, the counting problem $\#\mathcal{F}$ asks for the value of the tensor network. These dichotomy or quasi-dichotomy theorems form a partial order according to the inclusion relations of the problem subclasses they characterize. As the number of known dichotomy theorems increases, the number of maximal elements in this partially ordered set first grows, and then shrinks when a new dichotomy theorem unifies several previous maximal ones; currently, there are about five or six. More can be artificially defined. However, it might be the timing to directly study the maximum element in the total partial order, namely, the entire class. This paper proposes such a framework, which observes that for the unresolved $\#\mathcal{F}$ problems, the binary functions must be a finite group, formed by 2-by-2 matrices over complex numbers. The framework, divides all unsolved problems according to the group categories, into 9 cases. This paper: introduces this grand framework; discusses the simplification of matrix forms brought by transposition closure property of the group; discusses the barrier reached by the great realnumrizing method, when a quaternion subgroup is involved; advances the order-1 cyclic group case to a position based on a dichotomy theorem conjecture; and resolves the higher-order cyclic group case.

Authors: Kirill Krinkin

The observation that optimum circuit size changes by at most $O(n)$ under a one-point truth table perturbation is implicit in prior work on the Minimum Circuit Size Problem. This note states the bound explicitly for arbitrary fixed finite complete bases with unit-cost gates, extends it to general Hamming distance via a telescoping argument, and verifies it exhaustively at $n = 4$ in the AIG basis using SAT-derived exact circuit sizes for 220 of 222 NPN equivalence classes. Among 987 mutation edges, the maximum observed difference is $4 = n$, confirming the bound is tight at $n = 4$ for AIG.

Authors: Andreas Grigorjew, Michael Lampis

Quantified Boolean Formula (QBF) is a notoriously hard generalization of \textsc{SAT}, especially from the point of view of parameterized complexity, where the problem remains intractable for most standard parameters. A recent work by Eriksson et al.~[IJCAI 24] addressed this by considering the case where the propositional part of the formula is in CNF and we parameterize by the number $k$ of existentially quantified variables. One of their main results was that this natural (but so far overlooked) parameter does lead to fixed-parameter tractability, if we also bound the maximum arity $d$ of the clauses of the given CNF. Unfortunately, their algorithm has a \emph{double-exponential} dependence on $k$ ($2^{2^k}$), even when $d$ is an absolute constant. Since the work of Eriksson et al.\ only complemented this with a SETH-based lower bound implying that a $2^{O(k)}$ dependence is impossible, this left a large gap as an open question. Our main result in this paper is to close this gap by showing that the double-exponential dependence is optimal, assuming the ETH: even for CNFs of arity $4$, QBF with $k$ existential variables cannot be solved in time $2^{2^{o(k)}}|φ|^{O(1)}$. Complementing this, we also consider the further restricted case of QBF with only two quantifier blocks ($\forall\exists$-QBF). We show that in this case the situation improves dramatically: for each $d\ge 3$ we show an algorithm with running time $k^{O_d(k ^{d-1})}|φ|^{O(1)}$ and a lower bound under the ETH showing our algorithm is almost optimal.

Authors: Sándor Kisfaludi-Bak, Saeed Odak, Satyam Singh, Geert van Wordragen

We give an approximation scheme for the TSP in $d$-dimensional hyperbolic space that has optimal dependence on $\varepsilon$ under Gap-ETH. For any fixed dimension $d\geq 2$ and for any $\varepsilon>0$ our randomized algorithm gives a $(1+\varepsilon)$-approximation in time $2^{O(1/\varepsilon^{d-1})}n^{1+o(1)}$. We also provide an algorithm for the hyperbolic Steiner tree problem with the same running time. Our algorithm is an Arora-style dynamic program based on a randomly shifted hierarchical decomposition. However, we introduce a new hierarchical decomposition called the hybrid hyperbolic quadtree to achieve the desired large-scale structure, which deviates significantly from the recently proposed hyperbolic quadtree of Kisfaludi-Bak and Van Wordragen (JoCG'25). Moreover, we have a new non-uniform portal placement, and our structure theorem employs a new weighted crossing analysis. We believe that these techniques could form the basis for further developments in geometric optimization in curved spaces.

Authors: Joseph O'Rourke

It remains unknown if every prismatoid has a nonoverlapping edge-unfolding, a special case of the long-unsolved "Dürer's problem." Recently nested prismatoids have been settled [Rad24] by mixing (in some sense) the two natural unfoldings, petal-unfolding and band-unfolding. Band-unfolding fails due to a specific counterexample [O'R13b]. The main contribution of this paper is a characterization when a band-unfolding of a nested prismatoid does in fact result in a nonoverlapping unfolding. In particular, we show that the mentioned counterexample is in a sense the only possible counterexample. Although this result does not expand the class of shapes known to have an edge-unfolding, its proof expands our understanding in several ways, developing tools that may help resolve the non-nested case.

Authors: Stephen Kobourov, William Lenhart, Giuseppe Liotta, Daniel Perz, Pavel Valtr, Johannes Zink

We study the problem of simultaneous geometric embedding of two paths without self-intersections on an integer grid. We show that minimizing the length of the longest edge of such an embedding is NP-hard. We also show that we can minimize in $O(n^{3/2})$ time the perimeter of an integer grid containing such an embedding if one path is $x$-monotone and the other is $y$-monotone.

Authors: Prosenjit Bose, Jean-Lou De Carufel, Darryl Hill, John Stuart

Given a finite set $P\subset\mathbb{R}^2$, the directed Theta-6 graph, denoted $\vecΘ_6(P)$, is a well-studied geometric graph due to its close relationship with the Delaunay triangulation. The $\vecΘ_6(P)$-graph is defined as follows: the plane around each point $u\in P$ is partitioned into $6$ equiangular cones with apex $u$, and in each cone, $u$ is joined to the point whose projection on the bisector of the cone is closest. Equivalently, the $\vecΘ_6(P)$-graph contains an edge from $u$ to $v$ exactly when the interior of $\nabla_u^v$ is disjoint from $P$, where $\nabla_u^v$ is the unique equilateral triangle containing $u$ on a corner, $v$ on the opposite side, and whose sides are parallel to the cone boundaries. It was previously shown that the spanning ratio of the $\vecΘ_6(P)$-graph is between $4$ and $7$ in the worst case (Akitaya, Biniaz, and Bose \emph{Comput. Geom.}, 105-106:101881, 2022). We close this gap by showing a tight spanning ratio of 5. This is the first tight bound proven for the spanning ratio of any $\vecΘ_k(P)$-graph. Our lower bound models a long path by mapping it to a converging series. Our upper bound proof uses techniques novel to the area of spanners. We use linear programming to prove that among several candidate paths, there exists a path satisfying our bound.

Authors: Sebastian Angrick, Kevin Buchin, Geri Gokaj, Marvin Künnemann

To measure the shape similarity of point sets, various notions of the Hausdorff distance under translation are widely studied. In this context, for an $n$-point set $P$ and $m$-point set $Q$ in $\mathbb{R}^d$, we consider the task of computing the minimum $d(P,Q+τ)$ over translations $τ\in T$, where $d(\cdot, \cdot)$ denotes the Hausdorff distance under the $L_\infty$-norm. We analyze continuous ($T=\mathbb{R}^d$) vs. discrete ($T$ is finite) and directed vs. undirected variants. Applying fine-grained complexity, we analyze running time dependencies on dimension $d$, the $n$ vs. $m$ relationship, and the chosen variant. Our main results are: (1) The continuous directed Hausdorff distance has asymmetric time complexity. While (Chan, SoCG'23) gave a symmetric $\tilde{O}((nm)^{d/2})$ upper bound for $d\ge 3$, which is conditionally optimal for combinatorial algorithms when $m \le n$, we show this fails for $n \ll m$ with a combinatorial, almost-linear time algorithm for $d=3$ and $n=m^{o(1)}$. We also prove general conditional lower bounds for $d\ge 3$: $m^{\lfloor d/2 \rfloor -o(1)}$ for small $n$, and $n^{d/2 -o(1)}$ for $d=3$ and small $m$. (2) While lower bounds for $d \ge 3$ hold for directed and undirected variants, $d=1$ yields a conditional separation. Unlike undirected variants solvable in near-linear time (Rote, IPL'91), we prove directed variants are at least as hard as the additive MaxConv LowerBound (Cygan et al., TALG'19). (3) The discrete variant reduces to a 3SUM variant for $d\le 3$. This creates a barrier to proving tight lower bounds under the Orthogonal Vectors Hypothesis (OVH), contrasting with continuous variants that admit tight OVH-based lower bounds in $d=2$ (Bringmann, Nusser, JoCG'21). These results reveal an intricate interplay of dimensionality, symmetry, and discreteness in computing translational Hausdorff distances.

Authors: Vincent Cohen-Addad, Karthik C. S., David Saulpic, Chris Schwiegelshohn

The $k$-median and $k$-means clustering objectives are classic objectives for modeling clustering in a metric space. Given a set of points in a metric space, the goal of the $k$-median (resp. $k$-means) problem is to find $k$ representative points so as to minimize the sum of the distances (resp. sum of squared distances) from each point to its closest representative. Cohen-Addad, Feldmann, and Saulpic [JACM'21] showed how to obtain a $(1+\varepsilon)$-factor approximation in low-dimensional Euclidean metric for both the $k$-median and $k$-means problems in near-linear time $2^{(1/\varepsilon)^{O(d^2)}} n \cdot \text{polylog}(n)$ (where $d$ is the dimension and $n$ is the number of input points). We improve this running time to $2^{\tilde{O}(1/\varepsilon)^{d-1}} \cdot n \cdot \text{polylog}(n)$, and show an almost matching lower bound: under the Gap Exponential Time Hypothesis for 3-SAT, there is no $2^{{o}(1/\varepsilon^{d-1})} n^{O(1)}$ algorithm achieving a $(1+\varepsilon)$-approximation for $k$-means.

Authors: Anna Matsui, Innocent Obi, Guillaume Sabbagh, Leo Torres, Diana Kessler, Juan F. Meleiro, Koko Muroya

Critical pair analysis provides a convenient and computable criterion of confluence, which is a fundamental property in rewriting theory, for a wide variety of rewriting systems. Bonchi et al. showed validity of critical pair analysis for rewriting on string diagrams in symmetric monoidal categories. This work aims at automation of critical pair analysis for string diagram rewriting, and develops an algorithm that implements the core part of critical pair analysis. The algorithm enumerates all critical pairs of a given left-connected string diagram rewriting system, and it can be realised by concrete manipulation of hypergraphs. We prove correctness and exhaustiveness of the algorithm, for string diagrams in symmetric monoidal categories without a Frobenius structure.

Authors: Joan Boyar, Shahin Kamali, Kim S. Larsen, Ali Fata Lavasani, Yaqiao Li, Denis Pankratov

We introduce and study the weighted version of an online matching problem in the Euclidean plane with non-crossing constraints: points with non-negative weights arrive online, and an algorithm can match an arriving point to one of the unmatched previously arrived points. In the classic model, the decision on how to match (if at all) a newly arriving point is irrevocable. The goal is to maximize the total weight of matched points under the constraint that straight-line segments corresponding to the edges of the matching do not intersect. The unweighted version of the problem was introduced in the offline setting by Atallah in 1985, and this problem became a subject of study in the online setting with and without advice in several recent papers. We observe that deterministic online algorithms cannot guarantee a non-trivial competitive ratio for the weighted problem, but we give upper and lower bounds on the problem with bounded weights. In contrast to the deterministic case, we show that using randomization, a constant competitive ratio is possible for arbitrary weights. We also study other variants of the problem, including revocability and collinear points, both of which permit non-trivial online algorithms, and we give upper and lower bounds for the attainable competitive ratios. Finally, we prove an advice complexity bound for obtaining optimality, improving the best known bound.

Authors: David P. Woodruff, Samson Zhou

In this paper, we study the distributed experts problem, where $n$ experts are distributed across $s$ servers for $T$ timesteps. The loss of each expert at each time $t$ is the $\ell_p$ norm of the vector that consists of the losses of the expert at each of the $s$ servers at time $t$. The goal is to minimize the regret $R$, i.e., the loss of the distributed protocol compared to the loss of the best expert, amortized over the all $T$ times, while using the minimum amount of communication. We give a protocol that achieves regret roughly $R\gtrsim\frac{1}{\sqrt{T}\cdot\text{poly}\log(nsT)}$, using $\mathcal{O}\left(\frac{n}{R^2}+\frac{s}{R^2}\right)\cdot\max(s^{1-2/p},1)\cdot\text{poly}\log(nsT)$ bits of communication, which improves on previous work.

Authors: Peaker Guo, Rayne Holland, Hao Wu

Given a dataset of $n$ user-contributed strings, each of length at most $\ell$, a key problem is how to identify all frequent substrings while preserving each user's privacy. Recent work by Bernardini et al. (PODS'25) introduced a $\varepsilon$-differentially private algorithm achieving near-optimal error, but at the prohibitive cost of $O(n^2\ell^4)$ space and processing time. In this work, we present a new $\varepsilon$-differentially private algorithm that retains the same near-optimal error guarantees while reducing space complexity to $O(n \ell+ |Σ| )$ and time complexity to $O(n \ell\log |Σ| + |Σ| )$, for input alphabet $Σ$. Our approach builds on a top-down exploration of candidate substrings but introduces two new innovations: (i) a refined candidate-generation strategy that leverages the structural properties of frequent prefixes and suffixes, and (ii) pruning of the search space guided by frequency relations. These techniques eliminate the quadratic blow-ups inherent in prior work, enabling scalable frequent substring mining under differential privacy.

Authors: Miguel Bosch-Calvo, Fabrizio Grandoni, Yusuke Kobayashi, Takashi Noguchi

In the Weighted Triangle-Free 2-Matching problem (WTF2M), we are given an undirected edge-weighted graph. Our goal is to compute a maximum-weight subgraph that is a 2-matching (i.e., no node has degree more than $2$) and triangle-free (i.e., it does not contain any cycle with $3$ edges). One of the main motivations for this and related problems is their practical and theoretical connection with the Traveling Salesperson Problem and with some $2$-connectivity network design problems. WTF2M is not known to be NP-hard and at the same time no polynomial-time algorithm to solve it is known in the general case (polynomial-time algorithms are known only for some special cases). The best-known (folklore) approximation algorithm for this problem simply computes a maximum-weight 2-matching, and then drops the cheapest edge of each triangle: this gives a $2/3$ approximation. In this paper we present a PTAS for WTF2M, i.e., a polynomial-time $(1-\varepsilon)$-approximation algorithm for any given constant $\varepsilon>0$. Our result is based on a simple local-search algorithm and a non-trivial analysis.

Authors: Cezar-Mihail Alexandru, Adithya Diddapur, Magnús M. Halldórsson, Christian Konrad, Kheeran K. Naidu

We consider the \textsf{Unit Interval Selection} problem in the one-pass random order streaming model. Here, an algorithm is presented a sequence of $n$ unit-length intervals on the line that arrive in uniform random order, and the objective is to output a largest set of disjoint intervals using space linear in the size of an optimal solution. Previous work only considered adversarially ordered streams and established that, in this space constraint, a $(2/3)$-approximation can be achieved, and this is also best possible, i.e. any improvement requires space $Ω(n)$ [Emek et al., TALG'16]. In this work, we show that an improved expected approximation factor can be achieved if the input stream is in uniform random order, with the expectation taken over the stream order. Specifically, we give a one-pass streaming algorithm with expected approximation factor $0.7401$ using space $O(|OPT|)$, where $OPT$ denotes an optimal solution. We also show that algorithms with expected approximation factor above $8/9$ require space $Ω(n)$, and algorithms that compute a better than $2/3$-approximation with probability above $2/3$ also require $Ω(n)$ space. On a technical note, we design an algorithm for the restricted domain $[0,Δ)$, for some constant $Δ$, and use standard techniques to obtain an algorithm for unrestricted domains. For the restricted domain $[0,Δ)$, we run $O(Δ)$ recursive instances of our algorithm, with each instance targeting the situation where a specific interval from $OPT$ arrives first. We establish the interesting property that our algorithm performs worst when the input stream is precisely a set of independent intervals. We then analyse the algorithm on these instances. Our lower bound is proved via communication complexity arguments, similar in spirit to the robust communication lower bounds by [Chakrabarti et al., Theory Comput. 2016].

Authors: Benjamín Guzmán

This paper presents bsort, a non-comparison-based sorting algorithm for signed and unsigned integers, and floating-point values. The algorithm unifies these cases through an approach derived from binary quicksort, achieving $O(wn)$ runtime asymptotic behavior and $O(w)$ auxiliary space, where $w$ is the element word size. This algorithm is highly efficient for data types with small word sizes, where empirical analysis exhibits performance competitive with highly optimized hybrid algorithms from popular libraries.

Authors: Yuly Billig

We consider a matching problem for time series with values in an arbitrary metric space, with the stretching penalty given by the Hellinger kernel. To optimize this matching, we introduce the Elastic Time Warping algorithm with a cubic computational complexity.

Last Thursday, my friend and colleague Sam Baker, in UT Austin’s English department, convened an “emergency panel” here about the developing Pentagon/Anthropic situation, and asked me to speak at it. Even though the situation has continued to develop since then, I thought my prepared remarks for the panel might be of interest. At the bottom, I include a few additional thoughts.

---

Hi! I’m Scott Aaronson! I teach CS here at UT. While my background is in quantum computing, I’ve spent the past four years dabbling in AI alignment. I did a two-year leave at OpenAI, in their now-defunct Superalignment team. I joined back when OpenAI’s line was “we’re a little nonprofit, doing all this in the greater interest of humanity, and we’d dissolve ourselves before we raced to build an AI that we thought would be dangerous.” I know Sam Altman, and many other current and former OpenAI people. I also know Dario Amodei—in fact, I knew Dario well before Anthropic existed. Despite that, I don’t actually feel like I have deep insight into the current situation with Anthropic and the Pentagon that you wouldn’t get by reading the news, or (especially) reading commentators like Zvi Mowshowitz, Kelsey Piper, Scott Alexander, and Dean Ball. But since I was asked to comment, I’ll try.

The first point I’ll make: the administration’s line, to the extent they’ve had a consistent line, is basically that they needed to cut off Anthropic because Anthropic is a bunch of woke, America-hating, leftist radicals. I think that, if you actually know the Anthropic people, that characterization is pretty laughable. Unless by “woke,” what the administration meant was “having any principles at all, beyond blind deference to authority, and sticking to them.”

I mean, Anthropic only got into this situation in the first place because it was more eager than the other AI companies to support US national security, by providing a version of Claude that could be used on classified networks. So they signed a contract with the Pentagon, and that contract had certain restrictions in it, which the Pentagon read and agreed to … until they decided that they no longer agreed.

That brings me to my second point. The Pentagon regularly signs contracts with private firms that limit what the Pentagon can do in various ways. That’s why they’re called military contract-ors. So anyone who claims it’s totally unprecedented for Anthropic to try to restrict what the government can do with Anthropic’s private property—I think that person is either misinformed or else trying to misinform.

The third point. If the Pentagon felt that it couldn’t abide a private company telling it what is or isn’t an appropriate military use of current AI, then the Pentagon was totally within its rights to cancel its contract with Anthropic, and find a different contractor (like OpenAI…) that would play ball. So it’s crucial for everyone here to understand that that’s not all that the Pentagon did. Instead they said: because Anthropic dared to stand up to us, we’re going to designate them a Supply Chain Risk—a designation that was previously reserved for foreign nation-state adversaries, and that, incredibly, hasn’t been applied to DeepSeek or other Chinese AI companies that arguably do present such risks. So basically, they threatened to destroy Anthropic, by making it horrendously complicated for any companies that do business with the government—i.e., just about all companies—also to do business with Anthropic.

Either that, the Pentagon threatened, or we’ll invoke the Defense Production Act to effectively nationalize Anthropic—i.e., we’ll just commandeer their intellectual property, use it for whatever we want despite Anthropic’s refusal. You get that? Claude is both a supply chain risk that’s too dangerous for the military to use, and somehow also so crucial to the supply chain that we, the military, need to commandeer it.

To me, this is the authoritarian part of what the Pentagon is doing (with the inconsistency being part of the authoritarianism; who but a dictator gets to impose his will on two directly contradictory grounds?). It’s the part that goes against the free-market principles that our whole economy is built on, and the freedom of speech and conscience that our whole civilization is built on. And I think this will ultimately damage US national security, by preventing other American AI companies from wanting to work on defense going forward.

That brings me to the fourth point, about OpenAI. While this was going down, Sam Altman posted online that he agreed with Anthropic’s red lines: LLMs should not be used for killing people with no human in the kill chain, and they also shouldn’t be used for mass surveillance of US citizens. I thought, that’s great! The frontier AI labs are sticking together when the chips are down, rather than infighting.

But then, just a few hours after the Pentagon designated Anthropic a supply chain risk, OpenAI announced that it had reached a deal with the Pentagon. Huh?!? If they have the same red lines, then why can one of them reach a deal while the other can’t?

The experts’ best guess seems to be this: Anthropic said, yes, using AI to kill people autonomously or to surveil US citizens should already be illegal, but we insist on putting those things in the contract to be extra-double-sure. Whereas OpenAI said, the Pentagon can use our models for “all lawful purposes”—this was the language that the Pentagon had insisted on. And, continued OpenAI, we interpret “all lawful purposes” to mean that they can’t cross these red lines. But if it turns out we’re wrong about that … well, that’s not our problem! That’s between the Pentagon and the courts, or whatever.

Again, we don’t fully know, because most of the relevant contracts haven’t been made public, but that’s an inference from reading between the lines of what has been made public.

Back in 2023-2024, when there was the Battle of the Board, then the battle over changing OpenAI’s governance structure, etc., some people formed a certain view of Sam, that he would say all the good and prosocial and responsible things even while he did whichever thing maximized revenue. I’ll leave it to you whether last week’s events are consistent with that view.

OK, fifth and final point. I remember 15-20 years ago, talking to Eliezer Yudkowsky and others terrified about AI. They said, this is the biggest issue facing the world. It’s not safe for anyone to build because it could turn against us, or even before that, the military could commandeer it or whatever. And I and others were like, dude, you guys obviously read too much science fiction!

And now here we are. Not only are we living in a science-fiction story, I’d say we’re living in a particularly hackneyed one. I mean, the military brass marching into a top AI lab and telling the nerds, “tough luck, we own your AI now”? Couldn’t reality have been a little more creative than that?

The point is, given the developments of the past couple weeks, I think we now need to retire forever the argument against future AI scenarios that goes, “sorry, that sounds too much like a science-fiction plot.” As has been said, you’d best get used to science fiction because you’re living in one!

---

Updates and Further Thoughts: Of course I’ve seen that Anthropic has now filed a lawsuit to block the Pentagon from designating it a supply chain risk, arguing that both its free speech and due process rights were violated. I hope their lawsuit succeeds; it’s hard for me to imagine how it wouldn’t.

The fact that I’m, obviously, on Anthropic’s side of this particular dispute doesn’t mean that I’ll always be on Anthropic’s side. Here as elsewhere, it’s crucial not to outsource your conscience to anyone.

Zvi makes an extremely pertinent comparison:

[In shutting down Starlink over Ukraine,] Elon Musk actively did the exact thing [the Pentagon is] accusing Anthropic of maybe doing. He made a strategic decision of national security at the highest level as a private citizen, in the middle of an active military operation in an existential defensive shooting war, based on his own read of the situation. Like, seriously, what the actual fuck.

Eventually we bought those services in a contract. We didn’t seize them. We didn’t arrest Musk. Because a contract is a contract is a contract, and your private property is your private property, until Musk decides yours don’t count.

Another key quote in Zvi’s piece, from Gregory Allen:

And here’s the thing. I spent so much of my life in the Department of Defense trying to convince Silicon Valley companies, “Hey, come on in, the water is fine, the defense contracting market, you know, you can have a good life here, just dip your toe in the water”.

And what the Department of Defense has just said is, “Any company that dips their toe in the water, we reserve the right to grab their ankle, pull them all the way in at any time”. And that is such a disincentive to even getting started in working with the DoD.

Lastly, I’d like to address the most common counterargument against Anthropic’s position—as expressed for example by Noah Smith, or in the comments of my previous post on this. The argument goes roughly like so:

You, nerds, are the ones who’ve been screaming for years about AI being potentially existentially dangerous! So then, did you seriously expect to stay in control of the technology? If it’s really as dangerous and important as you say, then of course the military was going to step in at some point and commandeer your new toy, just like it would if you were building a nuclear weapon.

Two immediate responses:

1. Even in WWII, in one of the most desperate circumstances in human history, the US government didn’t force a single scientist at gunpoint to build nuclear weapons for them. The scientists did so voluntarily, based on their own considered moral judgment at the time (even if some later came to regret their involvement).
2. Even if I considered it “inevitable” that relatively thoughtful and principled people, like Dario Amodei, would lose control over the future to gleeful barbarians like Pete Hegseth, it still wouldn’t mean I couldn’t complain when it happened. This is still a free country, isn’t it?

By Scott

This post presents a very good interview of Scott Aaronson with Yuval Boger of QuEra, in which Scott gives a detailed and thoughtful account of his view of my position. Scott nicely characterizes the position I put forward early on as follows:

“There has to be some principle of correlated noise that comes on top of quantum mechanics and somehow screens off quantum computation”

Indeed, my previous post described, with the benefit of time perspective, conjectures I made about correlated noise twenty years ago. If correct, they would pose major obstacles to quantum computers. The fact that these conjectures remain undecided after twenty years may give us some indication of the time scale required both for progress in building quantum computers and for understanding whether quantum computation is possible at all.

Today, in the first part of the post I quote Scott’s view of my position, and in the second part I offer my responses. 

Let me mention two points I made that are relevant in broader scientific contexts. 

• In my view, carefully checking experimental claims—especially major ones—is an important part of scientific work. 
• As a general rule, raw data for such experiments should be publicly available.

While I do not always agree with Scott on the technical level, I find Scott’s answer perfectly reasonable. Over the decades—and especially in the past seven years—some of Scott’s references to my position were hostile, mocking or offensive, so I am glad that he chose a different path in this interview.

A fictitious scene generated by AI of Yuval, Scott, and me having a friendly discussion about quantum computing. In reality, I have not yet met Yuval, and I have not met Scott for many years. (Scott and Yuval approved the use of the picture.)

Scott Aaronson’s View of my View

Yuval: I’ve heard you refer many times in your talks to an argument with Gil Kalai about whether large-scale quantum computing is even possible. Do you think he still has a path to being vindicated, or is it over?

Scott: I feel like his path has been getting narrower and narrower. Gil Kalai is a brilliant mathematician and one of the leading skeptics of quantum computing. What he was postulating was that he believes quantum mechanics—quantum mechanics is fine—but there has to be some principle of correlated noise that comes on top of quantum mechanics and somehow screens off quantum computation.

I’ve never entirely understood why he’s so certain of that. Maybe it’s more accurate to say he starts with quantum computation being impossible as his axiom, then works backwards to find what kinds of correlated noise would kill the schemes for quantum error correction and therefore vindicate his axiom.

He’s come up with various models. I never found them physically plausible, but at least he was sticking his neck out, which is more than a lot of quantum computing skeptics were doing. He was proposing models and making predictions. His prediction was that at the scale of 50 to 100 qubits and hundreds or thousands of gates, you’d see correlations in the errors. If you apply a thousand gates, each 99.9% accurate, the total accuracy wouldn’t just be 0.999 to the thousandth power—it would be much worse because all the different errors would interact with each other.

Now those experiments have been done—famously by Google, Quantinuum, USTC, and I believe QuEra has done relevant demos too. And again and again, this is not what we’ve seen. The total accuracy does go down exponentially with the number of gates, but it merely goes down exponentially—exactly the way the theory of quantum fault tolerance presupposed 30 years ago. If this is all that’s going on—simple uncorrelated noise—then quantum error correction is going to work. It’s merely a staggeringly hard engineering problem to build this at the scale where it works.

Over the last five years, Gil Kalai has been driven in a really weird direction where he’s basically saying these experiments have to be wrong. He keeps writing to the Google people requesting more of their raw data—he CCs me on the emails—then does his own analyses, posts about it on the archive. He keeps saying their 2019 experiment must have been fallacious. But in the meantime, there’s been a dozen other experiments by other companies all getting the same conclusion. He’s fighting a losing battle at this point.

The fact that someone of his capability tried so hard to prove quantum computing impossible and failed makes me more confident. If there is a fundamental roadblock, it has to be something totally new and shocking, something we haven’t foreseen and Gil hasn’t foreseen either—some change to the laws of physics that somehow wouldn’t have reared its head with thousands of gates but will do so at millions of gates.

The scientist in me hopes we’ll make that discovery. I hope quantum computing will be impossible for some reason that revolutionizes physics—how exciting would that be? But that’s not my prediction. My prediction is that the more boring, conservative thing will happen: quantum computing will merely be possible, just like the theory said.

Some responses

Motivation

Maybe it’s more accurate to say he starts with quantum computation being impossible as his axiom, then works backwards to find what kinds of correlated noise would kill the schemes for quantum error correction and therefore vindicate his axiom.

Yes, this characterization of my work on correlated errors is essentially accurate, and it is often how I describe it myself. (See section “Motivation” of my previous post.)

My later works on quantum supremacy for NISQ computers analyzed the computational complexity and noise sensitivity of NISQ devices based on standard noise models.  Both directions lead to predictions at the scale of hundreds or thousands of gates.

Correlated errors

His prediction was that at the scale of 50 to 100 qubits and hundreds or thousands of gates, you’d see correlations in the errors.

Yes. For the precise predictions look at the previous post.

 If you apply a thousand gates, each 99.9% accurate, the total accuracy wouldn’t just be 0.999 to the thousandth power—it would be much worse because all the different errors would interact with each other.

No, this was not part of my predictions.

And again and again, this is not what we’ve seen. The total accuracy does go down exponentially with the number of gates, but it merely goes down exponentially—exactly the way the theory of quantum fault tolerance presupposed 30 years ago.

As I explained in item 8 of my previous post, this behavior does not contradict my conjectures regarding correlated errors. (I agree that such a behavior, if confirmed, is overall encouraging.)

Scrutinizing the Google 2019 experiment and other experiments

Over the last five years, Gil Kalai has been driven in a really weird direction where he’s basically saying these experiments have to be wrong. He keeps writing to the Google people requesting more of their raw data—he CCs me on the emails—then does his own analyses, posts about it on the archive.

Since I regard this issue as important in broader scientific contexts let me highlight my response.

In my view, carefully checking experimental claims—especially major ones—is an important part of scientific work. 

I also think that, as a general rule, raw data for such experiments should be publicly available.

(Scott was CC-ed to the correspondence because Scott initiated it; we would love to have a similar discussion with the relevant Google team about the 2024 distance-3,-5,-7 surface code paper and if Scott can make the connection this would be helpful.)

He keeps saying their 2019 experiment must have been fallacious.

Our findings indicate that the experiment may indeed have been flawed.

As I wrote elsewhere “I believe more can be done to clarify and explain the findings of our papers.” So far, the concerns raised in our papers were directed mainly to the Google team itself (and to interested specialists), and non-specialists may have found them difficult to follow. My 2024 post provides a short introduction of our work. 

But in the meantime, there’s been a dozen other experiments by other companies all getting the same conclusion. He’s fighting a losing battle at this point.

We examined the Google 2019 experiment carefully and looked less carefully at several other experiments. (I would personally be interested to extend our statistical study to the Google 2024 surface code paper.) If people find our efforts valuable, they may go on to scrutinize additional experiments. We would be happy to share our experience and computer programs.

For comparison, there have also been many experiments claiming the observation of Majorana zero modes (MZM), yet it remains an open question whether they have actually been demonstrated. (There are reasons to think that MZM were not conclusively demonstrated and to doubt the methodology of some of the experimental efforts. ) 

Conclusion

The fact that someone of his capability tried so hard to prove quantum computing impossible and failed makes me more confident.

This is perfectly OK! My goal is to advance understanding—even if the conclusions eventually go against my own views. 

If there is a fundamental roadblock, it has to be something totally new and shocking, something we haven’t foreseen and Gil hasn’t foreseen either—some change to the laws of physics that somehow wouldn’t have reared its head with thousands of gates but will do so at millions of gates.

Contrary to what Scott says, my conjectures and explicit predictions would already manifest themselves at the scales of hundreds of gates and of thousands of gates (perhaps even tens of gates), rather than only at the scale of millions.

__________

So what’s wrong with a little bit of hype?

There are various other interesting issues raised in Scott’s answer about my argument and in the entire interview. An interesting question raised by Yuval Boger in the interview was about hype in commercialization:

Yuval: It takes a lot of money to build a quantum computer and even more to develop one. This money comes from investors, and investors need to believe in a vision and a future. So what’s wrong with a little bit of hype to get the money you need to execute on the plan?

Yuval Boger graduated from the Hebrew University of Jerusalem. He is now the chief commercial officer for QuEra Computing.

By Gil Kalai

We have an open position for a doctoral candidate in the field of algorithmic operations research. The position is funded for 3 years by the NSF.

Requisite qualifications: Familiarity with algorithmic design, computational complexity, linear programming and game theory.

Website: https://directory.statler.wvu.edu/faculty-staff-directory/piotr-wojciechowski
Email: pwojciec@mail.wvu.edu

By shacharlovett

What’s been clear so far about this conference on Cultural AI is the organizers were interested in a broadly construed definition of AI and Culture. That works for me, as my talk ended up being about two ways of construing the culture of benchmarking. Here’s a summarized version of what I said.

I’ve been a machine learning researcher for nearly 25 years now (yikes), and I opened with a slide describing machine learning that I originally made in 2003.

It still works. Machine learning is prediction from examples, and that’s it. You have some blob of stuff that you call X’s. You have some blob of stuff you call Y’s, and you build computer programs to predict the Y’s from the X’s. The key thing that makes machine learning algorithms different than other kinds of predictions is that you deliberately try to bake in as few assumptions as possible, other than the fact that you have examples.

I find the online discourse castigating those who say “LLMs are just next token predictors” beyond annoying. They are just next token predictors. And that’s fascinating.1

The fascinating part comes in convincing yourself that your function works on new examples. How do you do that? Anybody who has read David Hume knows you can’t do it with formal proof. We convince ourselves through a particular system of evaluation. And then we built an entire engineering discipline on top of this.

Now, what is evaluation? In our 2025 course, Deb Raji and I adapted Peter Rossi’s definition, which he developed for social scientific program evaluation.

This definition seems reasonable enough, but in a world obsessed with quantification, this sets into motion an inevitable bureaucratic collapse. If you want to make your evaluation legible and fair to all stakeholders, you must make it quantitative. If you want to handle a diversity of contexts, you must evaluate on multiple instantiations and report the average behavior. Quantification has to become statistical. And once you declare your expectations and metrics, everything becomes optimization. Evaluation inevitably becomes statistical prediction.

This bureaucratic loop swallows up not just social scientific program evaluation but engineering evaluation more broadly. If you are calculating mean-square errors, you’re shoehorning your evaluation into statistical prediction. Everyone loves to lean on the artifice of clean statistical facts. Once you have set this stage, machine learning is practically optimal by definition.

Machine learning as a discipline has no foundation beyond evaluation. This is a descriptive, not normative statement. The most successful machine learning papers work like this: I say that Y is predictable from X by Method M, and you should be impressed. I then make billions of dollars in a startup. Maybe I have to tell a story about how Method M relates to the brain or mean-field approximations in statistical physics. Fantastic stories don’t seem to hurt.

Now, here’s an invalid AI paper, which a lot of critics like to write: “Y is not predictable from X.” It is impossible to refute this claim. You can’t even refute it for simple methods, because what’s gonna happen is some high school kid is gonna go and change the rules slightly and prove you wrong. Then he will dunk on you on Twitter, gleefully writing “skill issue.”

The logical reconstruction makes the logical positivists roll over in their graves. The field is fueled by pure induction. We progress research programs by demonstration alone. And the way we convince others that our demos are cool is by sharing data and code.

Core to machine learning is the culture of data sets. I’m not sure if some poor soul is still trying to update this wikipedia page, but the field thrives on shared data with common tasks. The data sets give you an easy path to impress your colleagues. You can argue about the novelty of your method M, which achieves high accuracy on a dataset that others agree is challenging.

People have turned datasets into literal competitions, starting with the Netflix Prize, moving to the ImageNet Large Scale Visual Recognition Challenge (ILSVRC), and ending with a company that hosts hundreds of competitions. Not to get all monocausal on you, but the ImageNet Challenge is why we use neural networks today instead of other methods. More fascinating is that we declared protein folding solved because Alphafold did really well on a machine learning competition. Competitive testing on benchmarks can produce Nobel Prizes.

You might be put off by how everything in machine learning becomes an optimization competition. But let’s applaud machine learning for its brutal, ingenuous honesty about how researchers are driven by ruthless competition. If you want to read more on how this works in practice, read Dave Donoho’s construction of frictionless reproducibility, my concurrence and analysis of the mechanism and costs, the history Moritz Hardt and I lay out in Patterns, Predictions, and Actions, or how it fits into the bigger story of The Irrational Decision.2

Perhaps the weirdest transition of the last decade was a move from dataset evaluation to “generalist” evaluation. Tracking the GPT series of papers is instructive. GPT2 declared language models to be general-purpose predictors, but OpenAI made their case with rather standard evaluations and metrics. GPT3 moved on to harder to pin down evaluations in “natural language inference,” but there were still tables with numbers and scores. With GPT4, we didn’t even get a paper. We got a press release formatted like a paper, which is fascinating in and of itself.3 That press release bragged about the LLM’s answers on standardized tests.

Of course, this got people excited, resulting in breathless press coverage and declarations of the end of education and white-collar work. Hypecycles are part of culture, too. Part of the goal of predicting Y from X is impressing people, and the results were very impressive. Based on the reaction, you can’t say that GPT4 didn’t surpass people’s expectations.

Now, if you live by the evaluation, you die by the evaluation. Notably, Facebook nuked their AI division after flopping on GPT4-style evaluation. Not only did its userbase think the model sucked, but they were caught cheating on their evaluations, too. In a flailing attempt to recover, Facebook went out and spent $14 billion to buy some random AI talent willing to report to King Z, and they’ve thrown orders of magnitude more at their subsequent AI investments. And what did this buy them? Literally Vibes.

We’re in this fascinating world now where research artifacts are consumer products, and the evaluation is necessarily cultural. Nonprofits funded by the same dirty money that funds AI companies might argue that they can measure the power of coding agents with objective statistical evaluations of yore. But agents are evaluated by coders’ experiences and managers’ fever dreams. I wrote this a year ago, and it remains true today: Generative AI lives in the weird liminal space between productivity software and science fiction revolution. The future of generative AI will be evaluated with our wallets. No leaderboard will help us do that.

Subscribe now

By Ben Recht

Turing Award winner and former Oxford professor Tony Hoare passed away last Thursday at the age of 92. Hoare is famous for quicksort, ALGOL, Hoare logic and so much more. Jim Miles gives his personal reflections.

Jill Hoare, Tony Hoare, Jim Miles. Cambridge, 7 September 2021

Last Thursday (5th March 2026), Tony Hoare passed away, at the age of 92. He made many important contributions to Computer Science, which go well beyond just the one for which most Maths/CompSci undergraduates might know his name: the quicksort algorithm. His achievements in the field are covered comprehensively across easy-to-find books and articles, and I am sure will be addressed in detail as obituaries are published over the coming weeks. I was invited in this entry to remember the Tony that I knew, so here I will be writing about his personality from the occasions that I met him.

I visited Tony Hoare several times in the past 5 years, as we both live in Cambridge (UK) and it turned out that my family knew his. As a Mathematics graduate, I was very keen to meet and learn about his life from the great man himself. I was further prompted by a post on this blog which mentioned Tony a few times and summarised a relevant portion of his work. I took a print out of that entry the first time I visited him to help break the ice - it is the green sheet of paper in the picture above.

Tony read the entry and smiled, clearly recalling very well the material of his that it referenced, and then elaborating a bit, explaining how vastly programs had scaled up in a rather short space of time and how they typically require different methods than many of those he had been developing in the early days.

I was aware that Tony had studied Classics and Philosophy at university so I was keen to learn how one thing had led to another in the development of his career. He explained that after completing his degree he had been intensively trained in Russian on the Joint Services School for Linguists programme and was also personally very interested in statistics as well as the emerging and exciting world of computers. This meant that after his National Service (which was essentially the JSSL) he took on a job 'demonstrating' a type of early computer, in particular globally, and especially in the Soviet Union. He described the place of these demonstrations as 'fairs' but I suppose we might now call them 'expos'. In a sense, this seemed like a very modest description of his job, when in fact - reading up on Tony's career - he was also involved in the development of code for these devices, but perhaps that's a historical quirk of the period: being a demonstrator of these machines meant really knowing them inside and out to the point of acting on the dev team (AND, one might deduce, being fluent in Russian!).

Tony would tell these stories with a clarity and warmth that made it clear that certainly he was still entirely 'all there' mentally, and that his memory was pinpoint sharp, even if there were some physical health issues, typical for anyone who makes it so far into their 80s (and, as we now know, beyond!).

A story that I was determined to hear from the source was the legendary quicksort 'wager'. The story goes that Tony told his boss at Elliott Brothers Ltd that he knew a faster sorting algorithm than the one that he had just implemented for the company. He was told 'I bet you sixpence you don't!'. Lo and behold, quicksort WAS faster. I asked Tony to tell this story pretty much every time we met, because I enjoyed it so much and it always put a smile on both of our faces. To his credit, Tony never tired of telling me this story 'right from the top'. I had hoped to visit again in the past year and record him telling it so that there was a record, but unfortunately this did not happen. However, I discover that it is indeed recorded elsewhere. One detail I might be able to add is that I asked Tony if indeed the wager was paid out or if it had merely been a figure of speech. He confirmed that indeed he WAS paid the wager (!). A detail of this story that I find particularly reflective of Tony's humble personality is that he went ahead and implemented the slower algorithm he was asked to, while he believed quicksort to be faster, and before chiming in with this belief. It speaks to a professionalism that Tony always carried.

About 50% of our meetings were spent talking about these matters relating to his career, while the rest varied across a vast range of topics. In particular, I wanted to ask him about a story that I had heard from a relative, that Tony - whilst working at Microsoft in Cambridge - would like to slip out some afternoons and watch films at the local Arts Picturehouse. This had come about because on one occasion a current film in question was brought up in conversation and it transpired Tony had seen it, much to the bemusement of some present. The jig was up - Tony admitted that, yes, sometimes he would nip out on an afternoon and visit the cinema. When I met Tony and gently questioned him on this anecdote he confirmed that indeed this was one of his pleasures and his position at Microsoft more than accommodated it.

On the topic of films, I wanted to follow up with Tony a quote that I have seen online attributed to him about Hollywood portrayal of geniuses, often especially in relation to Good Will Hunting. A typical example is: "Hollywood's idea of genius is Good Will Hunting: someone who can solve any problem instantly. In reality, geniuses struggle with a single problem for years". Tony agreed with the idea that cinema often misrepresents how ability in abstract fields such as mathematics is learned over countless hours of thought, rather than - as the movies like to make out - imparted, unexplained, to people of 'genius'. However, he was unsure where exactly he had said this or how/why it had gotten onto the internet, and he agreed that online quotes on the subject, attributed to him, may well be erroneous.

One final note I would like to share from these meetings with Tony is perhaps the most intriguing of what he said, but also the one he delivered with the greatest outright confidence. In a discussion about the developments of computers in the future - whether we are reaching limits of Moore's Law, whether Quantum Computers will be required to reinvigorate progress, and other rather shallow and obvious hardware talking points raised by me in an effort to spark Tony's interest - he said 'Well, of course, nothing we have even comes close to what the government has access to. They will always be years ahead of what you can imagine'. When pressed on this, in particular whether he believed such technology to be on the scale of solving the large prime factorisation that the world's cryptographic protocols are based on, he was cagey and shrugged enigmatically. One wonders what he had seen, or perhaps he was engaging in a bit of knowing trolling; Tony had a fantastic sense of humour and was certainly capable of leading me down the garden path with irony and satire before I realised a joke was being made.

I will greatly miss this humour, patience, and sharpness of mind, as I miss everything else about Tony.

RIP Tony Hoare (11 January 1934 - 5 March 2026)

By Lance Fortnow

Authors: Jing-Yuan Wei

We study a polynomial-time decision problem in which \emph{causal execution} is part of the instance specification. Each input describes a depth-$N$ process in which a single non-duplicable token must traverse an ordered sequence of steps, revealing only $O(1)$ bits of routing information at each step. The accept/reject outcome is defined solely by completion of this prescribed execution, rather than by order-free evaluation of the input. A deterministic Turing machine executes the process in $Θ(N)$ time. Using standard information-theoretic tools - specifically cut-set bounds for relay channels and Fano's inequality - we show that any execution respecting the causal constraints requires $Ω(N)$ units of causal time. Information about the delivery path can advance by at most one hop per unit of causal time, so the process admits no asymptotic parallel speedup. We further show that no classical $\mathbf{NC}$ circuit family can implement the process when circuit depth is interpreted as realizable parallel time. This identifies a class of polynomial-time problems with intrinsic causal structure and highlights a gap between logical parallelism and causal executability.

Authors: Kirill Krinkin

We study the gap between the minimum size of a Boolean circuit (DAG) and the minimum size of a formula (tree circuit) over the And-Inverter Graph (AIG) basis {AND, NOT} with free inversions. We prove that this gap is always 0 or 1 (Unit Gap Theorem), that sharing requires opt(f) >= n essential variables (Threshold Theorem), and that no sharing is needed when opt(f) <= 3 (Tree Theorem). Gate counts in optimal circuits satisfy an exact decomposition formula with a binary sharing term. When the gap equals 1, it arises from exactly one gate with fan-out 2, employing either dual-polarity or same-polarity reuse; we prove that no other sharing structure can produce a unit gap.

Authors: Rahul Jain, Srijita Kundu

Recently, Kretschmer et al. [KGD+25] presented an experimental demonstration of a proposed quantum information advantage protocol. We present an alternate proposal based on a relation derived from parallel-repeated CHSH games. Our memory measure is based on an information measure and is different from [KGD+25], where they count the number of qubits. Our proposal has an efficient verifier and a noise-robust quantum prover which is arguably much more efficient compared to [KGD+25].

Authors: Aminadav Chuyoon, Amir Shpilka

We study sparse polynomials with bounded individual degree and their factors, obtaining the following structural and algorithmic results. 1. A deterministic polynomial-time algorithm to find all sparse divisors of a sparse polynomial of bounded individual degree, together with the first upper bound on the number of non-monomial irreducible factors of such polynomials. 2. A $\mathrm{poly}(n,s^{d\log \ell})$-time algorithm that recovers $\ell$ irreducible $s$-sparse polynomials of individual degree at most $d$ from blackbox access to their (not necessarily sparse) product. This partially resolves a question of Dutta-Sinhababu-Thierauf (RANDOM 2024). In particular, if $\ell=O(1)$ the algorithm runs in polynomial time. 3. Deterministic algorithms for factoring a product of $s$-sparse polynomials of individual degree $d$ from blackbox access. Over fields of characteristic zero or sufficiently large characteristic the runtime is $\mathrm{poly}(n,s^{d^3\log n})$; over arbitrary fields it is $\mathrm{poly}(n,(d^2)!,s^{d^5\log n})$. This improves Bhargava-Saraf-Volkovich (JACM 2020), which gives $\mathrm{poly}(n,s^{d^7\log n})$ time for a single sparse polynomial. For a single sparse input we obtain $\mathrm{poly}(n,s^{d^2\log n})$ time. 4. Given blackbox access to a product of factors of sparse polynomials of bounded individual degree, we give a deterministic polynomial-time algorithm to find all irreducible sparse multiquadratic factors with multiplicities. This generalizes the algorithms of Volkovich (RANDOM 2015, 2017) and extends the complete-power test of Bisht-Volkovich (CC 2025). To handle arbitrary fields we introduce a notion of primitive divisors that removes characteristic assumptions from most of our algorithms.

Authors: Alexander Dobler, Siddharth Gupta, Philipp Kindermann, Fabrizio Montecchiani, Martin Nöllenburg

Storyline layouts visualize temporal interactions by drawing each character as an $x$-monotone curve and enforcing that the participants of every meeting form a contiguous vertical group. We study a drawing extension variant in which a layout of a sub-storyline is fixed and has to be extended by inserting missing characters while preserving all meeting constraints. We minimize the local crossing number $χ$, i.e., the maximum number of crossings along any single character. We prove that the problem is W[1]-hard parameterized by the number $k$ of inserted characters plus the maximum number $σ$ of active characters, in XP parameterized by $σ$ and in FPT parameterized by $σ+χ$.

Authors: Stefan Huber, Kristóf Huszár, Michael Kerber, Martin Uray

We propose an alternative formulation of the well-known Hough transform to detect lines in point clouds. Replacing the discretized voting scheme of the classical Hough transform by a continuous score function, its persistent features in the sense of persistent homology give a set of candidate lines. We also devise and implement an algorithm to efficiently compute these candidate lines.

Authors: Oswin Aichholzer, Katharina Klost, Kristin Knorr, Viola Mészáros, Josef Tkadlec

We consider a special, geometric case of a balancing game introduced by Spencer in 1977. Consider any arrangement $\mathcal{L}$ of $n$ lines in the plane, and assume that each cell of the arrangement contains a box. Alice initially places pebbles in each box. In each subsequent step, Bob picks a line, and Alice must choose a side of that line, remove one pebble from each box on that side, and add one pebble to each box on the other side. Bob wins if any box ever becomes empty. We determine the minimum number $f(\mathcal L)$ of pebbles, computable in polynomial time, for which Alice can prevent Bob from ever winning, and we show that $f(\mathcal L)=Θ(n^3)$ for any arrangement $\mathcal{L}$ of $n$ lines in general position.

Authors: Jette Gutzeit, Kalani Kistler, Tim Ophelders, Anna Schenfisch

The verbose persistent homology transform (VPHT) is a topological summary of shapes in Euclidean space. Assuming general position, the VPHT is injective, meaning shapes can be reconstructed using only the VPHT. In this work, we investigate cases in which the VPHT is not injective, focusing on a simple setting of degeneracy; graphs whose vertices are all collinear. We identify both necessary properties and sufficient properties for non-reconstructibility of such graphs, bringing us closer to a complete classification.

Authors: Jay Jayeshbhai Chavda, S Ganga Prasath

Origami and Kirigami, the famous Japanese art forms of paper folding and cutting, have inspired the design of novel materials & structures utilizing their geometry. In this article, we explore the geometry of the lesser known popup art, which uses the facilities of both origami and kirigami via appropriately positioned folds and cuts. The simplest popup-unit resembles a four-bar mechanism, whose cut-fold pattern can be arranged on a sheet of paper to produce different shapes upon deployment. Each unit has three parameters associated with the length and height of the cut, as well as the width of the fold. We define the mean and Gaussian curvature of the popup structure via the discrete surface connecting the fold vertices and develop a geometric description of the structure. Using these definitions, we arrive at a design pipeline that identifies the cut-fold pattern required to create popup structure of prescribed shape which we test in experiments. By introducing splay to the rectangular unit-cell, a single cut-fold pattern is shown to take multiple shapes along the trajectory of deployment, making possible transitions from negative to positive curvature surfaces in a single structure. We demonstrate application directions for these structures in drag-reduction, packaging, and architectural facades.