Theory of Computing Report

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: Ansh Nagda, Prabhakar Raghavan, Abhradeep Thakurta

We present improved lower bounds for five classical Ramsey numbers: $\mathbf{R}(3, 13)$ is increased from $60$ to $61$, $\mathbf{R}(3, 18)$ from $99$ to $100$, $\mathbf{R}(4, 13)$ from $138$ to $139$, $\mathbf{R}(4, 14)$ from $147$ to $148$, and $\mathbf{R}(4, 15)$ from $158$ to $159$. These results were achieved using~\emph{AlphaEvolve}, an LLM-based code mutation agent. Beyond these new results, we successfully recovered lower bounds for all Ramsey numbers known to be exact, and matched the best known lower bounds across many other cases. These include bounds for which previous work does not detail the algorithms used. Virtually all known Ramsey lower bounds are derived computationally, with bespoke search algorithms each delivering a handful of results. AlphaEvolve is a single meta-algorithm yielding search algorithms for all of our results.

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.

Authors: Josh Alman, Shyamal Patel, Rocco A. Servedio

We give an algorithm that learns arbitrary Boolean functions of $k$ arbitrary halfspaces over $\mathbb{R}^n$, in the challenging distribution-free Probably Approximately Correct (PAC) learning model, running in time $2^{\sqrt{n} \cdot (\log n)^{O(k)}}$. This is the first algorithm that can PAC learn even intersections of two halfspaces in time $2^{o(n)}.$

Authors: Kshitij Gajjar, Neeldhara Misra

We study a family of sorting match puzzles on grids, which we call permutation match puzzles. In this puzzle, each row and column of a $n \times n$ grid is labeled with an ordering constraint -- ascending (A) or descending (D) -- and the goal is to fill the grid with the numbers 1 through $n^2$ such that each row and column respects its constraint. We provide a complete characterization of solvable puzzles: a puzzle admits a solution if and only if its associated constraint graph is acyclic, which translates to a simple "at most one switch" condition on the A/D labels. When solutions exist, we show that their count is given by a hook length formula. For unsolvable puzzles, we present an $O(n)$ algorithm to compute the minimum number of label flips required to reach a solvable configuration. Finally, we consider a generalization where rows and columns may specify arbitrary permutations rather than simple orderings, and establish that finding minimal repairs in this setting is NP-complete by a reduction from feedback arc set.

Authors: Sebastiano A. Piccolo, Pasquale De Meo, Giorgio Terracina, Gianluigi Greco

The bus-factor is a measure of project risk with respect to personnel availability, informally defined as the number of people whose sudden unavailability would cause a project to stall or experience severe delays. Despite its intuitive appeal, existing bus-factor measures rely on heterogeneous modeling assumptions, ambiguous definitions of failure, and domain-specific artifacts, limiting their generality, comparability, and ability to capture project fragmentation. In this paper, we develop a unified, domain-agnostic framework for bus-factor estimation by modeling projects as bipartite graphs of people and tasks and casting the computation of the bus-factor as a family of combinatorial optimization problems. Within this framework, we formalize and reconcile two complementary interpretations of the bus-factor, redundancy and criticality, corresponding to the Maximum Redundant Set and the Minimum Critical Set, respectively, and prove that both formulations are NP-hard. Building on this theoretical foundation, we introduce a novel bus-factor measure inspired by network robustness. Unlike prior approaches, the proposed measure captures both loss of coverage and increasing project fragmentation by tracking the largest connected set of tasks under progressive contributor removal. The resulting measure is normalized, threshold-free, and applicable across domains; we show that its exact computation is NP-hard as well. We further propose efficient linear-time approximation algorithms for all considered measures. Finally, we evaluate their behavior through a sensitivity analysis based on controlled perturbations of project structures, guided by expectations derived from project management theory. Our results show that the robustness-based measure behaves consistently with these expectations and provides a more informative and stable assessment of project risk than existing alternatives.

Authors: Chengu Wang

We introduce a new method for proving bilinear complexity lower bounds for matrix multiplication over finite fields. The approach combines the substitution method with a systematic backtracking search over linear restrictions on the first matrix $A$ in the product $AB = C^T$. We enumerate restriction classes up to symmetry; for each class we either obtain a rank lower bound by classical arguments or branch further via the substitution method. The search is organized by dynamic programming on the restricted matrix $A$. As an application we prove that the bilinear complexity of multiplying two $3 \times 3$ matrices over $\mathbb{F}_2$ is at least $20$, improving the longstanding lower bound of $19$ (Bläser 2003). The proof is found automatically within 1.5 hours on a laptop and verified in seconds.

Authors: Hugo A. Akitaya, Joseph Dorfer, Peter Kramer, Christian Rieck, Gabriel Shahrouzi, Frederick Stock

We study the classic sliding cube model for programmable matter under parallel reconfiguration in three dimensions, providing novel algorithmic and surprising complexity results in addition to generalizing the best known bounds from two to three dimensions. In general, the problem asks for reconfiguration sequences between two connected configurations of $n$ indistinguishable unit cube modules under connectivity constraints; a connected backbone must exist at all times. The makespan of a reconfiguration sequence is the number of parallel moves performed. We show that deciding the existence of such a sequence is NP-hard, even for constant makespan and if the two input configurations have constant-size symmetric difference, solving an open question in [Akitaya et al., ESA 25]. In particular, deciding whether the optimal makespan is 1 or 2 is NP-hard. We also show log-APX-hardness of the problem in sequential and parallel models, strengthening the APX-hardness claim in [Akitaya et al., SWAT 22]. Finally, we outline an asymptotically worst-case optimal input-sensitive algorithm for reconfiguration. The produced sequence has length that depends on the bounding box of the input configurations which, in the worst case, results in a $O(n)$ makespan.

Authors: Chao Li

The Li-Chao tree (LICT) was first introduced in lecture as an efficient data structure for dynamic lower envelope maintenance. In the years since, it has achieved widespread adoption within the competitive programming community, yet no formal specification has appeared in the peer-reviewed literature. This paper provides the definitive formalization of the Li-Chao tree, serving as both the official specification and an expansion of the original lecture. We present complete algorithmic specifications, establish formal correctness proofs, analyze theoretical complexity, and provide empirical performance characterization. The LICT offers distinct advantages in implementation simplicity, numerical stability, and extensibility to advanced variants such as persistence and line segments.

Authors: Pravesh Kothari, Anand Louis, Rameesh Paul, Prasad Raghavendra

We study the problem of efficiently certifying upper bounds on the independence number of $\ell$-uniform hypergraphs. This is a notoriously hard problem, with efficient algorithms failing to approximate the independence number within $n^{1-ε}$ factor in the worst case [Has99, Zuc07]. We study the problem in random and semirandom hypergraphs. There is a folklore reduction to the graph case, achieving a certifiable bound of $O(\sqrt{n/p})$. More recently, the work [GKM22] improved this by constructing spectral certificates that yield a bound of $O(\sqrt{n}.\mathrm{polylog}(n)/p^{1/(\ell/2)})$. We make two key improvements: firstly, we prove sharper bounds that get rid of pesky logarithmic factors in $n$, and nearly attain the conjectured optimal (in both $n$ and $p$) computational threshold of $O(\sqrt{n}/p^{1/\ell})$, and secondly, we design robust Sum-of-Squares (SoS) certificates, proving our bounds in the more challenging semirandom hypergraph model. Our analysis employs the proofs-to-algorithms paradigm [BS16, FKP19] in showing an upper bound for pseudo-expectation of degree-$2\ell$ SoS relaxation of the natural polynomial system for maximum independent set. The challenging case is odd-arity hypergraphs, where we employ a tensor-based analysis that reduces the problem to proving bounds on a natural class of random chaos matrices associated with $\ell$-uniform hypergraphs. Previous bounds [AMP21, RT23] have a logarithmic dependence, which we remove by leveraging recent progress on matrix concentration inequalities [BBvH23, BLNvH25]; we believe these may be useful in other hypergraph problems. As an application, we show our improved certificates can be combined with an SoS relaxation of a natural $r$-coloring polynomial system to recover an arbitrary planted $r$-colorable subhypergraph in a semirandom model along the lines of [LPR25], which allows for strong adversaries.

Authors: Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff, Samson Zhou

We study the problem of constructing $(1+\varepsilon)$-coresets for Euclidean $(k,z)$-clustering in the distributed setting, where $n$ data points are partitioned across $s$ sites. We focus on two prominent communication models: the coordinator model and the blackboard model. In the coordinator model, we design a protocol that achieves a $(1+\varepsilon)$-strong coreset with total communication complexity $\tilde{O}\left(sk + \frac{dk}{\min(\varepsilon^4,\varepsilon^{2+z})} + dk\log(nΔ)\right)$ bits, improving upon prior work (Chen et al., NeurIPS 2016) by eliminating the need to communicate explicit point coordinates in-the-clear across all servers. In the blackboard model, we further reduce the communication complexity to $\tilde{O}\left(s\log(nΔ) + dk\log(nΔ) + \frac{dk}{\min(\varepsilon^4,\varepsilon^{2+z})}\right)$ bits, achieving better bounds than previous approaches while upgrading from constant-factor to $(1+\varepsilon)$-approximation guarantees. Our techniques combine new strategies for constant-factor approximation with efficient coreset constructions and compact encoding schemes, leading to optimal protocols that match both the communication costs of the best-known offline coreset constructions and existing lower bounds (Chen et al., NeurIPS 2016, Huang et. al., STOC 2024), up to polylogarithmic factors.

Authors: Zhou Fan, Timothy L. H. Wee, Kaylee Y. Yang

We study Bayesian inference of an unknown matching $π^*$ between two correlated random point sets $\{X_i\}_{i=1}^n$ and $\{Y_i\}_{i=1}^n$ in $[0,1]^d$, under a critical scaling $\|X_i-Y_{π^*(i)}\|_2 \asymp n^{-1/d}$, in both an exact matching model where all points are observed and a partial matching model where a fraction of points may be missing. Restricting to the simplest setting of $d=1$, in this work, we address the questions of (1) whether the posterior distribution over matchings is approximable by a local algorithm, and (2) whether marginal statistics of this posterior have a well-defined limit as $n \to \infty$. We answer both questions affirmatively for partial matching, where a decay-of-correlations arises for large $n$. For exact matching, we show that the posterior is approximable locally only after a global sorting of the points, and that defining a large-$n$ limit of marginal statistics requires a careful indexing of points in the Poisson point process limit of the data, based on a notion of flow. We leave as an open question the extensions of such results to dimensions $d \geq 2$.

Authors: Aiya Kuchukova, Will Perkins, Xavier Povill

In 1970 Hajnal and Szemerédi proved a conjecture of Erdös that for a graph with maximum degree $Δ$, there exists an equitable $Δ+1$ coloring; that is a coloring where color class sizes differ by at most $1$. In 2007 Kierstand and Kostochka reproved their result and provided a polynomial-time algorithm which produces such a coloring. In this paper we study the problem of approximately sampling uniformly random equitable colorings. A series of works gives polynomial-time sampling algorithms for colorings without the color class constraint, the latest improvement being by Carlson and Vigoda for $q\geq 1.809 Δ$. In this paper we give a polynomial-time sampling algorithm for equitable colorings when $q> 2Δ$. Moreover, our results extend to colorings with small deviations from equitable (and as a corollary, establishing their existence). The proof uses the framework of the geometry of polynomials for multivariate polynomials, and as a consequence establishes a multivariate local Central Limit Theorem for color class sizes of uniform random colorings.

Authors: Priyanka Sinha, Dilys Thomas

Network partitions pose fundamental challenges to distributed name resolution in mobile ad-hoc networks (MANETs) and edge computing. Existing solutions either require active coordination that fails to scale, or use unstructured gossip with excessive overhead. We present \textit{Structured Gossip DNS}, exploiting DHT finger tables to achieve partition resilience through \textbf{passive stabilization}. Our approach reduces message complexity from $O(n)$ to $O(n/\log n)$ while maintaining $O(\log^2 n)$ convergence. Unlike active protocols requiring synchronous agreement, our passive approach guarantees eventual consistency through commutative operations that converge regardless of message ordering. The system handles arbitrary concurrent partitions via version vectors, eliminating global coordination and enabling billion-node deployments.

Authors: Katalin Friedl, Levente Gegő, László Kabódi, Viktória Nemkin

Quadratic Unconstrained Binary Optimization (QUBO) is a standard NP-hard optimization problem. Recently, it has gained renewed interest through quantum computing, as QUBOs directly reduce to the Ising model, on which quantum annealing devices are based. We introduce a QUBO formulation for permutations using compare-exchange networks, with only $O(n \log^2 n)$ binary variables. This is a substantial improvement over the standard permutation matrix encoding, which requires $n^2$ variables and has a much denser interaction graph. A central feature of our approach is uniformity: each permutation corresponds to a unique variable assignment, enabling unbiased sampling. Our construction also allows additional constraints, including fixed points and parity. Moreover, it provides a representation of permutations that supports the operations multiplication and inversion, and also makes it possible to check the order of a permutation. This can be used to uniformly generate permutations of a given order or, for example, permutations that commute with a specified permutation. To our knowledge, this is the first result linking oblivious compare-exchange networks with QUBO encodings. While similar functionality can be achieved using permutation matrices, our method yields QUBOs that are both smaller and sparser. We expect this method to be practically useful in areas where unbiased sampling of constrained permutations is important, including cryptography and combinatorial design.

Authors: Pierre Ohlmann

We propose a new deterministic symmetric recursive algorithm for solving mean-payoff games.

Authors: Mike Heddes, Igor Nunes, Tony Givargis, Alex Nicolau

Tensor network contraction is a fundamental mathematical operation that generalizes the dot product and matrix multiplication. It finds applications in numerous domains, such as database systems, graph theory, machine learning, probability theory, and quantum mechanics. Tensor network contractions are computationally expensive, in general requiring exponential time and space. Sketching methods include a number of dimensionality reduction techniques that are widely used in the design of approximation algorithms. The existing sketching methods for tensor network contraction, however, only support acyclic tensor networks. We present the first method capable of approximating arbitrary tensor network contractions, including those of cyclic tensor networks. Additionally, we show that the existing sketching methods require a computational complexity that grows exponentially with the number of contractions. We present a second method, for acyclic tensor networks, whose space and time complexity depends only polynomially on the number of contractions.

Authors: Leo van Iersel, Mark Jones, Simone Linz, Norbert Zeh

A directed phylogenetic network is tree-child if every non-leaf vertex has a child that is not a reticulation. As a class of directed phylogenetic networks, tree-child networks are very useful from a computational perspective. For example, several computationally difficult problems in phylogenetics become tractable when restricted to tree-child networks. At the same time, the class itself is rich enough to contain quite complex networks. Furthermore, checking whether a directed network is tree-child can be done in polynomial time. In this paper, we seek a class of undirected phylogenetic networks that is rich and computationally useful in a similar way to the class tree-child directed networks. A natural class to consider for this role is the class of tree-child-orientable networks which contains all those undirected phylogenetic networks whose edges can be oriented to create a tree-child network. However, we show here that recognizing such networks is NP-hard, even for binary networks, and as such this class is inappropriate for this role. Towards finding a class of undirected networks that fills a similar role to directed tree-child networks, we propose new classes called $q$-cuttable networks, for any integer $q\geq 1$. We show that these classes have many of the desirable properties, similar to tree-child networks in the rooted case, including being recognizable in polynomial time, for all $q\geq 1$. Towards showing the computational usefulness of the class, we show that the NP-hard problem Tree Containment is polynomial-time solvable when restricted to $q$-cuttable networks with $q\geq 3$.