Theory of Computing Report

Authors: Baocheng Sun, Thomas Vidick

The model of interactive oracle proofs (IOP) generalizes the notion of probabilistically checkable proof (PCP), in which a static proof is verified probabilistically by querying a small number of bits, to the interactive setting: a polynomial-time verifier interacts with an unbounded prover, but is restricted to only reading a small number of bits, in total, from the messages sent by the prover. IOPs provide a relaxed setting in which to study local probabilistic verification. They have proved instrumental in devising efficient methods for verification through subsequent compilation into non-interactive or succinct protocols. We study a quantum analogue of interactive oracle proofs (qIOP) in which the verifier and communication are both allowed to be quantum; yet the verifier is restricted to perform measurements only on a small number of qubits received from the prover. Our main result is a qIOP for any language in QMA, in which the total communication is polynomial but the verifier only reads a polylogarithmic number of qubits in total. The protocol has completeness parameter exponentially close to $1$ and soundness bounded away from $1$ by a constant. In the absence of a quantum PCP theorem, this provides the first information-theoretically sound local and robust characterization of QMA, albeit interactive. Our protocol combines the use of a quantum locally testable code (LTC) with classical techniques, notably probabilistically checkable proofs of proximity (PCPP). We avoid the necessity for complex multi-qubit tests employed in other settings by leveraging the local indistinguishability property of the quantum LTC.

Authors: Riley Brown, Istvan Miklos

We study the $t$-uniform hypergraphicality problem under a compressed representation of the degree sequence. Instead of listing all vertex degrees explicitly, the input consists of pairs $$ (δ_1,n_1),\dots,(δ_k,n_k), $$ meaning that exactly $n_i$ vertices have degree $δ_i$. Thus the parameter $k$ denotes the number of distinct degrees. Although deciding $t$-hypergraphicality is NP-complete for every fixed $t>2$, we prove that the problem is fixed-parameter tractable parameterized by $(k,t)$. Our result shows that tractability extends substantially beyond previously known bounded-range regimes: even degree sequences with large overall degree spread can be handled efficiently when the number of distinct degrees is bounded. Our approach decomposes hyperedges according to their types with respect to the degree classes, yielding a bounded-dimension spectrum representation. Using balancing hinge-flips, we show that every feasible spectrum can be transformed into a realization of the prescribed degree sequence. This leads to an integer programming feasibility formulation with $$ \binom{t+k-1}{k-1} $$ variables. Applying Lenstra's theorem yields an FPT algorithm running in time $$ f(k,t)\cdot \mathrm{poly}(L), $$ where $L$ denotes the encoding length of the compressed input.

Authors: Chaowen Guan, Akshit Katiyar

We present a quantum algorithm for the Kravchuk transform that scales logarithmically in both the dimension and the inverse of the error parameter. The quantum Kravchuk transform maps computational basis states to states with amplitudes proportional to Kravchuk functions. We achieve this by combining two key techniques: the structural relationship between the Kravchuk transform and the Lie algebras $\mathfrak{su}(2)$, and a recent fast-forwarding simulation method for $\mathfrak{su}(2)$ operators in the oscillator representation. More precisely, we first establish the map from Kravchuk transform in computational basis to $\mathfrak{su}(2)$ in Fock basis. Then built on this connection, we apply the fast-forwarding to achieve an efficient quantum Kravchuk transform.

Authors: Christian Ikenmeyer

We observe that the Kronecker product of tensors is the operation that converts the determinant polynomial into Cayley's first hyperdeterminant. We apply the Kronecker product to iterated matrix multiplication, which results in the hypercomputant, a VNP-complete and VW[1]-complete polynomial whose hardness we prove via the equivariance of the Kronecker product. The construction works over arbitrary commutative semirings and also for the tensor algebra and the exterior algebra. For the tensor algebra this gives a version of "noncommutative VNP", and for polynomials over the nonnegative real numbers this gives a version of "monotone VNP", each with the hypercomputant as the complete object. We take a parameterized complexity viewpoint and compare the noncommutative setting and the monotone setting. Using standard techniques we obtain optimal algebraic branching program width lower bounds in both settings, and these are notably not always the same. We also prove the polystability of the hypercomputant and that its isotypic components are characterized by their stabilizer.

Authors: Ruy Fabila-Monroy, Benedikt Hahn, Jesús Leaños

Order types are an equivalence relation between point configurations that capture their combinatorial and convexity properties. Let $P$ be a $κ$-colored sequence of $n \ge d+1$ points in general position in $\mathbb{R}^d$. Let $ρ$ be a $κ$-colored order type on $k \le d+1$ points that has positive density on $P$; that is, for some constant $δ>0$, there are $δ\cdot \binom{n}{k}$ $k$-point subsequences of $P$ that have the same order type as $ρ$ and the same color pattern. In this paper we show that there exists a constant $c >0$ (depending only on $d, δ$, $k$ and $κ$) and disjoint subsets $X_1,\dots,X_k$ of $P$, each with at least $c \cdot n$ points, such that for every choice of $k$ points $x_i \in X_i$, $(x_1,\dots,x_k)$ has the same order type and color pattern as $ρ$.

Authors: Maria Constantin, Adrian Miclăuş, Alexandru Popa, Andrei Popa

Given a finite set of integers $A$, a \emph{unary translocation} produces a new set $A' = A \cup \{u,v\}$, where $u$ and $v$ are nonnegative integers satisfying $x+y=u+v$ for some $x,y\in A$. For an input set $A$ and a target set $B$, the \emph{unary translocation distance} is the minimum number of unary translocations required to obtain a superset containing $B$. In this paper, we study this problem from both theoretical and computational perspectives. We prove that computing the unary translocation distance is strongly NP-hard, thereby answering an open question raised by \citet{ConstantinMiclausPopa2026UnaryTranslocation}. On the positive side, we give an exact pseudo-polynomial algorithm for every fixed constant value of $|B|$, extending our previous results for $|B|\leq 2$. For arbitrary target sets, we present a $2$-approximation algorithm, an additive $(|B|-1)$-approximation algorithm, and show that the additive algorithm also yields a $3$-approximation. We also propose parameterized algorithms, including algorithms parameterized by the maximum value in the input set together with the optimum distance, and by the maximum value in the target set together with $|B|$. In addition, we propose an integer linear programming formulation that gives an exact mathematical model for the problem, analyze its size, and show that the LP relaxation has integrality gap at least $\frac{4}{3}$. Finally, we report computational experiments comparing the $2$-approximation algorithm, beam search, and simulated annealing. The results show that the approximation algorithm is highly effective in practice and often outperforms the heuristic baselines.

Authors: László Kozma

The $k$-center problem is one of the best-studied and most intuitive clustering formulations. It asks, given a set of $n$ points in a metric space, for $k$ of the points to be designated as cluster centers, so that the maximum distance of an input point to its nearest center is minimized. Gonzalez's greedy algorithm from 1985 is a simple and efficient way to find a $2$-approximate solution. The algorithm has the attractive feature of \emph{incrementality}: it outputs the centers one by one, with a guaranteed $2$-approximation for every prefix of the obtained sequence of centers. Incrementality imposes a geometric constraint on how solutions can be built, and it is natural to ask whether this comes at a price in the quality of the solution. It is known that in polynomial time, the approximation ratio of $2$ is best possible, assuming $P \neq NP$. In this paper we show that even with \emph{unlimited} computational power, the factor $2$ cannot be improved, if the solution is required to be built incrementally. The lower bound construction imposes a tradeoff between all $n$ levels of the clustering simultaneously; it was obtained with the help of ChatGPT, an aspect we discuss in Section 3 of the paper.

Authors: Anupam Gupta, Benjamin Moseley, Rudy Zhou

We introduce a stochastic probing problem with correlated items. In our model, which we call Bayesian Probing, the correlations are modeled by an underlying graph $G$. Each vertex is independently active with a known probability. Each item corresponds to an edge in the graph. Probing an edge has some cost, gives some reward if both endpoints are active, and also reveals the state of its endpoints. Hence a probe induces a Bayesian update on the remaining edges. The goal is to adaptively probe items/edges subject to a knapsack constraint to maximize the expected total reward obtained from the probed edges. Bayesian Probing generalizes stochastic knapsack and stochastic probing by allowing correlations between items. Moreover, it gives a tractable model for the Bayesian Active Search problem, a popular problem considered in the machine learning community. In Bayesian Active Search, the goal is to find items in a particular class by adaptively probing at most, say $k$, items. Given a prior distribution over items, we want to compute a Bayesian policy to maximize the number of such items found. For this general problem with arbitrary priors, there are strong lower bounds on efficiently computing good policies. In this paper, we design efficient approximation algorithms for Bayesian Probing. These results give the first efficient approximation algorithms for Bayesian Active Search, for a class of practically-relevant prior distributions.

Authors: Arpon Basu, Joshua Brakensiek, Pravesh K. Kothari, Aaron Putterman

In this paper, we continue a line of research initiated by Basu, Brakensiek, and Putterman [2026] studying the sparsifiability of Hamiltonians. We focus particularly on the sparsifiability of the widely-studied Quantum Cut (QC) Hamiltonians. Our main result is that in an $n$-qubit system, any $n$-qubit QC Hamiltonian can be sparsified to $\widetilde{O}(n /\varepsilon^2)$ many terms while preserving the energy of every state up to a factor of $1 \pm \varepsilon$. Our result can be interpreted as giving an importance sampling scheme for the edges of an arbitrary graph $G$ such that the \emph{Kikuchi} graph at level $\ell$ of the sampled graph is a spectral approximation to the Kikuchi graph of $G$. Importantly, the \emph{same} sampling scheme works simultaneously for all $\ell$. The natural approach of leverage score sampling, analyzed via matrix concentration inequalities, yields a polynomially worse bound in our setting because the underlying matrices have dimension $\sim 2^n$. Instead, our approach relies on decomposing the action of these matrices into invariant subspaces. Then, by using an operator-valued inequality of Alon and Kozma [Ann. Henri Poincaré, 2020], itself building on an \emph{octopus inequality} of Caputo, Liggett, and Richthammer [J. AMS, 2010], we extend our sparsification technique to all expander graphs. We then invoke expander decomposition to extend our sparsifier to all graphs.

Authors: Peter Sanders, Matthias Schimek, Tim Niklas Uhl, Thomas Weidmann

The list ranking problem is one of the classical problems of parallel computing, with nontrivial algorithms and many applications as a subroutine for solving other problems. While it has been intensively studied in the early days of parallel computing, few things happened in the last 20 years. In particular, there is little work on scaling list ranking to large machines and input sizes. We reconsider list ranking starting from the ground-breaking results of Sibeyn a quarter century ago. We employ algorithm and performance engineering to improve his sparse ruling-set algorithm, making it capable of scaling to many processors, and provide a more detailed analysis of the impact of the algorithm's parameters, further guiding our practical implementation. We perform an extensive experimental study across a variety of input instances with different structural properties. We demonstrate that indirect communication, exploiting input locality, and message coalescing allows scaling to billions of elements on up to 24,576 cores.

Authors: Amir Tonta, Bernhard Seeger, Eljas Soisalon-Soininen

Multiversion concurrency control (MVCC) enables scans to read data from a committed snapshot (version), reducing conflicts with write operations compared to traditional concurrency approaches. Currently, versioned records are often managed in a B$^+$-tree using version chains. However, version chains introduce overhead during scans and can still lead to conflicts between scans and writers. The multiversion B-tree (MVBT) was designed for optimal range scan performance on arbitrary versions, but has been considered impractical due to its structural complexity and, until recently, the lack of effective concurrency control. In this paper, we present the concurrent MVBT (cMVBT), a redesign of the MVBT featuring a novel concurrency control protocol that uses optimistic latches for write operations and requires no latches for range scans, while preserving all the optimality guarantees of the original MVBT. Additionally, cMVBT supports continuous garbage collection without activity spikes, seamlessly integrating free-space management. Experiments with mixed workloads derived from a standard benchmark show that the cMVBT achieves low overhead, high write throughput, and excellent range scan performance, outperforming state-of-the-art methods based on version chains.

Authors: Vladimir Braverman, Chen Wang, Liudeng Wang, Samson Zhou

Motivated by the recency effect in online learning, we study algorithms for single-pass *sliding-window streaming multi-armed bandits (MABs)* in this paper. In this setting, we are given $n$ arms with unknown sub-Gaussian reward distributions and a parameter $W$. The arms arrive in a single-pass stream, and only the most recent $W$ arms are considered valid. The algorithm is required to perform pure exploration and regret minimization with limited memory, defined as the number of stored arms. The model is a natural extension of the streaming multi-armed bandits model (without the sliding window) that has been extensively studied in recent years. We provide a comprehensive analysis of both the pure exploration and regret minimization problems with the model. For pure exploration, we prove that finding the best arm is hard with sublinear memory while finding an approximate best arm admits an efficient algorithm. For regret minimization, we explore a new notion of regret and give sharp memory-regret trade-offs for any single-pass algorithm. We complement our theoretical results with experiments, demonstrating the trade-offs between sample, regret, and memory.

Authors: Yushan Li

We formulate the quotient admission problem for finite graph-window rows. The input is a finite row set, an admissible evidence map, semantic labels, witness-support hypergraphs, and atom-level admissibility predicates. The output is a quotient decision on evidence atoms, with possible decisions certificate, residual, low-confidence, or blocked. The problem asks for the maximal guard-respecting atom-level decision map that uses no refinement beyond the admissible evidence partition. We prove an atom-union characterization of identifiable classes, give a witness-support hypergraph guard for certificate admission, characterize projected-label conflicts as blocked atoms, and present quotient admission algorithms with correctness, maximality, and complexity guarantees. With explicit evidence vectors and hyperedges, the algorithms run in expected O(B + I + n) time and space by hashing and deterministic O(B + I + n log n) time by sorting under a key-linear comparison model, where n is the number of rows, B is the total evidence encoding length, and I is the total hyperedge incidence size. We also prove a magnitude-only indistinguishability lower bound: any evaluator that observes only residual magnitudes fails on instances whose evidence atoms require different residual decisions after the magnitudes collapse them.

Authors: Giulio Malavolta, Alon Rosen

Motivated by polynomial identity testing with exponentials (Li and Wu, ITCS'26), we study uncertainty principles for the number-theoretic transform (NTT). We show that the NTT satisfies strong sparsity tradeoffs: For every fixed prime $q$ and for all but finitely many primes $p \equiv 1 \pmod q$ every nonzero $f\in \mathbb F_p^{\mathbb Z_q}$ and its number-theoretic transform $\hat f$ satisfy \[ |\mathrm{Supp}(f)| + |\mathrm{Supp}(\hat f)| \ge q+1. \] Thus, a $k$-sparse function has transform support at least $q-k+1$. As our main technical contribution, we prove a probabilistic version of the above uncertainty principle, averaged over primes $p$, in the regime $p=q^{O(1)}$. As an application, we obtain a black-box identity test for $k$-sparse exponential polynomials of degree at most $d$ with vanishing soundness error, for $q$ moderately larger than $k$.

Authors: Andreas Björklund

A multivariate polynomial on $n$ variables $x_1,\ldots,x_n$ of total degree $n$ over $\mathbf{Z}_2$ containing the multilinear monomial $\prod_{i=1}^n x_i$ is by the combinatorial nullstellensatz [Alon, Comb. Probab. Comput., 1999] known to always have a nonroot. We show that there cannot be a randomised polynomial time algorithm that given an arithmetic circuit of polynomial size formally computing such a polynomial, locates a nonroot with constant nonzero probability unless RP=NP. The result holds even when the individual degree of every variable in the input polynomial is at most two.

Authors: Pravesh K. Kothari

We prove that level-$\ell$ Kikuchi graphs of random $2r$-uniform hypergraphs spectrally approximate the Kikuchi graph of the complete $2r$-uniform hypergraph at a sampling rate that is sharp up to a logarithmic factor, in the regime $r\leq \ell \leq n/2$. Our proof is based on the matrix Bernstein inequality, but, unlike prior works, we apply it to an appropriate collection of blocks of Johnson eigenspaces. Our analysis relies on a new, simple band-locality property for arbitrary Kikuchi graphs. As an application, we prove that the natural degree-$2\ell$ sum-of-squares relaxation for the Max $2r$-XOR problem is ``integral'' when the input is a planted noisy $2r$-XOR instance on a random hypergraph with $\gtrsim n \cdot (n/\ell)^{r-1} \log n$ hyperedges.

Authors: Michalis Xefteris

In this work, we study Restricted Assignment scheduling on multiple machines, where each job can be processed only on a specified subset of machines and the objective is to minimize the makespan. We introduce a learning-augmented setting in which a possibly infeasible predicted assignment is provided. The prediction error (moved-load) is measured by the total processing volume that must be reassigned in order to obtain an optimal feasible schedule. Using a single prediction, we obtain two types of guarantees. First, we design an algorithm whose approximation ratio degrades smoothly with the prediction error while retaining a worst-case guarantee independent of the prediction quality. More precisely, for any fixed constant, we can make the additive dependence on the prediction error arbitrarily small, at the cost of increasing the polynomial running time. This guarantee can also be combined with any approximation algorithm for the problem without predictions to obtain robustness. Second, given a makespan estimate, we provide a repair procedure that returns a schedule matching this estimate in time parameterized by the prediction error. This allows the algorithm to exploit the separation between estimation and approximation algorithms for Restricted Assignment. Finally, we complement the repair algorithm with a parameterized hardness result, showing that exact moved-load repair with a given target makespan is W[1]-hard when parameterized by the amount of moved-load.

Authors: Ramiro N. Deo-Campo Vuong

Equitable allocation of indivisible goods to agents in online settings is an algorithmic primitive with applications for load balancing, network routing, online marketplaces, and multi-agent systems. We consider a general setting in which allocations are constrained to be bases of discrete polymatroids that arrive online. Our work demonstrates that a simple, myopic algorithm called Brick-Laying, which greedily minimizes the sum of squared loads on agents, achieves a universal and objective-free notion of optimality called majorization minimax-optimality [BDK26] for this setting. As a consequence, Brick-Laying simultaneously guarantees minimax optimal competitive ratios and regret for all Schur-concave and Schur-convex objectives, and for any number of agents and resources (despite being agnostic to problem scale). Departing from popular primal-dual analysis, we employ majorization to compare allocations. We leverage the conjugates of integer partitions -- which act as a discrete dual to majorization -- to characterize worst-case instances for the Brick-Laying algorithm. Our approach reveals a novel structural connection between the geometry of partitions and online equitable allocation.

Authors: Meng Li, Xiaohua Yang, Jie Liu, Shiyu Yan

This paper asks when MR-subset selection is a real mutant-level requirement for minimum complete evidence in metamorphic testing rather than a coarse fault-class counting artifact. We define a layer-relative completeness criterion over an admitted mutant--draw coverage universe. The central result is a support-set domination boundary: it states when class-level abstraction is safe and when mutant-level MR minimization is necessary. The boundary is governed by kill-signature heterogeneity, which yields a scoped fault-signature kernel and separates the MR-specific question from ordinary fault-class counting. The resulting Min-MR-Complete problem is Set-Cover-equivalent over the selected coverage universe, giving NP-hardness, the classical logarithmic approximation boundary, a greedy approximation, an exact ILP formulation, and an SMS-rank upper bound that is not a lower bound or tight predictor. Artifact lanes provide lane-local minimization and audit evidence; separately, route witnesses instantiate both collapse and non-collapse regimes for the boundary theorem and are not pooled as population-level experiments. Other MR-class-proxy rows remain intermediate signals rather than route-admitted witness evidence.

Authors: Ben Bals, Joakim Blikstad, Daniel Dadush, Yasamin Nazari, Jonas Schmidt

The reachability diameter ($\mathrm{ReachDiam}$) of a directed graph is the maximum distance over all pairs $u,v$ where $v$ is reachable from $u$. This notion is present in the definition of shortcut sets, and the name was recently coined in that context by Haeupler, Jiang, and Saranurak [SOSA 2026]. While this is a very natural notion of diameter in directed graphs, and especially DAGs, it is so far not computationally explored. Other definitions of diameter in directed graphs are either trivial (infinite) in graphs that are not strongly connected (e.g., the classical definition) or are non-trivial only in highly restrictive graph classes (e.g., Min-Diameter). We initiate the problem of computing the (approximate) reachability diameter from a fine-grained complexity point of view. Under certain fine-grained assumptions, we prove that there is no algorithm in time $\mathcal{O}(n^{ω- \varepsilon}$) that gives any approximation of $\mathrm{ReachDiam}$ in weighted graphs. Similarly, there is no algorithm with better than $2$-approximation for unweighted graphs in this time. To supplement this, we provide algorithmic upper bounds that lead to additive approximation of $\mathrm{ReachDiam}$ for unweighted graphs. Hence, we establish a strong separation between the weighted and unweighted cases, which makes this type of diameter different in nature than other known notions. Considering the hardness in general weighted graphs, we also study special graph classes and get small constant approximations for DAGs with bounded width or graphs with bounded treewidth. Interestingly, our techniques also lead to exact hopsets with hopbound $2$ for bounded treewidth graphs. This and some of our upper bounds for general graphs show technical connections between approximating $\mathrm{ReachDiam}$ and computing shortcut sets and hopsets.

Authors: Xian Chen, Ruobing Bai, Pan Peng

Subgraph counting is a fundamental problem in graph analysis. Motivated by practical scenarios where graph analytics are performed on subgraphs induced by selected vertices -- rather than on the entire graph -- and by growing privacy concerns, we initiate the study of differentially private range subgraph counting (DPRSC). The goal is to privately count occurrences of a fixed pattern graph within induced subgraphs defined by multi-dimensional attribute ranges. Unlike classical point counting, subgraph counting is inherently nonlinear and exhibits high sensitivity: a single edge modification can affect many subgraph occurrences. We present the first efficient algorithms for DPRSC with small additive error. Our approach introduces a subgraph projection that reduces DPRSC to weighted orthogonal range counting, enabling the use of range trees and local sensitivity estimation to achieve accurate private query answering. We complement our algorithms with matching lower bounds, obtained by reducing reconstruction attacks to DPRSC and leveraging discrepancy theory. In particular, we show that any differentially private algorithm for DPRSC must incur additive error exponential in the dimension. Empirical evaluations demonstrate that our algorithms significantly outperform baseline methods in accuracy and runtime while maintaining strong privacy guarantees.

Authors: Ira Pohl, Larry Stockmeyer

We introduce two infinite families of 3-regular planar graphs. Both families are conceptual adversaries to the Pohl-Warnsdorf algorithm for finding Hamiltonians. We provide a closed form calculation of the number of Hamiltonians.

Authors: David G. Harris

We describe new dependent-rounding algorithms for bipartite graphs. Given a fractional matching $x$ of graph $G = (U \cup V, E)$, the algorithms return an integral solution $X$ such that each right-node $v \in V$ has at most one edge, and where the variables $X_e$ also satisfy broad non-positive correlation properties. In particular, for any edges $e_1, e_2$ sharing a left-node $u \in U$, the variables $X_{e_1}, X_{e_2}$ have \emph{strong} negative-correlation, i.e. the expectation of $X_{e_1} X_{e_2}$ is significantly below $x_{e_1} x_{e_2}$. Dependent rounding schemes with these properties have been used for a approximation algorithms for job-scheduling on unrelated machines to minimize weighted completion times, among other applications. Our new algorithm achieves simpler and qualitatively stronger bounds compared to prior algorithms. In particular, we achieve a negative-correlation property $$ \E[X_{e_1} X_{e_2}] \leq 0.79751 \ x_{e_1} x_{e_2}, $$ which is a significant constant-factor improvement over Baveja, Qu & Srinivasan (2023).

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.