Theory of Computing Report

I was surprised by how divisive last Thursday’s post was. Some thought it was my best post, and others my worst. Let me convince you today that both assertions are true.

I understand why people are confused by the massive uncertainty in health-related decision making and enticed by evidence-based argumentation. When experts disagree, doesn’t that mean that someone is wrong? Shouldn’t there be a rigorous path to find the correct answer? Evidence-based medicine promised a reprieve from ambiguity through cold calculation. Its proponents still insist that biometry alone will lead us to universal truths.

Except, of course, it can’t. As I’ve been yammering on about, medical statistics tell us about population-level optimization and can’t say much about individuals. What a doctor believes about their patient comes from a complex synthesis of expertise and evidence. It never follows simply from a statistical decision-making computer program. EBM both displaces the physician as authoritative and displaces the patient into a statistical aggregate. Moreover, the conditions that establish population-level facts in a trial, like rigid inclusion criteria and strictly controlled experimentation, are simultaneously the conditions that render those facts inapplicable to any individual.

For anyone who’s read a bit of 20th-century French critical theory, that sounds an awful lot like a deconstructive moment. The founders of EBM thought of themselves as working in the pure spirit of Enlightenment rationalism. They were, in fact, unintentionally embracing postmodernism.

Postmodernism, fittingly, means many different things to many different people. Broadly speaking, it’s an embrace of the lack of universal truth, the fluidity of meaning, and the spirit of pluralism. Let me first explain some lessons worth drawing from the postmodernists, who have been far more right in their predictions than prognosticators ought to be. Then I’ll engage with those who receive postmodernism as nihilism and a rejection of plain facts.

Specifically, Jean-François Lyotard articulated how computerization led to an obsession with statistical optimization and an abandonment of grand shared narratives. He declared the postmodern condition to be the replacement of a collective search for universal truth with many disjoint searches for local optimality.

In the postmodern condition, scientific inquiry is reduced to asking whether interventions reduce costs, time, or deaths or increase shareholder value, productivity, or “well-being.” Knowledge is legitimated only if it can do something outside of itself. Research is funded only if it promises to improve performance. Science has to produce things that work. Whether or not any of these produce truth or understanding is irrelevant. Truth is justified through the attainment of ends.

Scaled-up statistical optimization is postmodern, be it in (evidence-based) medicine, economic development, or adtech. Once truth is arbitrated by number-go-up, you disregard explanation, mechanism, and experience in exchange for metric chasing. Lyotard warned us that if knowledge is governed by performance, then centralized technocratic power would get to decide what counts as knowledge and who gets to speak. In 1979, this needed a monograph. In 2026, it’s undeniable.

It is deliciously ironic that mathematical rationality—building statistical models and maximizing expected utility—is the epitome of Lyotard’s postmodernism. Those steeped in rationality would scoff and say that of course statistics isn’t postmodern.1 Rational calculation was supposed to be the purest form of modern reason. Instead, it has led to a fractured, virtualized, monetized cultural schizophrenia.

This is why the rationalist-adjacent crowd in Silicon Valley has been in a royal tizzy about the postmodernists and their antecedents. They have been fluffing jeremiads against “The Frankfurt School,” decrying postmodernism as the most harmful idea advanced against humanity, all while embracing attitudes toward reality that 20th-century postmodern theorists would have thought caricatures. Geoff Shullenberger has been writing great essays on this topic.2

Now, there’s a problem with pulling out the term postmodern. Lumping a bricolage of related ideas together under a catch-all also made a body of pressingly relevant thought easy to dismiss. I’m sure I’ve already lost people midway through this post because I chose to deploy it. The word “postmodern” tends to end conversations.

Indeed, that’s what happened in the 21st century. Scientists hated postmodernists who questioned their authority. Scientists also romantically put forward the idea that their theories explain universal truths about the fabric of reality and the technology we’ve built on top of it.3 In the 1990s, this led to heated public debates, culminating in the stupid controversy over Sokal’s hoax, in which a theoretical physicist got a fake paper filled with nonsense published in a postmodernism-friendly humanities journal. Postmodernism was thrown aside as unrigorous nonsense.

It was, of course, a pyrrhic victory. In the intervening decades, the academic STEM literature, with LLMs and perverse incentives, has Sokal-hoaxed itself to death. By contrast, the ensuing history has pretty much proven the postmodernists more than right.

So I’m choosing to use the term postmodern because it’s accurate and precise. The term explicitly captures the dialectic of mathematical rationality, the conflation of truth and utility, and the locality of efficacy. And though the French theorists wrote in an annoyingly inscrutable air of pessimism, I’d argue they offer glimpses of alternative political orders. It is perhaps only through productive disagreement that we might break free from the insidious, multiscale pressure of optimization.

Subscribe now

By Ben Recht

I refute the 1995 dream XOR lemma conjecture by Goldreich, Nisan, and Wigderson. I also give a counterexample to the XOR lemma for low-degree polynomials.

Authors: Srinivasan Arunachalam, Arkopal Dutt

We give a general framework for tomography of states that have bounded-extent with respect to a structured class of states. Let $\textsf{C}$ be a family of $n$-qubit states such that: $(i)$ $\textsf{C}$ is succinctly representable and $(ii)$ there is a weak agnostic learner of $\textsf{C}$. We give a tomography protocol for an unknown state $|ψ\rangle$ that is promised to admit a decomposition of the form $|ψ\rangle = \sum_i c_i |φ_i\rangle$, where $|φ_i\rangle \in \textsf{C}$ with bounded $\ell_1$-norm of the coefficients (which we call extent). Our main contribution is to show that a weak agnostic learner for $\textsf{C}$ can be boosted into a tomography algorithm for states with bounded extent with respect to $\textsf{C}$. Our reduction is black-box and applies broadly across model classes. As an application, when $\textsf{C}$ is the class of stabilizer states, we obtain tomography algorithms for states with stabilizer extent $ξ$ up to trace distance $\varepsilon$, in time $\textsf{poly}(n,(ξ/\varepsilon)^{\log(ξ/\varepsilon)})$, which is improvable to $ \textsf{poly}(n,ξ,1/\varepsilon)$ assuming the algorithmic polynomial Freiman-Ruzsa conjecture in the high-doubling regime. When the unknown state $|ψ\rangle$ is arbitrary, we give an algorithmic decomposition result in the spirit of a weak regularity lemma for quantum states with respect to $\textsf{C}$ and show that the structure in $|ψ\rangle$ that is explainable by $\textsf{C}$ can be efficiently learned. Our main conceptual message is that agnostic learning of a structured base class automatically yields learnability of its low-complexity linear span.

Authors: Xujun Bai, Yun Shang, Honghong Lin

The traveling salesman problem (TSP) is a significant classical NP-hard combinatorial optimization problem. In this work, we demonstrate that combining classical dynamic programming with quantum search can yield an achievable quantum advantage for TSP on the basis of excellent work by the authors of~\cite{ambainis2019quantum}. We design the quantum divide and conquer strategy to provide a parameterized spectrum for this combination. The hybrid algorithm proposed in~\cite{ambainis2019quantum} corresponds to a specific case in this spectrum, while the two extremes of the spectrum represent the purely classical Held-Karp and the purely quantum search algorithm, respectively. Within our parameterized spectrum, we prove that the optimal query complexity is $O^*(1.865666\ldots^n)$, achieved with the 4-subset scheme, while the counting in~\cite{ambainis2019quantum} overlooked half of the recursive branches. The correct query complexity of their algorithm is $O^*(2.225880\ldots^n)$ at their chosen parameter ($α\approx0.055362$), and cannot fall below $O^*(2^n)$ for any $α$ - meaning their $8$-subset scheme, correctly analyzed, never surpasses the classical Held-Karp bound. Furthermore, in previous studies on quantum advantages for NP-hard combinatorial optimization problems, researchers focused only on improvements in query complexity. Our work, however, points out that the quantum advantage stems not only from the quadratic speedup of quantum search but also from the structured quantum state preparation. We argue that structured state preparation is indispensable for realizing the oracle operator while maintaining the total time complexity of $O^*(1.865666\ldots^n)$. Therefore, we design an elegant method for preparing the set partition state, which makes our TSP solver practically executable.

Authors: Ruiqi Cui, Cem Akarsubaşı, Emil Toftegaard Gæde, Eva Rotenberg, Leif Kobbelt, J. Andreas Bærentzen

Surface reconstruction from point clouds remains challenging when both geometric fidelity and topology control are required. Rotation System Reconstruction (RsR) reconstructs triangle meshes from point clouds while explicitly controlling topology through the Euler characteristic, but its sequential edge insertion limits scalability. We present Hierarchical Rotation System Reconstruction (HRsR), which accelerates RsR through a hierarchical pipeline of edge collapses and vertex splits. HRsR first simplifies the input using a $k$-nearest neighbor graph, performs reconstruction on the reduced structure, and then restores geometric detail while preserving topology. To maintain geometric consistency, we incorporate intersection handling and quality-driven vertex split selection. Experiments demonstrate up to a $6\times$ speedup and more than $8\times$ reduction in memory usage over RsR, while achieving comparable reconstruction results.

Authors: Joshua Steier

Spielman-Srivastava spectral sparsification preserves Laplacian quadratic forms to within (1 +/- epsilon), but does not directly control the adjacency spectral radius lambda_1, which governs the NIMFA epidemic threshold and arises in spectral clustering. We prove |lambda_1(A_H) - lambda_1(A_G)| <= epsilon(2 Delta - lambda_1) deterministically, with a sharp epsilon*lambda_1 bound for reweighting sparsifiers via Perron-Frobenius monotonicity. Under effective-resistance sampling, Matrix Bernstein gives O(epsilon Delta / sqrt(c)) with high probability. Combining eigenvector delocalization with resolvent perturbation theory, we establish that for graphs with delocalized Perron eigenvectors and spectral gap = Omega(Delta), the distortion is O(epsilon Delta sqrt(log n) / sqrt(n)) + O(epsilon^2 Delta^2 / delta_gap), with corollaries for Erdos-Renyi graphs, regular expanders, and stochastic block models. Lower bounds establish tightness for regular graphs.

Authors: Akramah Faizi, Arash Rafiey

The Odd Cycle Transversal (OCT) problem, which asks for a minimum subset of vertices whose removal renders a graph bipartite, is a central problem in algorithmic graph theory. It is known to be NP-complete even on $P_k$-free graphs for $k \ge 6$. Furthermore, assuming the Unique Games Conjecture (UGC), OCT does not admit a constant-factor approximation algorithm on general graphs. Motivated by these hardness results, we investigate the approximability of OCT on $P_k$-free graphs. We first establish that the problem becomes polynomial-time solvable on specific subclasses of $P_k$-free graphs, most notably $(P_6, C_3)$-free graphs, by exploiting a structural decomposition into rings of bipartite graphs. Leveraging these tractable substructures as a basis, we present a constant-factor approximation algorithm for OCT on general $P_k$-free graphs. We achieve an approximation ratio of $k-2$ when $k$ is odd and $k-3$ when $k$ is even. These results provide the first nontrivial constant-factor approximations for this class dependent on $k$, aligning with the UGC implication that no approximation factor independent of $k$ is likely to exist.

Authors: Mateusz Gienieczko, Martín Muñoz, Filip Murlak, Charles Paperman

Streaming allows executing queries over massive JSON or XML documents whose size makes it infeasible to fully parse them into a tree. Earliest query answering is a radical approach to reducing latency and memory footprint. To minimize latency, a document node must be returned as soon as the node is guaranteed to be an answer regardless of how the document ends. Similarly, to minimize memory footprint, a node must be discarded as soon as it cannot become an answer regardless of how the document ends. For simple queries that select nodes based on the path from the root, the decision for each node can be made on the spot, but practical languages such as XPath or JSONpath support filters, which allow selecting nodes based on information collected from various parts of the document, possibly further down the stream. This makes earliest query answering a challenging task, as candidate nodes must be kept in memory until it becomes clear that they can be safely returned or discarded. We show that this can be done for all unary queries expressible in monadic second order logic (MSO), while ensuring constant update time -- provided that nodes are returned by passing a suitable iterator, rather than one by one.

Authors: Justin Y. Chen, Ying Feng, Piotr Indyk, Michael Kapralov, Ekaterina Kochetkova, Boris Prokhorov

The attention mechanism is a cornerstone of modern transformer architectures. However, its expressive power comes at the cost of quadratic runtime and linear space usage. In particular, the classical transformer architecture explicitly stores all previously seen input elements (tokens) in order to generate the next one. The problem of implementing a transformer in limited space, known as KV cache compression, has received much interest over the past few years, spurring the development of powerful heuristics. Recent works of Haris et al, COLT'25 and Kochetkova et al, NeurIPS'25, formalized KV cache compression as the streaming attention approximation problem, providing both upper bounds (based on discrepancy theory) and information theoretic lower bounds. However, those papers left open a significant gap between the upper and lower bounds. For example, the space usage of their algorithms increases with the precision parameter, but the lower bound does not get stronger. In this work, we revisit the streaming attention approximation problem and provide nearly tight bounds on its space complexity. On the algorithmic side, we achieve the result through a surprisingly tight interplay between three distinct methods for kernel density estimation: discrepancy-based coreset constructions (e.g., Charikar-Kapralov-Waingarten'24), the polynomial method (e.g., Greengard-Rokhlin'87, Alman-Song'23), and space partitioning (e.g., Andoni-Laarhoven-Razenshteyn-Waingarten'17, Charikar-Kapralov-Nouri-Siminelakis'20). On the lower bound side, our main technical contribution is a new technique for using the INDEX problem with a large amount of side information that we hope will prove useful in other high dimensional geometric estimation problems.

Authors: Tzvika Geft

This paper presents a simple framework that settles the complexity of Multi-Agent Path Finding (MAPF) on trees across standard objectives--distance, makespan, and flowtime--for both labeled and colored variants. In MAPF, agents occupy the vertices of a graph and must move to target vertices without collisions while optimizing a given objective. In the labeled case, the agents are distinct and have respective targets; in the colored case, agents of the same color are interchangeable. While many MAPF variants are known to be intractable, several basic cases on trees have remained open. We prove NP-hardness on trees for both labeled and 2-colored MAPF under all three objectives. In particular, we resolve the classical Pebble Motion problem, where one pebble moves at a time to an adjacent empty vertex and the goal is to minimize the total number of moves. Despite being one of the most basic discrete motion models, its complexity on trees had remained open for several decades. Moreover, for colored Pebble Motion, we give the first hardness result on any graph class, already with two colors, which is tight. All of these results are established through the hardness of Stack Rearrangement, itself posed as an open problem, which asks to optimally rearrange items stored in stacks, and which we also prove to be NP-hard. Notably, the connection to stacks yields hardness already on very simple trees--subdivided stars--across all problems. Together, these results reveal a common tractability barrier that permeates several fundamental motion models, thereby unifying and strengthening prior hardness results.

Authors: Mozhengfu Liu, Samir Khuller, Xueyan Tang

Motivated by the critical need for energy-efficient scheduling in cloud computing, this paper investigates Span Minimization, a fundamental variant of the well-studied BusyTime problem. In the general BusyTime problem, $n$ jobs characterized by release times, deadlines, and processing times must be partitioned into bundles of capacity $B$, where the objective is to minimize the total active duration of the virtual machines. Span minimization addresses the specific case of unbounded capacity ($B = \infty$), a problem that serves as a vital precursor for achieving high-performance approximation guarantees in more complex scheduling environments. While previous research established a deterministic $2$-approximation for interval jobs and a $3$-approximation for the general BusyTime problem, the online landscape of span minimization remains less explored. In this paper, we focus on the online version of span minimization. We demonstrate that randomization can be leveraged to break the known deterministic competitive barrier of $2$. For uniform-length jobs, we derive a randomized competitive upper bound of $\frac{1}{\ln{2}}\approx 1.443$ and a lower bound of $\frac{\sqrt{3}+1}{2}\approx 1.366$. Furthermore, we show that by introducing the ability to restart jobs, we can achieve an optimal competitive ratio equal to the golden ratio ($φ\approx 1.618$). Our results provide new insights into the power of randomization and flexibility in online energy-aware scheduling.

(In 2008 I wrote a survey of some of the known sum-product theorems, see here. Avi Wigderson has a great slide-set on sum-product theorems and their applications---the slides are on Avi's webpage of talks he has given (all the talks are excellent) which is here. I had a prior post on sum-product theorems here) 

If \(A\) is a set then let

\(A+A = \{ x+y \ \colon\  x,y\in A \} \),     \(A\cdot A = \{ xy \ \colon \  x,y\in A \} \).

Let \(A= \{1,\ldots,n\} \).

\(|A+A| = \Theta(n)  \) which is small. 

What about \(|A\cdot A|\)?  By the prime number theorem there are  \( \Theta(\frac{n}{\log n}) \) primes in \(A\) hence \(|A\cdot A| \ge \Omega(\frac{n^2}{\log^2n})\) by taking product of two primes. 

Or better: look at  \(\{ xy \ \colon \ x \hbox{ a prime in } \{n/2,\ldots,n\} , y \in \{1,\ldots,n/2\} \} \).

This is a subset of  \( A\cdot A \) of size  \( \Omega( \frac{n^2}{\log n} ) \). 

Ford improved this to 

\[ |A\cdot A| = \Theta\biggl (\frac{n^2}{(\log n)^a(\log\log n)^{3/2}} \biggr ) \]

 

 where  \(a=1-\frac{1+\ln\ln 2}{\ln 2} \sim 0.086\). So \(|A\cdot A|\) is Large! (Ford's paper is here.) 

Let \(A= \{2^1,\ldots,2^n\} \).

\(|A+A| = \Theta(n^2) \). Large!  \(|A\cdot A| = \Theta(n)  \). Small! 

Is it always the case that, for \(A\) a finite subset of numbers, \(\max(|A+A|,|A\cdot A|)\) is large?

In 1976 Erdős made a series of conjectures:

For all \(A\subset N\), A finite, \(\max(|A+A|,|A\cdot A|) \ge |A|^{2-o(1)} \).

For all \(A\subset Z\), A finite,  \(\max(|A+A|,|A\cdot A|) \ge  |A|^{2-o(1)}\).

For all \(A\subset R\), A finite,  \(\max(|A+A|,|A\cdot A|) \ge |A|^{2-o(1) } \).

For all  \(A\subset C\), A finite, \(\max(|A+A|,|A\cdot A|) \ge  |A|^{2-o(1) }\). 

Even though there are four of them (plural) these have come to be called The Sum-Product Conjecture (singular).

The paper appeared in the Israel Journal of Math and is oddly titled: Problems and results on 3-progressions and related topics. (I could not find this paper online- if you can, email me the pointer or pdf.)

In 1983 Erdős and Szemerédi made progress on the conjecture for \(Z\) by showing the following two theorems (they combine it into one).

1) There exists \(c>0\) such that, for all \(n\),  for all \(A\subset  Z \), \(|A|=n\), \( n^{1+c} < \max\{|A+A|,|A\cdot A|\}\). The \(c\) was very small. In my survey I present a sequence of results where \(c\) gets bigger and bigger. More has been found since my survey, see the Wikipedia page on Sum-Product Theorems here. 

2) There exists \(d>0\) such that, for all \(n\), there exists \(A\subset Z\), \(|A|=n\), such that  \(\max\{|A+A|,|A\cdot A|\}  < n^2\exp(\frac{-c\log n}{\log\log n})\).  

The paper appeared in a Studies in Pure Mathematics volume in memory of Paul Turán and is properly titled On sums and products of integers. The paper is here. For a sanity check I worked out that this is an improvements on Ford's result, so the set \(A\) in part 2 is better than \(\{1,\ldots,n\} \), see here.

Because of the two papers, the conjecture is sometimes attributed to Erdős and sometimes attributed to Erdős-Szemerédi.

Who should the conjecture be attributed to? It no longer matters since humans  found a counterexample to the conjecture! In particular Thomas Bloom, Will Sawin, Carl Schildkraut, and Dimitri Zhelezov found a counterexample for the conjecture over \(R\) (and hence also over \(C\)). Remarkably, they used a thought-to-be-obsolete tool called thinking. Their paper is here

The math world was shocked! An Erdős problem resolved by humans!  One Abel prize winner was quoted as saying We knew the day would eventually come when humans could resolve Erdős problems, but we didn't know it would come this soon!  Several math departments now have plans for workshops on Human Alignment.

MY POINTS

1) The Sum-Product conjecture is a well known and interesting conjecture, so this is not some obscure problem invented to make humans look good.

2) Human-generated or Human-assisted? The announcement claims that it  was mostly human. I tend to agree since if it was done by AI they wouldn't hide it, they'd brag about it (see my post: here).

3) AI may still be needed to clean up the proof. In the future, we will all use AI the way we currently use grad students, cleaning up what we do.

4) The final proof was readable. One concern about human proofs is that they would be unreadable and hard to verify. That was not the case here.

5) The ideas needed for the solution already existed; however:

a) The right combination was hard to find.

b) The relevant techniques used, algebraic number theory, are not standard tools in this field (What field is the sum-product conjecture in? If you have an opinion on this, leave a comment. Future blog topic: what dictates what field a conjecture is in? a theorem is in?)

c) It was widely believed that the Sum-Product conjecture was true.

d) Contrast the difficulty of the following two statements

The Sum-Product Conjecture over \(R\) is false. This requires finding a counterexample.

The Sum-Product Conjecture over \(N\) is true. If true this would require a proof that covers all finite subsets of \(N\).

The first statement seems easier to prove.

It would be of interest to see if humans can prove the Sum-Product Conjecture for \(N\).  Of course, it might not be true. In which case it would be even more impressive to prove it.  My undergraduates can not only prove \(\sqrt{2}\) and \(\sqrt{3}\) are irrational but also that \(\sqrt{4}\) is irrational.

6) In the short term, this result and what it portends, is good: math problems we care about will be resolved with the help of humans, perhaps solely by humans.  But in the long run AI may lose the ability---or at least the patience---to do the proofs themselves.

See item 10-ONE for a counter thought.

By gasarch

The hardness of the Learning Parity with Noise (LPN) problem is a foundational assumption in cryptography, forming the basis of constructions ranging from symmetric-key primitives to public-key encryption and beyond. A central open question is whether the average-case hardness of LPN can be based on worst-case complexity assumptions, as has been achieved for the analogous Learning With Errors (LWE) problem. Existing worst-case-to-average-case reductions for LPN [BLVW19, YZ21] rely on statistical smoothing of linear codes, which inherently limits the resulting average-case hardness to noise rates as large as $1/2 - 1/\mathrm{poly}(n)$, which is insufficient for public-key applications. We explore a new approach towards obtaining such reductions: rather than requiring that random sparse combinations of the rows of the generator matrix of a code be statistically close to uniform, we only require that they be computationally indistinguishable from uniform. This leads to a clean win-win structure: we show that any efficient LPN solver can be transformed into a pair of efficient algorithms $(S, D)$ such that for every matrix $A$ of appropriate dimensions over $\mathbb{F}_2$, either $S$ decodes the code generated by $A$ from random noise, or $D$ distinguishes random noisy codewords of the dual of this code from uniform. By instantiating this reduction with appropriate parameters, we obtain the average-case hardness of LPN with inverse-polynomial noise rate $n^{-\alpha}$ for any constant $\alpha < 1$, assuming the worst-case simultaneous hardness of decoding a code from random noise and distinguishing random noisy codewords of its dual from uniform. In particular, setting $\alpha = 1/2$, our reduction yields LPN hardness in the parameter regime required for Alekhnovich's construction of public-key encryption [Ale03], a regime that was previously inaccessible via worst-case reductions.

10 11 12 papers in May! With a mix of testing for logic, quantum, codes, and distribution testing, this was a very prolific and well-rounded month. Let’s get to it, in no particular order!

Constant time testability of first-order logic with modulo counting on finitary graphs, by Isolde Adler, Jenny Stimpson (arXiv). This paper is concerned with testing, in the bounded-degree graph model, graph properties which can be expressed in first-order (resp. second-order monadic) logic with additional modulo quantifiers. The main result is a “meta-theorem” which states that every such property concerning graphs with a uniform (constant) bound on the size of connected components can be tested with a constant number of queries.

Tolerant Testing for Unique Games, by Yuichi Yoshida (arXiv). The property testing version of Unique Games sees the constraint satisfaction problem over \(n\) variables and \(m\) constraints as a constraint graph \(G\) with \(n\) vertices and \(m\) edges, where the edges are labeled by permutations of the alphabet \([Q]\): the goal is then, given query access to the graph, to distinguish between he minimum fraction of constraints violated by any labeling being at most \(\varepsilon\) or at least \(\rho\). This paper considers the question in the adjacency list access model, where the algorithm can where the algorithm has uniform-vertex, degree, and neighbor query access to the graph. The main result is a tester which (in contrast to previous work) makes no structural assumption on the graph, and, for \(\varepsilon = O(\rho^4/\log n)\), solves this tolerant testing question with query complexity $\(\tilde{O}((\sqrt{m} + n/\sqrt{m})\text{poly}(1/\rho))\)$ for constant alphabet size \(Q\).

Optimal Testing of Reed-Muller Codes with an Online Adversary, by Esty Kelman, Uri Meir, Kai Zhe Zheng (arXiv). In the online erasure model of property testing, after each query made to the input \(f\), an adversary gets to erase up to \(t\) (adaptively chosen) values of \(f\). This makes the testing task much more challenging, requiring testers to (intuitively) behave somewhat unpredictably. In this paper, the authors define a new type of testers, in-between sample-based (only make uniformly random queries to the input) and query-based: semi-sample-based testers, which first choose an arbitrary subset \(S\) of potential queries, and then get uniformly random queries from \(S\). The main results are (1) a semi-sample-based tester for Reed-Muller codes in the “usual” testing model, which (2) can be made to work in the online erasure model (complemented by a lower bound showing it is then near-optimal).

Mean Testing under Truncation beyond Gaussian, by Yuhao Wang, Roberto Imbuzeiro Oliveira, Themis Gouleakis (arXiv). In the Mean Testing problem, given i.i.d. samples from a high-dimensional distribution with unknown mean vector \(\mu\), the goal is to distinguish between \(\|\mu\|_2=0\) and \(\|\mu\|_2 > \alpha\). While the fundamental cases of \(d\)-dimensional Gaussian distributions and product Bernoulli distributions are fully understood, a natural generalization is what happens when the samples are corrupted or censored: for instance, if samples are truncated (i.e., only samples within an (unknown) set \(S\) can be observed). Work of Canonne, Gouleakis, Wang, and Yang (2025) addresses the case of mean testing under truncation for identity-covariance Gaussians: this paper significantly generalizes these results, dropping the Gaussianity to allow for any class of high-dimensional distributions satisfying a bounded moment assumption.

Distributed Gaussian Mean Testing under Communication Constraints: messages, samples, and coins, by Clément Canonne and Nimitt (arXiv). Going back to Gaussian mean testing, what happens when the i.i.d. samples are distributed among \(n\) users each holding \(m\) samples, subject to strict (but possibly different) one-way communication constraints, and sharing a small random seed? The authors provide algorithms for Gaussian mean testing in this very general setting, which capture as special cases a number of previous works on distributed mean testing, and allow for smooth trade-offs between the parameters at play.

And now, onto the quantum realm!

On Clifford hierarchy testing and near-extremizers of noncommutative uniformity norms, by Zongbo (Bob) Bao, Jop Briët, Davi Castro-Silva, Philippe van Dordrecht, and Jonas Helsen (arXiv). The Clifford hierarchy is a sequence of quantum circuit models, allowing for increasingly general gates (the first level of the Clifford hirerachy being the set of Pauli gates, and the second is the Clifford group). In this paper, the authors consider the question of testing, given access to a unitary \(U\) (and its inverse), whether it belongs to a given level of the Clifford hierarchy, or is far from it. Their main result is an efficient testing algorithm for the 3rd level of the Clifford hierarchy, the first one still open: to do so, they establish a “robust inverse theorem” for the fourth Pauli uniformity norm \(P^4\), relating the closeness of a unitary to the 3rd level of the Clifford hierarchy to to its \(P^4\) norm.

Practical Tests and Witnesses of Fermionic non-Gaussianity, by Tobias Haug, Xhek Turkeshi, and Piotr Sierant (arXiv). In this paper, the authors are concerned with quantifying and detecting the distance of a (pure) \(n\)-qubit-quantum state to the set of Fermionic Gaussian States (FGS). Among other results, they provide two testing algorithms which distinguish between (1) being a (pure) Fermionic Gaussian state and (2) being at trace distance at least \(\varepsilon\) from every FGS: the first, using \(O(n^2/\varepsilon^2)\) two-copy Bell measurements, and the second, using \(O(n^3/\varepsilon^4)\) single-copy measurements.

Quantum Multi-Level Estimation of Functionals of Discrete Distributions, by Kean Chen, Minbo Gao, Tongyang Li, Qisheng Wang, Xinzhao Wang (arXiv). Given purified quantum query access to a classical probability distribution \(p\) over \(n\) elements, i.e., access to a unitary which prepares the state $$\sum_{i=1}^n \sqrt{p_i}|i\rangle |\textsf{garbage}_i\rangle$$, the goal is to estimate a functional \(f(p)\) of the distribution: distance to uniformity, entropy, support size… This paper provides a general framework to do so, for any function \(f\) for which \(f^2\) admits a low-degree polynomial approximation. As a direct application, the authors obtain improved quantum algorithms for estimating the \(q\)-Tsallis entropy of a discrete distribution, for all ranges of parameter \($q\) (and near-optimal for \(q > 1\)).

Sticking with distributions, but back to classical…

Entropy Equivalence Testing, by Clément Canonne, Yash Pote, Jonathan Scarlett, and Joy Qiping Yang (arXiv). In the standard task of closeness testing for probability distributions, one gets i.i.d. samples from two unknown probability distributions \(p,q\), and must distinguish between (1) \(p=q\) and (2) \(\text{TV}(p,q) > \varepsilon\), where TV denotes the total variation distance. This is now well-understood — but what happens when one changes (2) to something else? Some previous work considered different notions of distance than TV distance: in this work, (2) is relaxed to a much weaker version, only asking to reject when the entropies of \(p,q\) are significantly different. As shown in the paper, not only does this variant lead to a more sample-efficient tester, it can be very useful: used as a blackbox, this yields a better learning algorithm for a well-studied class of high-dimensional distributions, that of Bayesian networks.

Testing properties of trees in graphical models with covariance queries, by Sofiya Burova, Francisco Calvillo, Gábor Lugosi, Piotr Zwiernik (arXiv). The goal of this paper is to test properties about the structure of high-dimensional distributions (specifically, of Gaussian graphical models), but not from samples: instead, given queries to their covariance matrix, or, equivalently, to the graph encoding dependencies between variables. Here, the assumption is that this underlying graph is a tree, and the goal is to test its diameter: the main result is an bicriteria testing algorithm which decides whether the tree has diameter at least \(D\) or at most \((1-\delta)D\), making \(\tilde{O}(\frac{n^2}{D^2\delta^2})\) covariance queries (where \(n\) is the dimension).

Edit: I had forgotten one!

Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs, by Akash Kumar, Abhiruk Lahiri, and C. Seshadhri (arXiv). Influential results in graph theory and graph property testing are separator theorems, which state that some classes of graphs can be “partitioned” at little cost into small components. In particular, known separator theorems imply that bounded-degree minor-free graphs can be partitioned into connected components of constant size! This led to the notion of partition oracle, by Hassidim-Kelner-Nguyen-Onak, which, given access to a minor-free graph, asks to implement fast and consistent “oracle access” to such a partition: given a vertx \(v\), which connected component is it in? These have led to numerous advances in sublinear algorithm and property testing, but one aspect remained ill-understood: how large of an input random seed does a partition oracle need to achieve this consistent oracle access? This paper answers the question by showing that the constant-query partition oracle of Kumar, Seshadhri, and Stolman (2021) can be implemented with a constant-size random seed (for constant bounded degree and \(\varepsilon\)), being efficient in all respects.

Edit: I had forgotten two!

A digest of the work of Rothblum, Vadhan, and Wigderson (2013), by Oded Goldreich (ECCC). Interactive Proofs of Proximity (IPPs) are the property testing analogue of Interactive Proof systems, where the testing algorithm is allowed to interact with an all-powerful but untrusted prover. IPPs are fascinating objects, which have received significant interest since their introduction, a decade or so ago. In this expository work, the author provides a detailed overview, complemented with proofs and discussion, of a result of Rothblum, Vadhan, and Wigderson, who showed that any property decidable by log-space uniform circuits of small depth \(D\) and size \(S\) admits public-coin IPPs with perfect completeness, low query complexity, and low communication complexity, and round complexity \(O(D\log S)\). (The theorem further provides a smooth tradeoff between query complexity \(q\) and communication complexity \(c\): roughly, \(q\cdot c \approx n\cdot D^{O(1)}\)). This positive result is (somewhat) complemented by a negative one, showing the existence of some necessary trade-off between query and communication complexity.

By Clement Canonne

My interview in the Israeli Academy interview series Interviewer: Alex Lubotzky

At the beginning of the interview, I mentioned two lessons from my father. One was the formula for ((a+b)^2), which he showed me at a young age; the other was that everything becomes interesting if you devote yourself to it. (These two lessons were included in a short “promo” for the interview prepared by the Academy.)

We spoke about my mathematical activities in high school, where Alex and I first met, and about my years as a research student of Micha A. Perles, alongside a remarkable group of fellow students. We also talked about my wife Mazi—the best choice of my life—and about our children, Neta, Hagai, and Lior, as well as life in Jerusalem and Boston in the 1980s. Mazi and I first met in 1979 on a student trip to Sinai, just a week before it was returned to Egypt.

Most of the interview was devoted to mathematics: convex sets and polytopes, Helly-type theorems, high-dimensional trees, the Borsuk conjecture, linear programming, influences, the KKL theorem, noise, and quantum computing. I even brought along some polytopes and solids of constant width for demonstration.

Alex recalled that after my 2018 ICM plenary lecture he jokingly told me that my lecture had caused stock markets around the world to fall. I responded that Google’s flawed 2019 “quantum supremacy” announcement arguably caused investors in Bitcoin to lose ten billion dollars or so. We also briefly discussed the free-will problem in the context of the inherent noise sensitivity of physical systems.

At the end, we reminisced about two trips we took together: one in the 1970s to the Jordan River, and another in 2004, with our wives Yardena and Mazi, to the Amazon River and Rio.

Top two pictures, taken from the video. Right: my parents with my sister and me, around 1958. Left: Micha Perles carefully checking the proof of my main thesis result and writing out every step. At the end he triumphantly added “QED!!!” and “תושלב״ע”.

Bottom two pictures, taken during the interview. Right: with Alex Lubotzky and Yael Ben Haim. Left: with a few of my favorite polytopes.

My interview in ECAA. Interviewer: Toufik Mansour

Toufic Mansour founded the journal Enumerative Combinatorics and applications, and has conducted an impressive series of interviews with combinatorialists (and mathematicians with interests in combinatorics). Here is Toufik’s 2022 interview with me.

Some of Toufik’s questions are common to all his interviews, while others were specific to my research. If I ever decide to write a scientific autobiography, this interview could serve as a starting point.

Toufik asked about my formative years, and I told him about a book I received from my mother.

Mansour: We would like to ask you about your formative years. What were your early experiences with mathematics? Did these come under the influence of your family or other people?

Kalai: “… My mother gave me her high-school calculus book (she did not like mathematics very much, but realized that I did), and I remember trying to read it. I could understand various things (like functions), but I got stuck on the expression . I knew that x was a variable representing numbers, but I did not understand how numbers could be added to triangles.”

Toufik also asked about problems I have worked on for many years, and I mentioned three of my own: the cascade conjecture from 1974, the influence-entropy conjecture, and the following problem from the 1980s: find a (weighted) enumeration of Laman graphs with labeled vertices that gives .

Toufik asked me if there are there are topics in mathematics that are more important than others. I answered that I suppose there are such topics but then concluded with the statement  “I am not sure if importance is that important.” Looking back, sometimes this remark strikes me as clever, and at other times as rather silly.

My interview in the “Superposition Guy” Interviewer: Yuval Boger

Yuval Boger interviewed me on his podcast.  Transcript; Spotify.

Yuval Boger asked excellent questions about my position on quantum computing, and I was quite pleased with the substance of my answers. As for my delivery and English, at times I was reminded of what one of my MIT students in Calculus 18.011 wrote about me in 1983: “The TA mumbles, fumbles, and bumbles.” (In that course, taught by the legendary Frank Morgan, Noga Alon, Paul Seymour, and I were among the TAs.)

Toward the end, Yuval asked what I hoped the quantum computing community would take from my work, regardless of who ultimately turns out to be right.

In my response, I mainly elaborated on what might be learned from my work if I am right and, as I expect, scalable quantum computing—and even significant early milestones toward it—cannot be achieved. Such a possibility could have implications beyond quantum computing itself and may shed light on several questions in physics. I mentioned, for example, the scope of the time-energy uncertainty principle and the question of whether the new phases of matter required for topological quantum computing (“Majorana zero modes”) can actually exist.

At the same time, I said that if I am correct about quantum computers, then a great deal of the effort invested in this area will ultimately reach a dead end. In this context, I expressed my enthusiasm for the many smaller problems that arise within this grand endeavor, and my broader view that what we do has value—scientifically, intellectually, and personally—even if things do not go our way or according to our hopes.

This applies to many efforts toward quantum computing, which would become considerably less important if my theory is correct. It also applies more broadly to the work of mathematicians and scientists in a future where AI may be able to replace some of us.

By Gil Kalai

Simplex is usually stated with signed quorums that anyone can forward and verify. Here we describe an information-theoretic version. Parties have authenticated point-to-point channels, but no signatures and no transferable quorums. Each party therefore acts only on quorums of messages it received directly. The motivation is practical as well as conceptual: avoiding signatures removes signature verification from the critical path. Threshold signatures and multi-signatures can reduce this overhead in signed...

By Ittai Abraham, Sourav Das, Yuval Efron, Jovan Komatovic, Gilad Stern

Authors: Jehn-Ruey Jiang

We introduce Transition states (T states), denoted by $\ket{T_k^n}$, as a class of multipartite entangled states characterized by a fixed number of state transitions between adjacent qubits. These states form equal-amplitude superpositions over all states with a specified transition count. Unlike Bell states based on two-qubit correlations, GHZ states characterized by global correlations among all qubits, and W and Dicke states based on fixed numbers of qubit excitations, T states are defined by transition counts along an ordered sequence of qubits. We prove that T states are unitarily equivalent to Dicke states through a chain of CX (controlled-X) operations, thereby establishing a direct correspondence between transition-based and excitation-based representations of multipartite entanglement.

Authors: Marcel Wild

A Boolean function in CNF format is of type Positive$\wedge$Negative} if each clause C is either positive (i.e. all literals of C are positive) or negative (i.e. all literals of C are negative). As is well known, deciding the satisfiability of such CNFs is NP-complete. We say that a CNF is of type DisjointPositive if its clauses are positive and mutually disjoint. Dually define DisjointNegative. It is shown that the satisfiability of CNFs of type DisjointPositive$\wedge$DisjointNegative can be decided in quadratic time. Moreover, the modelset can be output in polynomial total time. This is relevant since it affects not only the modelsets of CNFs of type Positive$\wedge$Negative, but more generally of type Horn$\wedge$AntiHorn. As to the latter CNFs, they e.g. occur in connection with the fixpoints of a Monotone Boolean Network.

Authors: Abhishek Indupally, Ibraheem Alawadhi, Satchit Ramnath, Jami J. Shah

Engineering design is an iterative, simulation-driven process where traditional workflows rely heavily on computationally expensive analyses such as finite element and computational fluid dynamics. Although data-driven methods have accelerated design evaluation and optimization, most existing geometric representations discard parametric and feature-level semantics, limiting their integration with CAD-driven design workflows and reducing model interpretability. To address this gap, this work introduces Attributed Feature Graphs (AFGs), a feature-based representation that encodes design features, such as extrusions, ribs, and pockets, as nodes and their geometric or dependency relations as directed edges. AFGs preserve design intent and parametric structure while remaining compatible with standard graph-based learning methods, enabling end-to-end learning directly on CAD-derived feature graphs. The paper demonstrates the proposed representation through a surrogate-modeling case study on the CarHoods10K automotive hood frame dataset, where a Graph Neural Network (GNN) is trained as an evaluation engine to predict performance metrics from AFG inputs. The learned model achieves competitive surrogate performance compared with traditional data-driven approaches, but with the added benefit that engineers can map predictions back to specific CAD features and interpret how individual design elements influence system behavior. Furthermore, because AFGs are built from native CAD features, engineers can directly edit the underlying geometry in the CAD environment and reevaluate the design through the same learned model.

Authors: Henk Mulder

The extension of the analytic fractal curve trees of (2601.17490} to analytic surface patch trees reveals a new geometric structure: branch points are replaced by interface curves that transmit the full analytical state of parent patches to their children. These interfaces prove to be central in determining the topology of the surface patch trees, including for the conditions for self-similarity of the interfaces, the patches and thus the trees. We establish the analytic conditions for the integrability and well-posedness of the surface patch trees and introduce further restrictions for conformality. We demonstrate that patch trees have a natural foliation that slices the trees into one dimensional curve trees, each of which has their own Hausdorff dimension, jointly creating a smooth dimension field. We extend the two dimensional surface model to arbitrary dimensions $n$ where $n-1$ interface manifolds transport the $n$ field state of the parent patches to their child branches. We note that the balance or discrepancy between patch field dimension and the dimensions in which the branches may evolve, determine the analytical regime from essentially geometrical to essentially operational.

Authors: Alexandre L. M. Levada

Estimating local mean curvature at each point of a high-dimensional dataset is a key ingredient of geometry-aware machine learning algorithms, such as the Mean Curvature Boundary Points (MCBP) method. The naive implementation of this computation, based on a local shape operator approximated from k-nearest neighbor patches, involves an explicit construction of a matrix $H$ whose trace form yields an $O(m^4)$ cost per point, rendering the approach intractable for datasets with more than a few dozen features. This paper introduces two complementary contributions that together reduce this cost by several orders of magnitude. The first contribution is an exact algebraic identity. This identity, derived from the orthogonality of the eigenvectors of the covariance matrix and the cyclicity of the trace operator, eliminates $H$ entirely and reduces the per-point cost to $O(m^2)$ after the eigendecomposition. The second contribution addresses the remaining $O(m^3)$ bottleneck of the full eigendecomposition. Since the local covariance matrix has rank at most $k-1 \ll m$, we replace it with a truncated SVD of the $k \times m$ centered data matrix, an $O(k^2 m)$ operation, and derive an analytical approximation for the contribution of the null-space eigenvectors based on the expected value of their outer product under the Haar measure. The resulting estimator has total cost $O(k^2 m + k m p^2)$, where $p = k-1$. Experiments on real-world datasets confirm speedups of 50 to 300 times relative to the original implementation, with negligible loss when the fast estimator is used to replace the original version. By providing a scalable and data-driven estimate of local curvature, the proposed method establishes curvature as a practical geometric feature for a broad range of machine learning tasks, from classical to modern deep learning pipelines.

Authors: Chris Kapulkin, Nathan Kershaw

We introduce a new algorithm for computing persistent homology of Vietoris--Rips filtrations, which in many cases offers a considerable speedup over the existing implementation of the persistence pairing algorithm. The key innovation, called active enumeration, is made possible by a new theoretical framework of Reduction to Zero Differentials (hence RedZeD) in which to view persistent homology.

Authors: Vinicius M. Gonçalves, João Baião, Felipe Bartelt, Douglas G. Macharet, Gustavo M. Freitas, Héctor Azpúrua, Luciano C. A. Pimenta

Vector-field-based methods are widely used for robot control and are often applied to the path-tracking problem. Some vector field approaches require repeatedly computing the distance between the robot configuration and the curve, as well as the corresponding closest point. Recently, vector fields have been extended to Lie Groups. In this case, this computation can be expensive, especially when performed at high control frequencies on embedded platforms. This paper proposes a method for efficiently computing the distance between a point and a curve represented as what is called a G-polynomial curve, which is a curve representation that generalizes polynomial curves to matrix Lie groups. The proposed approach exploits the structure of these curves to reduce the problem to a small number of polynomial root-finding computations. Simulation results show that the method significantly reduces computation time while maintaining accuracy compared to existing optimization-based approaches. Practical formulas are also provided for the case of the group SE(3), and the method is validated experimentally on a robotic manipulator. The methodology is implemented in a computational package, available online.

Authors: Márk Hunor Juhász, Péter Madarasi

We study maximum matching problems in temporal graphs whose underlying graph is a tree. We consider two temporal models. In a $Δ$-matching, selected time edges sharing an endpoint must have time ticks differing by at least $Δ$. In a $γ$-matching, the selected objects are blocks of $γ$ consecutive appearances of the same underlying edge. We also consider the related ordered static problem of $d$-distance matchings. We show that maximum $Δ$-matching remains NP-hard on temporal trees for every $Δ\geq 2$, even in the sparse case where each edge appears at most twice. Using a reduction between the temporal models, we obtain the analogous result for maximum $γ$-matching on temporal trees, even when each edge admits at most two $γ$-edges. We also show, via a reduction from $d$-distance matching, that maximum $γ$-matching is APX-hard even when the underlying graph is bipartite. Complementing these hardness results, we identify several tractable cases. We prove that maximum $Δ$-matching is polynomial-time solvable on temporal trees in which every edge appears exactly once, and that maximum $γ$-matching is polynomial-time solvable when each edge admits at most one $γ$-edge. We also give dynamic-programming algorithms under bounded local-use and local-sparsity assumptions, and derive polynomial-time solvability of maximum $d$-distance matching when the input bipartite graph is a tree. Finally, we prove that both maximum $Δ$-matching and maximum $γ$-matching admit polynomial-time approximation schemes on temporal trees.

Authors: Naixu Guo, Po-Wei Huang, Qisheng Wang, Jayne Thompson, Patrick Rebentrost, Mile Gu, Chengran Yang

Financial crashes, cascading failures in infrastructure, and critical errors in AI systems are frequently triggered by events that occur with extremely small probability. Efficiently discovering and sampling events with probability below a threshold is therefore of critical interest. Yet this task is highly non-trivial using existing classical or quantum methods. Being rare, such events require an immense sampling overhead to collect sufficient data samples. Moreover, because the rare events are not known in advance, they cannot be flagged for amplification using standard techniques. Here, we introduce a quantum algorithm for rare-event discovery and sampling without first learning which events are rare. The algorithm achieves the optimal quantum scaling with the rarity threshold. We further demonstrate that this can achieve a quadratic speedup for heavy-tailed systems whose tail has nonvanishing total mass, and translates into a robust polynomial speedup for stationary stochastic processes, with the exponent determined by its entropy-rate structure.

Authors: Ruize Zhao

The textbook choice B=sqrt(n) for square-root decomposition is asymptotically natural, but it is not always the fastest implementation choice. We study block-size autotuning as a reproducible algorithm-engineering problem and show that a learned workload model can improve over fixed sqrt(n) on the tested implementation. Under repeated grouped cross-validation, the best policy is a full-feature KNN-9 model that reduces mean regret from 1.2882 to 1.0646 and yields a paired geometric-mean speedup of 1.151x. A confidence gate retains most of that gain while reducing slowdowns. A family-free full-observation follow-up remains better than fixed blocking, which suggests that the model is learning from workload statistics rather than memorizing labels. In contrast, short-prefix variants do not produce a successful low-overhead online tuner in the current prototype. External validation is selective but supportive: Zipf-Hotspot is the strongest out-of-distribution case, and a six-window Baleen follow-up still improves over fixed blocking. Overall, block-size choice is workload aware and platform aware, and the fixed sqrt(n) rule leaves substantial performance on the table.

Authors: Luciano Gualà, Simone Pellegrini, Luca Pepè Sciarria, Alessandro Straziota

Motivated by the problem of detecting large and cohesive groups of vertices in real networks, the task of finding large \emph{quasi-cliques} has attracted considerable attention across different research areas. From a computational complexity perspective, strong inapproximability results are known for this problem, yet several heuristics have been proposed to identify large quasi-cliques in real-world networks. Recently, [Pang \emph{et al.}, (WWW 2024)] introduced a similarity-based approach that represents the current state of the art. In this work, we extend that approach to \emph{dynamic} networks, thereby addressing an open problem posed by [Pang \emph{et al.}, (WWW 2024)]. We first present a Baseline fully dynamic algorithm where edges of the network can be both inserted and deleted. The algorithm exactly maintains the same quasi-clique returned by the algorithm by Pang et al. on the current graph, with update time $\widetilde{O}(Δ)$, where $Δ$ is the maximum degree. We then focus on the practically relevant incremental case, where only edge insertions are allowed, and design an algorithm with $O(\log Δ)$ update time. This method leverages a novel technique for dynamically maintaining accurate estimates of vertex $γ$-degrees, a core component of framework by Pang et al., and achieves up to $207\times$ speed-up over the Baseline while preserving comparable solution quality. Finally, we extend the approach to the fully dynamic setting, supporting both insertions and deletions, obtaining up to $21\times$ speed-up with limited and acceptable loss in quasi-clique size and density. We provide a formal analysis of our algorithms and validate them through an extensive set of experiments on real-world datasets.

Authors: Marcin Zukowski

Huffman encoding has been an enduring technique for 70+ years, ubiquitous in compression algorithms since its invention. In this paper we propose a new approach to Huffman coding, based on a data structure from wavelet trees. The resulting pivot-coded Huffman (PivCo-Huffman) enables high-performance SIMD-friendly encoding and decoding operations. In our tests PivCo-Huffman consistently outperforms state-of-the-art Huffman codecs in decoding throughput. Additionally, we show how ANS-coding can be selectively applied to skewed nodes in this structure, yielding compression ratios approaching those of ANS-based codecs while preserving very high decompression speeds.

Authors: Ting Hou, Yanhao Wang, Yiping Wang, Cen Chen, Minghao Zhao, Fan Dang

In this paper, we study multi-objective submodular maximization (MOSM) subject to a cardinality constraint under differential privacy (DP). Specifically, we aim to select a set of at most $k \in \mathbb{Z}_{+}$ elements to maximize the minimum of $d > 1$ monotone submodular functions while satisfying $\varepsilon$-DP. Although extensive studies have been conducted on both differentially private single-objective submodular maximization on sensitive data and non-private MOSM, to the best of our knowledge, there has not yet been any prior work on MOSM with DP. We propose two novel algorithms: the first extends the classic greedy algorithm and the second employs a truncation technique, both of which are integrated with DP mechanisms for privacy protection and achieve approximation guarantees for MOSM. Finally, we conduct numerical experiments on two submodular maximization applications, namely maximum coverage and facility location, in multi-objective settings to validate the efficacy and efficiency of our proposed algorithms.

Authors: Josh Ascher, Eric Balkanski, Jason Chatzitheodorou, Vasilis Gkatzelis

In the classic online min-cost matching problem, the goal is to match a sequence of requests that arrive dynamically over time to a set of static servers, aiming to minimize the total cost of the matching. This assumes that there are two distinct "sides" and that only one of these sides arrives online, but many of the motivating applications violate these assumptions. We study online min-cost perfect-matching when \emph{all} participants arrive online and, upon arrival, they need to either be matched to someone from a waiting pool or to join the waiting pool. We evaluate the competitive ratios achievable in different input models and show that for both the adversarial and the random-order input models the competitive ratio of any algorithm is unbounded. In contrast, for i.i.d. arrivals we give a $O( \log^2{n})$-competitive algorithm, even if the distribution that generates these arrivals is unknown to the algorithm. This result implies a rare example of separation in the achievable competitive ratio between the random-order and the unknown-i.i.d. input models.

Authors: Lei Dong, Bowie Liu, Dennis Wong, Lin Chen, Chan-Tong Lam, Sio-Kei Im

A grand Motzkin path with air pockets is a non-empty lattice path in the first and fourth quadrant of $\mathbb{Z}^2$, starting at the origin $(0,0)$, ending on the $x$-axis, and consisting of up-steps $(1, 1)$, horizontal steps $(1, 0)$, down-steps $(1, -k)$ where $k \geq 1$, and with no consecutive down-steps. A {grand Dyck path with air pockets} is a grand Motzkin path with air pockets that uses no horizontal steps. We present the first known 2-Gray codes for grand Motzkin paths with air pockets. Setting the number of horizontal steps to zero in our algorithm yields the first known 2-Gray codes for grand Dyck paths with air pockets. Our three-stage algorithm generates each path in constant amortized time per string, using $O(n^2)$ memory. We also provide enumeration formulae for grand Motzkin paths and grand Dyck paths with air pockets.

Authors: Faruk Alpay, Levent Sarioglu

A long-running append-mostly sequence, such as an edit log, event store, or versioned working set, is usually tiered into a bounded hot stratum and colder folded summaries. This saves memory but breaks stable references: a handle minted while a record is hot may later be resolved after the record has moved into a digest, after it has been superseded, or while a fold is in flight. We define the resulting cross-tier anomalies--dangling, stale, corrupt, and snapshot-skewed resolution--and present the Cascade Log, a reference-stable tiered append structure. The structure keeps a single persistent coalescing interval map over handles as the sole authority on each live version; folding a contiguous run replaces many singleton entries by one digest-backed interval node, and immutable roots provide snapshot tokens. Its cost is characterized by the fragmentation $A$, the number of index pieces, namely live handles plus maximal same-digest runs. The index uses $Θ(A)$ space, resolves a point in $O(\log A)$, reports a $k$-handle range in $O(\log A+k)$, and performs $a$ appends and $s$ supersedes in $O((a/B+s)\log A)$ update work for fold block size $B$. Matching lower bounds show that $Ω(A)$ space and $Ω(\log A+k)$ ordered range cost are unavoidable, and an adversary can force $A=Θ(s)$. Thus the index is sublinear on append-dominated histories and grows linearly only under fragmenting edits. A reference implementation and reproducible experiments to $10^6$ records validate the anomaly-freedom and the fragmentation bounds.

Authors: Christian Coester, Alexa Tudose, Alexander Turoczy

We present learning-augmented algorithms for two general classes of online minimization problems: metrical task systems and laminar set cover. Both algorithms achieve improved theoretical guarantees using machine-learned predictions of an optimal solution to the dual linear program. Unlike optimal primal solutions, which can change drastically under tiny instance perturbations, these dual solutions are much more stable, which ensures the existence of good (and learnable) predictions for families of similar instances. While previous work has used dual predictions in offline settings and for online maximization problems, our algorithms are, to the best of our knowledge, the first demonstration that such dual predictions can be effective for online minimization. Our theoretical results are complemented by experiments on the $k$-server problem and the parking permit problem.

Authors: Haoyu Wang, Guangxu Yang

In this paper, we give a one-pass quantum streaming algorithm for Max-$k$SAT that uses $\operatorname{polylog}(n)$ space and achieves a $0.7172$-approximation on instances with $n$ variables. In contrast, prior work by Chou, Golovnev, and Velusamy (FOCS 2020) implies that achieving an approximation ratio better than $\sqrt{2}/2 \approx 0.7071$ for Max-$k$SAT requires $Ω(\sqrt{n})$ space for any classical streaming algorithm. Therefore, it yields an exponential quantum space advantage for Max-$k$SAT in the streaming setting. We further give a one-pass quantum streaming algorithm for Max-2OR that uses $\operatorname{polylog}(n)$ space and achieves a $0.7425$-approximation on instances with $n$ variables. Combining with the known results, it gives a complete classification of quantum space advantages for all Boolean Max-2CSPs.

June 4-22, 2026 STOC 2026, Salt Lake City, Utah, USA, and Gather.Town https://acm-stoc.org/stoc2026/call-for-posters.html Submission deadline: June 12, 2026 As part of the STOC 2026 program, we will be hosting an online poster session from 18:30-19:30 MDT (GMT -6) on Monday, June 22, 2026 on the platform Gather.Town. Our hope is that people who cannot come … Continue reading STOC TheoryFest 2026 Online Poster Session – Call for Posters

By shacharlovett

Weighted pseudorandom generators (wPRGs) were suggested by Braverman, Cohen, and Garg (STOC, 2018) as a relaxation of pseudorandom generator (PRG) used for derandomization. We present proofs of several observations regarding wPRGs, where some of these observations are well known.

There is a tempting story you can tell about the cardiology megatrials I’ve written about in the past few posts. If you focus on a single health outcome (say, mortality) and a single disease (say, infarctus du myocarde, aka heart attack), you can optimize the treatment program by continually running randomized clinical trials. Each trial will carefully compare two nearly identical treatment regimens that differ only in a single step. Professional societies will regularly communicate the latest results and guidelines. Piecemeal improvements to the standard of care will be broadcast at meetings and on websites to keep all clinicians up to date on the best plan for every patient.

This approach can be applied to multiple diseases. With enough buy-in, these trials can be scaled up to provide personalized adjustments to the standard of care. Patients’ demographic information, family history, and behaviors can then be considered, and professional societies can craft specialized plans for each demographic bucket.

Now, statistical calculations would quickly tell you that you need far more than 8 billion people to make this optimized dream a reality. But let’s leave that aside for a minute. There’s something bizarre and alienating about this view. In this pipe dream, care becomes nothing more than a computer algorithm. A patient becomes nothing more than a classification assignment. Healthcare becomes nothing more than optimizing actuarial tables. Is this dignified? Is this care? Is this what we want the medical system to be?

There was a reactionary and revolutionary movement in the 1990s that thought yes, healthcare should be nothing more than the application of clinical data: evidence-based medicine.

EBM remains incredibly influential. I mean, who wants medicine that isn’t based on evidence, right? Back in 2020, I also had a brief moment when I thought this was a brilliant way to conceptualize medicine. For mathematically minded people, EBM has the appeal of rigor. It provides what appears to be a set of clear rules for deciding on medical treatment. There is a hierarchy of evidence. A pyramid, if you will:

Expert opinion is the lowest form of evidence. Case studies are barely better. Epidemiological studies would be of slightly higher grade, but these are too easily fooled by confounding causes. A big step above, a gold standard, is the randomized controlled trial. And at the very top, we place an even higher grade on systematic reviews of all randomized controlled trials conducted on a disease.1

Once you have this evidence in hand, you can make clear decisions. You don’t need expertise. You simply need a Meehlian formula: you plug all of the data you have about a patient into a computer. The computer spits out a treatment plan for the patient based on the highest grade evidence available. Healthcare is now solved.

You might think I’m caricaturing their position, but you can go back to the original position papers, and the quotes are even stronger than what I say. Here’s the opening paragraph of “Evidence-Based Medicine: A New Approach to Teaching the Practice of Medicine,” written by a working group chaired by EBM pioneer Gordan Guyatt:

“A new paradigm for medical practice is emerging. Evidence-based medicine de-emphasizes intuition, unsystematic clinical experience, and pathophysiologic rationale as sufficient grounds for clinical decision making and stresses the examination of evidence from clinical research. Evidence-based medicine requires new skills of the physician, including efficient literature searching and the application of formal rules of evidence evaluating the clinical literature.”

The working group was explicit about expert judgment: “The new paradigm puts a much lower value on authority. The underlying belief is that physicians can gain the skills to make independent assessments of evidence and thus evaluate the credibility of opinions being offered by experts.” In their view, expert intuition and creative care caused more harm than good. Moreover, they thought a move to computerized decision making would improve patient outcomes, writing “A final assumption of the new paradigm is that physicians whose practice is based on an understanding of the underlying evidence will provide superior patient care.”

Computerization was exactly what they had in mind. David Sackett put together a prototype treatment computer, called The Evidence Cart, in the early nineties. Check him out making a diagnosis:

Sackett stuffed the evidence cart with a compendium of information: BestEvidence, the JAMA Rational Clinical Examination series, the Cochrane Library, multiple textbooks, and material compiled by his collaborators from journal groups and other assessments. Sackett’s crew would wheel the Evidence Cart into a patient room and evaluate each decision against the best evidence.

Did it work? Hilariously, the evidence that the Evidence Cart works is a tiny, single-center observational study, not an RCT. But the influence of EBM and the goal of making Sackett’s dream a reality was undeniable. Doctors now have supercomputers in their pockets at all times. They can pull out medical calculators, reduce patients to categories, and prescribe treatment plans based on the best evidence. Every doctor-patient visit is hooked up to a different computer that serves not only as a way for doctors to keep records of how their patients are doing, but also as a way to file them as statistics in actuarial tables at insurance companies and to enter their virtualized identity into the pool of future observational studies.

Has healthcare landed in a good spot? It’s complicated. Obviously, studies are good. But the idea that you can synthesize an optimal decision from the medical literature is crazy, whether you have modern LLMs or not. You can’t do an RCT of every possible option. We’ve already seen that expert knowledge is needed to decide which RCTs to do and to make sense of RCTs that seemingly contradict each other. And the medical literature does not tell you what to do with an individual patient. Patients are not just category labels. Care is more than robotic decision-making.

I’m more sympathetic to the iatrogenic argument put forward by the EBM pioneers. Many were medical conservatives. They thought that most treatments not only lacked evidence but were also harmful. You can look at the barbarism that riddles the history of medicine and certainly see that they had a point. Medical conservatives believe that we should err on the side of treating less not more. EBM was partially a battle against the intervention bias that still plagues medicine. “We have to do something” feels right, but is often harmful. This is why the CAST trial on anti-arrhythmia drugs is a poster child for the movement.

Though well-intentioned, evidence-based medicine is one of the best case studies of how the quantification trap leads to madness. We computerize everything to displace the influence of narratives. Mechanism and natural law don’t matter. The only thing that matters is optimizing outcomes. The pursuit of medical knowledge is only to optimize actuarial tables, not to understand the human condition. Medicine becomes a video game. This is the purest form of what Jean-François Lyotard called postmodernism. Statistical thinking run amok is the postmodern condition.

Subscribe now

By Ben Recht

Authors: Qisheng Wang

Tight bounds on quantum sample complexity and quantum query complexity have been known for various computational problems in the literature, whereas tight bounds on quantum time complexity (i.e., the size of quantum circuits) remain unresolved. In this paper, we provide a framework to establish lower bounds on the quantum time complexity for testing permutation-invariant properties of quantum states, via a reduction from quantum sample complexity. As an application, we obtain a series of matching lower bounds when given sample access to the input quantum states, including: 1. The SWAP test due to Buhrman, Cleve, Watrous, and de Wolf (Phys. Rev. Lett. 2001) is time-optimal to estimate the purity $\operatorname{tr}(ρ^2)$ and the inner product $\operatorname{tr}(ρσ)$. 2. The Shift test due to Ekert, Alves, Oi, Horodecki, Horodecki, and Kwek (Phys. Rev. Lett. 2002) is time-optimal to estimate the high-order functionals $\operatorname{tr}(ρ^k)$. 3. The productness tester for multipartite pure states due to Harrow and Montanaro (J. ACM 2013) is time-optimal. 4. The LMR protocol due to Lloyd, Mohseni, and Rebentrost (Nat. Phys. 2014) is time-optimal to implement the reflection operator about a pure state. 5. The samplizer due to Wang and Zhang (IEEE Trans. Inf. Theory 2025) is time-optimal for pure states. 6. The estimator for pure-state trace distance and fidelity due to Wang and Zhang (ICALP 2026) is time-optimal. To the best of our knowledge, this is the first method that allows us to systematically establish tight lower bounds on quantum time complexity.

Authors: Fedor Kiselev

We study the relationship between deterministic and randomized black-box reducibility between problems in TFNP. Our main contribution is a general technique that establishes equivalence between these reducibility types from specific TFNP problems to any TFNP problem. In particular, we show that this equivalence holds for reductions from complete problems in PPP, PPAD, PPA, and $t$-PPP. In turn, it strengthens all known black-box separations, originating from these classes, to randomized separations.

Authors: Matthew Finlayson, Andreas Grivas, Xiang Ren, Swabha Swayamdipta

Language model parameters are known to impose unique (to each model) geometric constraints on their logit outputs, which serves as a signature that identifies the model, but also leaks the model's final layer parameters when an API distributes logits. We investigate more restrictive APIs that expose token rankings (i.e., their ordering by probability, but not the probability values) and find that rankings also constitute a signature: every model has a unique set of feasible top-$k$ rankings for sufficiently large $k$. Furthermore, the ranking signature is the first known (polynomially) unforgeable signature, since finding a model with the same set of feasible rankings is NP-hard. On the security front, we find that token rankings are already sufficient to approximately steal the final layer of the model, similar to logits, though the approximation is too coarse to forge the signature, and can be effectively countered by restricting the API to top-$k$ tokens with sufficiently small $k$. Since the top-$k$ required to present the model signature is generally smaller than the $k$ required to prevent stealing, it is possible for an API to present an unforgeable signature without leaking model parameters.

Authors: Tayfun Pay

We define a new family of complexity classes called bit-counting complexity classes, since membership depends not merely on the number of accepting paths, but also on the binary profile of that number. We study the relationship between this new family of complexity classes and the classical complexity classes. We prove that the classical complexity class ${\bf PP}$ is contained in our comparison based bit-counting complexity classes ${\bf B_{|0|=|1|}P}$, ${\bf B_{|0|<|1|}P}$ and ${\bf B_{|0|>|1|}P}$. We further show that all of these complexity classes are Turing equivalent ${\bf P}^{\bf PP} = {\bf P}^{{\bf B_{|0|=|1|}P}}={\bf P}^{{\bf B_{|0|>|1|}P}}={\bf P}^{{\bf B_{|0|<|1|}P}}$. We also prove that classical complexity classes ${\bf NP}$ and ${\bf CoNP}$ are contained in both of our parity based bit-counting complexity classes ${\bf B_{|0| \oplus}P}$ and ${\bf B_{|1| \oplus}P}$.

Authors: Hunter Monroe

Monroe (2026) shows that the nonexistence of an optimal proof system can be read as an information constraint regarding canonical hard instances: no sound arithmetic theory simulates the extensions adjoining sufficiently large, unprovable Busy Beaver values. Furthermore, if the best-known route to simulation is also necessary -- that is, if simulation requires a relative-consistency explanation over a weak base theory -- then the same constraint holds for inaccessible Kolmogorov-randomness facts. Call this Kolmogorov Hardness (KH). We argue that open questions in computational complexity can likewise be reformulated as information constraints involving Kolmogorov-random strings. Variants of KH yield, as conditional consequences, dense families of small hard tautologies, no-mutual-help phenomena for independent random axioms, PH noncollapse with explicit dense separators at each level, $SAT\notin P/poly$, and canonical disjoint NP pairs arising from random-axiom constructions. Time-bounded and sparse-support variants extend the same template to one-way functions via Liu--Pass, derandomization, natural-proofs-style limitations, and Feige-style random refutation. This framework gives a unified working model of complexity theorists' beliefs, organized around canonical hard instances. It seems self-evident that efficient proofs in a theory should not leverage true randomness facts the theory cannot verify. Yet the structural features of KH and its variants suggest they may be formally independent of standard metatheories. They behave like reflection principles; their internal readings fail in nonstandard models even when the corresponding external readings are true; and the same information constraints may apply to the metatheories themselves. We propose a research program: extend the model, resolve questions of formal independence, and identify which principles are potential new axioms.

Authors: Masahito Nakano

We study Sibley's guard-point convexity measure for simple polygons and compare it with the exterior and perimeter convexity measures. We prove the exterior inequality G(F) <= E(F) and disprove the pointwise perimeter inequality G(F) <= P(F) by an explicit nonconvex pentagon with G(F) = 62/63 and P(F) = 185/189. Nevertheless, we prove the uniform bound G(F) <= 2P(F) for every simple polygon. Thus the pointwise perimeter inequality is false, but the corresponding asymptotic non-domination conclusion remains true. We also record an auxiliary guard-point-adapted anisotropic perimeter ratio, which isolates the directional loss in the Euclidean perimeter comparison.

Authors: Minjie Tang, Xiangfei Li

Generating compact polygonal models from point clouds is a key problem in 3D vision and computer graphics. However, due to inherent limitations of LiDAR scanning (e.g. range constraints and occlusions), critical scene information is often missing, leading to degraded reconstruction accuracy. To address this, we propose a plane assembling strategy that effectively recovers missing details while maintaining model compactness. We classify all the planes extracted from the scene into three categories: highly visible, barely visible, and invisible. The invisible planes, which are recovered by scene structure analysis, indicate the missing details. The three types of planes correspond to the three growth priorities. Each plane grows according to the priority level, and the space is partitioned progressively, namely, the hierarchical partition. Subsequently, we generate a watertight polygonal mesh from the partition via a min-cut-based optimization. Finally, comparisons on public datasets show the effectiveness and superiority of our method against mainstream approaches. The project page is available at https://hsr-3dv.github.io/.

Authors: Panagiotis Simatis, Panagiotis Bouros, Nikos Mamoulis

Spatial indexing is foundational to Geographic Information Systems (GIS) and multi-dimensional data management, yet the current open-source landscape poses a significant barrier to research that employs or benchmarks spatial access methods. We observe that most of the existing open-source libraries include a single index. Some are hindered by complex dependencies, missing critical functionalities, inconsistent APIs, and rigid constraints regarding the support of spatial data types. To address this issue, we introduce Indexicon: a unified, highly portable, extendable, open-source spatial indexing library, designed specifically for rapid integration and ease of modification of main-memory spatial access methods. Indexicon provides a comprehensive suite of popular tree-based spatial access methods, including the R-tree, Quad-tree variants, and the KD-tree. Each structure is meticulously implemented as a self-contained, single-file, header-only C++ template with zero external dependencies beyond the standard library. Crucially, every index features a uniform interface, natively supporting bulk-loading, dynamic insertions/deletions, range queries, $k$-nearest neighbor ($k$NN) search, and structural statistics tracking. We also present an extensive performance evaluation of Indexicon against well-established and widely used implementations of these structures (including Boost Geometry, PCL, and Nanoflann) across six real-world geographic datasets. Our results demonstrate that Indexicon's lightweight design matches or outperforms existing state-of-the-art implementations while offering unmatched architectural flexibility. To foster reproducible spatial research, we open-source the complete library alongside our datasets and query workloads.

Authors: Shakiba Khourashahi, Ilia Jahanshahi, Bei Wang, Lin Yan

As data becomes increasingly central across engineering and scientific disciplines, effective visualization is essential for interpreting complex, high-dimensional structures. Dimensionality reduction techniques project high-dimensional data into lower dimensions while aiming to preserve structural properties such as pairwise distances and local neighborhoods. In this paper, we focus on improving homological preservation, that is, the retention of topological features such as connected components and loops, which is critical for maintaining global shape and continuity. We first introduce AdaMapper, a Mapper-based algorithm that leverages persistence diagrams to guide both skeleton construction and landmark selection. AdaMapper incorporates an adaptive refinement strategy that automatically increases cover resolution in regions exhibiting topological loops. We then propose AdaHIsomap, which extends landmark Isomap by incorporating homology-informed landmark selection and augmenting it with random anchor points to better balance distance and homology preservation. We evaluate both methods on a diverse set of datasets, including high-dimensional point clouds, scientific simulations, networks, and image data, and benchmark their performance against state-of-the-art approaches.

Authors: Anda Skeja, Daniel Gutiérrez Espinoza, Fiona Skerman, Alexander S. Wein

We establish the first sharp thresholds for low-degree polynomial tests in planted-vs-planted settings, where the goal is to determine with vanishing error which of two structured planted mechanisms generated the observed data. We prove matching low-degree upper and lower bounds for counting communities in the planted submatrix and planted dense subgraph models. The resulting testing threshold coincides, down to the sharp constant, with the known low-degree recovery threshold. In contrast, the task of weak testing, where the goal is to outperform random guessing, does not have a sharp threshold but rather a smooth transition, which we identify. To prove our results, we develop a framework for planted-vs-planted testing that builds on a latent-variable expansion originating in low-degree recovery and employs new methods to identify and prune non-signal contributions.

Authors: Tim A. Hartmann, Dániel Marx

The distance-d variants of Independent Set and Dominating Set problems have been extensively studied from different algorithmic viewpoints. In particular, the complexity of these problems are well understood on bounded-treewidth graphs [Katsikarelis, Lampis, and Paschos, Discret. Appl. Math 2022][Borradaile and Le, IPEC 2016]: given a tree decomposition of width t, the two problems can be solved in time $d^t \cdot n^{O(1)}$ and $(2d + 1)t \cdot n^{O(1)}$, respectively. Furthermore, assuming the Strong Exponential-Time Hypothesis (SETH), the base constants are best possible in these running times: they cannot be improved to $d-ε$ and $2d+1-ε$, respectively, for any $ε > 0$. We investigate continuous versions of these problems in a setting introduced by Megiddo and Tamir [SICOMP 1983], where every edge is modeled by a unit-length interval of points. In the δ-Dispersion problem, the task is to find a maximum number of points (possibly inside edges) that are pairwise at distance at least δ from each other. Similarly, in the δ-Covering problem, the task is to find a minimum number of points (possibly inside edges) such that every point of the graph (including those inside edges) is at distance at most δ from the selected point set. We provide a comprehensive understanding of these two problems on bounded-treewidth graphs.

Authors: Andrei Graur, Aaron Sidford, Ta-Wei Tu

We provide faster deterministic and randomized algorithms for exactly solving discounted Markov Decision Processes (DMDPs). We obtain our results by efficiently reducing computing optimal values and policies in DMDPs to the easier tasks of policy evaluation and computing approximately optimal values in DMDPs. We provide both a straightforward deterministic reduction and a more efficient randomized variant that, together with advances in approximately solving DMDPs, yield our results.

Authors: Deniz Elbek, Kamer Kaya

Modern GPUs have Tensor Cores (TCs) capable of extremely high-throughput matrix operations, yet graph algorithms remain difficult to accelerate because of their irregular and data-dependent execution patterns. This work presents BLEST, a TC-accelerated framework that reformulates Breadth-First Search (BFS) as a bit-level sparse matrix-vector computation while addressing the load imbalance, memory inefficiency, and synchronization overheads that limit prior approaches. BLEST introduces Binarized Virtual Slice Sets (BVSS), a graph representation that partitions work into balanced warp-level units and schedules only frontier-relevant regions of the graph. It further employs an optimized TC layout that maps neighbour checks onto binary MMA instructions without wasted outputs, reducing the number of required MMA calls by 8$\times$ compared with prior layouts. To mitigate atomic and cache bottlenecks, BLEST incorporates a lazy vertex-update scheme. We revisit the switching terminology for BFS and propose a mechanism that dynamically transitions from TCs to CUDA cores when it becomes more efficient. We also extend BLEST to multi-source BFS and closeness centrality workloads. Finally, we introduce a scalable graph reordering method that improves compression for scale-free-like graphs, while using RCM to improve locality for others. Across a broad set of real-world graphs, BLEST achieves average speedups of 22.0$\times$, 7.7$\times$, 8.1$\times$, and 5.9$\times$ over GAP, Gunrock, GSWITCH, and BerryBees, respectively, establishing a new BFS baseline on GPUs. Thanks to its high performance, BLEST can compute the exact closeness centralities of 65.6M vertices in a social network with 3.6B edges in an hour using 100 H100 GPUs.