Theory of Computing Report

In the noisy chaos of science-based wellness on social media, there are a few reasonable voices. One of my favorites1 is Greg Nuckols, a champion powerlifter who has been blogging about the science of strength training for well over a decade. Over the weekend, I read his 2015 books The Art of Lifting and The Science of Lifting, and they hammer home how a simple topic can be made overly complicated when we decide to write scientific papers about it.

Nuckols’ two-volume series is less than two hundred pages long and written in an engaging, bloggy voice. Though the books link out to systematic reviews and randomized trial reports, he doesn’t get bogged down in that material. Instead, he focuses on one simple modeling principle and its consequences: adaptation.

Though the human body is impossibly complex, its many interconnected systems deal with stressors in a surprisingly uniform way. Stressor here means all sorts of things: wounds, infections, temperature changes, environmental changes, activity changes. Something out of the ordinary. The model of homeostasis posits that bodies actively work to stay the same as much as possible. Most of our daily activities don’t stress the body, and we remain in a pleasant, steady state. However, the body changes and adapts if it gets pushed far enough out of its comfort zone. If you apply enough stress, the body initiates a response to prevent harm or death. There are limits to this response, and too much stress will cause injury or death. But in the right Goldilocks range, the body will reconfigure itself to resist the stress next time it sees it.

Exercise can be modeled as a stressor. It’s certainly stressful. It increases muscle tension and body temperature. It increases demand for oxygen and nutrients. It lights up your sympathetic nervous system and triggers the release of adrenaline. Your body responds to exercise similarly to how it fights off other stressors like injuries and infections. It panics and then marshals resources to make sure it sucks less the next time you go to the gym.

There are many models for the temporal behavior of the stress reaction. The most common mathematical model is the fitness fatigue model developed by Tom Calvert, Eric Banister, and collaborators in the 1970s. Notably, Calvert was an electrical engineer who introduced his physiology colleagues to cybernetics and impulse responses. The fitness-fatigue model is a parametric model of adaptation: stressors introduce bad effects (fatigue) from which the body works hard to recover quickly. It also introduces positive training effects, the adaptations you were chasing. The fitness-fatigue model posits that the positive effects decay more slowly than the negative ones. For the dynamical systems nerds out there: they model this with a simple second-order linear system. Hence, if you repeat this process of enough but not too much stress over time, you nudge your body to handle more and more stress.

This feels science-y, no? The general adaptation syndrome is a well-tested, clean model that certainly helps guide how to train athletes and implement physical therapy. This model hasn’t changed since 1980. It prescribes working hard and continuing to do so over time to increase adaptation. It predicts that training harder than last time is beneficial. These two together form the principle of progressive overload, a very simple concept that influencers try to make absurdly complicated. Moreover, this model of adaptation tells you that you need to recover to hasten the elimination of fatigue. It even suggests implementing tapering periods before competition, a common practice.

OK great, now let’s try to apply this model to practice. What is the right shape of the actual stress to give you the results you want? If you want to get stronger, which exercises should you do? How frequently should you do them? What weights should you use? How many repetitions should you do for each exercise?

Unlike most of the charlatans in the science-based fitness space, Nuckols is brutally honest about this: the answer to all of these questions is that we don’t really know. Or at least, we at best only have partial answers. You probably need to go above some nominal effort to induce adaptation. Because there is so much intersubject variability, the exact perfect amount is hard to pin down. But if you work hard and make sure to rest and eat, you’ll get stronger over time.

Nuckols thinks the broader scientific research on sports training tells us more than I think it does. From my reading of too many studies in this space, the ns are always really small, the data are always poor, and the assessments are always ill defined. Do we need thousands of studies to tell us that we should “keep it simple, stupid?” People obviously can go to the gym and get stronger.

But what’s interesting to me about how Nuckols writes is that he doesn’t consider “science” to be some combination of biomolecular pathways and randomized trials. Instead, his scientific view is one of simple predictive models and their limitations. For an athlete like Nuckols, the scientific view helps systematize what matters in training. Working hard matters. Working harder over time matters. But resting and recovery are also critical to good performance. The right balance might not be easy to quantify, but the qualitative arc and predictions based on principles of adaptation are helpful. The general adaptation model for training tells us that training isn’t that complicated if you think carefully about what you are going to measure, and how you are going to track progress. This cybernetic view of biomedical science—one closer to what I would call engineering—feels like a promising path for many other aspects of medicine.

Subscribe now

By Ben Recht

Authors: Omar Al-Ghattas, David Gamarnik

A central question in quantum information theory is the circuit complexity of states arising from standard many-body models. We study this question for quantum $p$-spin glasses, random Hamiltonians whose interactions act on $p$-tuples of qubits through Pauli strings. Anschuetz, Gamarnik, and Kiani (arXiv:2404.07231) showed that the optimum energy is separated from the best energy achievable by product states. This leaves open whether shallow circuits can close the gap, since even depth-one circuits can generate entanglement. We show that the entanglement needed to close the product-state gap cannot be generated at shallow depth. When the average interaction degree grows with $n$, we prove that, for all sufficiently large fixed $p$, any circuit preparing an $n$-qubit state whose normalized energy is within a fixed positive constant of the optimum must have depth $Ω_p(\log n)$. In the bounded-average-degree regime, we prove a fixed-depth obstruction: for every fixed $D$, a sufficiently large degree prefactor rules out depth-$D$ preparation of near-ground states. Both results hold uniformly over circuits with an arbitrary number of ancilla qubits. Our results give an obstruction in the spirit of the No Low-Energy Trivial States problem of Freedman and Hastings (arXiv:1301.1363), but for random quantum spin glasses rather than code-based Hamiltonians such as those of Anshu, Breuckmann, and Nirkhe (arXiv:2206.13228), whose ground states admit polynomial-size preparation circuits. This setting opens a probabilistic route to NLTS-like questions: we recast state-preparation lower bounds for random quantum Hamiltonians as uniform control of Gaussian processes indexed by shallow circuits.

Authors: Mojtaba Soltanalian

We study exact verification of ReLU networks in an adversarial smoothed model. Every network weight and bias is independently perturbed by Gaussian noise, clipped to $[-2,2]$, and rounded to the exact dyadic grid determined by the input bit complexity. We show that, under the standard assumption $\mathrm{NP}\not\subseteq\mathrm{BPP}$, there is no sound and complete verifier whose expected running time is polynomial in network size, bit complexity, and inverse noise level for every base instance. The conclusion already holds at the fixed noise level $σ_\star=2^{-11}$ for one-hidden-layer networks over a unit box, with hidden fan-in at most three and base coefficients in $[-1,1]$. The proof combines an exact gap embedding with a quantitative robustness argument. For every E3SAT formula $Φ$ with $m$ clauses, a four-ReLU-per-clause construction satisfies $\max_{x\in[0,1]^n} g_Φ(x)=(m-\operatorname{unsat}(Φ))/3$, and coordinatewise threshold rounding never decreases the objective. A weighted parameter-sensitivity inequality and Gaussian concentration then show that a verification gap linear in $m$ survives the aggregate perturbation of all coefficients with probability at least $1-e^{-m/8}$. The proof includes clipping, exact dyadic rounding, output-layer perturbations, polynomial-bit sampling of the rounded Gaussian law, and the conversion from expected smoothed running time to a BPP algorithm. Computational checks test the exact identity and illustrate the different scaling of extensive and constant gaps; they are diagnostics rather than evidence for the complexity theorem. The result concerns worst-case base networks in the stated absolute-noise model, but it shows that parameter nondegeneracy alone does not yield a universal smoothed-polynomial guarantee for exact verification.

Authors: Ethan Dickey, Alexandros Psomas, Athina Terzoglou

Stable Voting and Simple Stable Voting, introduced by Holliday and Pacuit, are Condorcet-consistent voting rules defined recursively: a candidate wins if they would win after removing some opponent they beat, taking the pair with the largest margin first. The computational complexity of winner determination under these rules has been an open question. We resolve this problem: winner determination is PSPACE-complete under both Stable Voting and Simple Stable Voting.

Authors: Marcel K. Goh, Hamed Hatami

It is conjectured that every idempotent Schur multiplier can be written as a finite sum of contractive idempotents. This conjecture is equivalent to the statement that any boolean matrix $A$ with factorization norm $\lVert A\rVert_{γ_2}$ at most $γ$ can be expressed as a signed sum $$A = \sum_{i=1}^L \pm B_i,$$ where, up to permutation of rows and columns, each $B_i$ is a blow-up of an identity matrix, and $L$ depends only on $γ$. In this note we show that if $A$ is an $n\times n$ boolean matrix with $\lVert A\rVert_{γ_2} \le γ$, then it admits such an expression with $L = 2^{O(γ^9) + \log^*\! n}$, where $\log^*$ is the iterated logarithm function. As an application, any sequence of matrices with bounded factorization norm belongs to the complexity class $\mathrm{P}^\mathrm{EQ}$ of communication problems with polylogarithmic equality-oracle complexity.

Authors: V. R. Saiprasad, V. Troude, D. Sornette

Across hydrodynamics, ecology, neuroscience, network dynamics, non-Hermitian physics, and socio-economic systems, asymptotically stable dynamics can exhibit large transient amplifications that are invisible to eigenvalue-based analyses. The mechanism is geometric rather than spectral: perturbations entering along one direction may be expressed transiently along another, allowing asymptotic decay to coexist with strong transient or noise-driven amplification. We introduce non-normal directional response inference, a data-driven method for detecting this geometry from multivariate time series when the governing operator is unknown. A local linear operator is estimated from sliding windows and projected onto the dominant two-dimensional input-response subspace. The reduced dynamics are summarized by the eigenvalue splitting $Δ$, eigenvector non-orthogonality $K$, and the scale-free ratio $R=K/K_c(Δ)$, where $K_c(Δ)$ is the two-dimensional threshold for transient amplification. Controlled benchmarks show that the reduced geometry, particularly $R$, can be recovered from finite data even when the full high-dimensional operator is poorly estimated. Tests across sample size, dimension, training horizon, spectral structure, and non-stationarity confirm that the relevant response geometry requires far fewer observations than full-matrix recovery. Applied in moving windows to electrohysterogram, seizure EEG, freezing-of-gait, and unstable push-up inertial recordings, the method reveals systematic changes around known physiological or behavioral episodes through shifts in $R$, changes in $Δ$, or stronger projection of fluctuations onto the inferred response direction. It thus exposes interpretable changes in local response geometry without framing the problem as supervised event detection.

Authors: Akshay Sasi

Machine-learning datasets labelled "4D" universally denote three spatial dimensions plus time. We introduce HyperShadow, the first public benchmark in which the fourth, fifth, and sixth dimensions are spatial: the task is to decide whether a 3D point cloud is a native three-dimensional shape or the projection, the "shadow", of a rigid object living in R^N (N = 4-6). We show this task is fundamentally distinct from intrinsic-dimension estimation: a shadow is still at-most-3-dimensional data, and standard estimators (TwoNN, Levina-Bickel MLE) reach only 71-73% accuracy. Detection instead requires projection signatures, density folds, filled volumes with characteristic radial profiles, and topology changes, which a 190k-parameter point network recovers at 96.6% accuracy across four corruption tiers, generalizing at 79-91% to object families never seen in training. On a temporal track of rigidly rotating objects we introduce a zero-parameter rigidity witness: the residual of the optimal rigid 3D alignment (Kabsch) between consecutive frames, which must vanish for any rigid 3D motion but cannot vanish for the shadow of a rigid rotation in R^N. This single interpretable statistic separates the classes at AUROC 0.982. All data are generated reproducibly from seeds; the dataset, models, and code are released publicly. HyperShadow makes no claim about physical reality; it is a controlled instrument for studying which observable statistics can certify incompatibility with a purely three-dimensional explanation.

Authors: Sepehr Assadi, Max Jiang, Mars Xiang

We prove that no single-pass semi-streaming algorithm (deterministic or randomized) can achieve a better-than-half approximation to the maximum matching problem. This implies the optimality of the naive greedy algorithm, answering an outstanding open question in the graph streaming literature since the introduction of the model over two decades ago. Our proof follows the "blueprint framework" introduced previously by the authors, which reduced proving lower bounds for semi-streaming matching to constructing certain combinatorial objects called blueprints. We present an optimal construction of blueprints that when used in this framework implies our semi-streaming matching lower bound. Our results also imply that the optimal competitive ratio of online matching with preemption is half, again matching the naive greedy algorithm, settling this open question as well.

Authors: Sepehr Assadi, Max Jiang, Mars Xiang

In the semi-streaming model, we have an $n$-vertex graph $G=(V,E)$ whose edges arrive in an arbitrary order in a stream. The goal is to make one or a few passes over the stream, use a limited memory of $\tilde O(n)$ bits, and output a solution to the problem at hand at the end. A central open question in this area is to determine the best approximation ratio possible for the maximum matching problem via single-pass semi-streaming algorithms. This problem admits a simple $0.5$-approximation algorithm, by maintaining a maximal matching greedily, which, despite extensive efforts, has remained the state of the art. Lower bounds for this problem have also been few and far between with best known bounds ruling out better than $1/(1+\ln{(2)}) \sim 0.590$ approximation, using a highly complicated construction motivated by the literature on RS graphs from extremal graph theory. We develop a new framework for proving lower bounds for the semi-streaming matching problem. Our framework abstracts out the extremal graph theory and information theoretic arguments in the lower bounds, and reduces the problem to constructing certain constant-size graphs, which we call blueprints. Not only existing lower bounds can be captured by these blueprints, leading to far simpler and more concise arguments, but also we can design new blueprints that can be used to rule out $(8-2\sqrt{10})/3 \sim 0.558$-approximation for the semi-streaming matching problem. We believe this approach can be of its own independent interest and lead to further improvements on this tantalizing open question.

Authors: Thomas L. Draper, Feras A. Saad

We prove fundamental space lower bounds for exact random sampling using an entropy source of i.i.d. uniform bits. A classic result from information theory shows that generating $n$ discrete random variables $X_1, \dots, X_n$ requires at least $H(X_1, \dots, X_n)$ input random bits on average, where $H$ is the Shannon entropy function. How much space must a random sampling algorithm use in order to approach this information-theoretically optimal entropy bound? We prove that any random sampling algorithm that is exact for arbitrary discrete target distributions and consumes at most $H(X_1,\ldots,X_n)+\varepsilon n+o(n)$ input bits in expectation for every output process must use $Ω(\log(1/\varepsilon))$ bits of space. In fact, i.i.d. sampling from the single distribution $\mathrm{Bernoulli}(1/3)$ already forces at least $(1/{5.116201}-o(1))\log(1/\varepsilon)$ bits of space. If the sampler handles a family of infinitely many Bernoulli distributions, we show a sharper bound of at least $\log(1/\varepsilon)$ bits of space. We also prove lower bounds for general i.i.d. sampling: for almost every distribution on $k$ outcomes, the space is at least $(1/(k+1)-o(1))\log(1/\varepsilon)$ bits. The proof technique is based on a graph-theoretic analysis of the amount of information that any algorithm can store in its state. Finite state spaces force short cycles around the state-transition graph, and the loss around such cycles reduces to Diophantine lower bounds on fractional parts of integer combinations of log-probabilities. To the best of our knowledge, these results comprise the first known space lower bounds for entropy-efficient random sampling.

Authors: Prantar Ghosh, Sahil Kuchlous, Shravan Mehra, Sagnik Mukhopadhyay

What problems can one solve on a tournament if only its score sequence is known? Tournaments are oriented complete graphs that form an extensively-studied class of directed graphs (digraphs), both from combinatorial and algorithmic perspectives. Over the years, researchers have identified multiple classical digraph problems that can be solved on a tournament from only its score sequence (indegree sequence). These problems include acyclicity testing and topological sorting [Chakrabarti, Ghosh, McGregor, and Vorotnikova; SODA'20], $s,t$-reachability, strong connectivity, and decomposition into strongly connected components (SCC) [Ghosh and Kuchlous; ESA'24], and vertex-ordering problems such as cutwidth and optimal linear arrangement [Barbero, Paul, and Pilipczuk; ICALP'17]. These prior works showed the sufficiency of the score sequence by designing distinct algorithms for the individual problems. In this work, we give a simple unified framework that solves all these problems using only indegrees and, in fact, completely characterises the class of problems that is determined by the indegree information: problems whose answers are invariant under cycle reversals. This characterisation is a special case of a much more general result that we establish: for any arbitrary digraph, the knowledge of its skeleton (underlying undirected graph) and the vertex indegrees completely determines its properties that are invariant under cycle reversal. As a byproduct of our results, we obtain algorithms for a variety of connectivity-based, cut-based, and vertex-ordering problems on tournaments and ``almost tournaments'' in the streaming, the two-player communication, and the cut-query models of computation. Some of these algorithms match existing optimal bounds and others provide bounds improving the state of the art.

Authors: Julia Baligacs

In the online graph exploration problem, a single agent needs to visit every vertex of an initially unknown graph, which is learned over time in an online fashion, and return to its starting position. We prove that the competitive ratio of this problem is at least 4, improving on the previously best known lower bound of 10/3. A key ingredient of our proof is showing that several restrictions can be imposed on the agent's behavior without affecting the competitive ratio. As a byproduct, we also obtain that certain graph properties, such as the triangle inequality or being subcubic, can be assumed without affecting the competitive ratio.

Authors: Minbo Gao, Zhengfeng Ji, Chenghua Liu

Principal component analysis (PCA) is optimal for the linear reconstruction of Gaussian data, a foundational property underlying its central role in algorithms and signal processing. Its nonlinear analogue, however, is notoriously subtle: in 2011, Mallat and Zeitouni conjectured that the Karhunen--Loève (KL) basis remains optimal even when the retained coordinates are chosen adaptively per sample, a property that would theoretically justify the ubiquitous pipeline of PCA followed by sparse thresholding. In this paper, we establish a $1+O(1/\sqrt{d})$-approximate version of the retained-energy form of the Mallat--Zeitouni conjecture, showing that the KL basis is within this factor of the optimal basis. This dimension-free comparison depends only on the number of retained coordinates and shows that the possible advantage of optimizing over all orthonormal bases vanishes as $d$ grows. It complements the universal-constant reconstruction-error comparison of Litvak and Tikhomirov (Ann. Appl. Probab., 2018), while providing a comparison naturally suited for algorithmic analysis. Our proof rests on a clean, conceptual reduction: we relax arbitrary rotations to a deterministic threshold bound via Schur--Horn majorization, and identify the remaining loss with the correlation gap of the rank-$d$ uniform matroid over Gaussian level sets.

Authors: Itai Boneh, Paweł Gawrychowski

The LZ-End parsing of a length-$n$ string is a variation of Lempel-Ziv compression introduced by Kreft and Navarro [DCC 2010], motivated by the lack of a linear-size structure with $O(\log n)$ access time for the classical variant. While the original paper was only able to provide efficient extraction from the phrase boundaries, recently Kempa and Saha [SODA 2022] established that, for a string $S$ whose LZ-End parsing consists of $z$ phrases, there exists a random access data structure that uses $O(z)$ space and guarantees $O(\log^{4}n \cdot \log\log n)$ query time. However, their proof does not yield an efficient construction algorithm, and their data structure is inherently randomized. We resolve both limitations by providing a deterministic, $O(z)$-space data structure that supports random access queries in polylogarithmic time and can be constructed in $O(z\log^{2}(n/z))$ time directly from the LZ-End parsing. In addition to eliminating randomness and providing an efficient construction algorithm, the query time of our data structure is $O(\log^{2}(n/z))$, significantly improving upon the query time of Kempa and Saha. We also show that our techniques can be used to support the more general substring-extraction. Namely, we present a data structure with the same space and the same construction time that given two indices $i$ and $j$, outputs $S[i..j]$ in $O(j-i+\log^2\frac{n}{z})$ time.

Authors: Tomohiro Koana, Soh Kumabe

\textsc{$H$-Packing} asks whether a graph $G$ contains $k$ vertex-disjoint copies of a fixed pattern graph $H$. Via the standard reduction to \textsc{$d$-Set Packing}, one obtains generic kernels with $O(k^{|V(H)|-1})$ vertices and $O(k^{|V(H)|})$ edges. We revisit the question of beating these bounds for specific patterns $H$. Our main results concern subdivided stars. Let $S_{d_1,d_2}$ denote the subdivided star with $d_1$ branches of length $1$ and $d_2$ branches of length $2$. We obtain kernels with $O(k^2)$ vertices and $O(k^3)$ edges for $P_5=S_{0,2}$, for $S_{1,2}$, and for every $S_{d_1,1}$, kernels with $O(k^4)$ vertices and $O(k^6)$ edges for every fixed $S_{d_1,d_2}$ with $d_1\ge 1$, and a kernel with $O(k^2)$ vertices and $O(k^4)$ edges for the paw. Our proofs proceed in two steps. First, we reduce to instances in which all but a small part of the graph is independent, or in which the graph has a small vertex cover. Second, we reduce the independent side by keeping only a bounded number of witness vertices for each subset of the small part. On the negative side, we prove a lower bound for the line $S_{0,d}$. For every $d\ge 3$ and every $\varepsilon>0$, \textsc{$S_{0,d}$-Packing} does not admit a compression of size $O(k^{d-\varepsilon})$ unless $\NP\subseteq \coNP/\poly$. Thus, deleting a single vertex from the pattern may, surprisingly, make kernelization provably harder, showing that compressibility of \textsc{$H$-Packing} is not monotone under taking induced subgraphs.

Authors: Frank Bauernöppel, Jörg-Rüdiger Sack

Enumerating simple paths and cycles subject to a given length bound is a fundamental problem in graph algorithms with applications ranging from network analysis to computational biology. Recent algorithms for this problem, namely CYCLE_SEARCH (Gupta and Suzumura, 2021) and BC-DFS (Peng et al., 2019, 2021), employ barrier values to prune fruitless searches. Both algorithms have been shown incomplete and their delay-bound arguments rely on monotonicity claims that are flawed. For CYCLE_SEARCH this was shown previously. In this paper we establish the analogous results for BC-DFS by presenting new counter-examples and identifying a defect in its barrier-update procedure. As our main contribution, we introduce the concept of edge-consistency, a local invariant on barrier values analogous to heuristic consistency in informed search. Edge-consistency provides an incremental mechanism for maintaining admissible barrier estimates and yields concise correctness proofs. We use edge-consistency as a unifying framework for design and analysis of Bounded-Scope Depth-First Search (BS-DFS) -- a new $O(k(n+m))$ delay algorithm for enumerating simple paths or cycles of length at most $k$ in a directed graph -- and of several variants of it. We also use edge-consistency to pinpoint the precise failure mechanism of BC-DFS. Experimental results confirm that the omissions in BC-DFS are not isolated edge cases and occur with noticeable frequency on random graphs.

Authors: Aditya Anand, Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, Amatya Sharma, Ernest van Wijland

We give a new dual fitting algorithm which gives improved approximation ratios of $3+\ln 2 + ε (\approx 3.694)$ and $4.9+ε$ for $k$-Means in (high-dimensional) Euclidean and general metrics respectively, improving upon the previously known ratios of $4+ε$ [Charikar, Cohen-Addad, Gao, Grandoni, Lee, and van Wijland STOC'26] and $5+ε$ [Byrka, Guo, Hu, Li, Wan, Wang FOCS'26], resp. In particular, our result for Euclidean $k$-Means breaks the hardness barrier of $1+8/e\approx 3.94$ for Metric $k$-Means. Prior to our work, no such separation between general and Euclidean metrics was known for $k$-Median, $k$-Means, or Facility Location in terms of their approximability. Unlike prior dual fitting approaches for $k$-Means, our new dual fitting algorithm tightly accounts for dual payments while still facilitating an effective dual feasibility analysis. We introduce a new framework that uses spectral analysis for determining the approximation factor of our algorithm.

Authors: Shintaro Matsushita, Takayoshi Shoudai, Yusuke Suzuki

Unordered trees are useful for modeling hierarchical structures in which the order among siblings is irrelevant. To represent flexible structural patterns in such data, unordered term tree patterns with height-constrained variables provide a natural framework. In our previous work, we studied the pattern matching problem for rooted unordered term tree patterns with height-constrained variables under the restriction that the child port of each variable must correspond to a leaf of a binding tree. In this paper, we remove this restriction and generalize the binding model so that the child port may correspond to any non-root vertex of a binding tree. Under generalized bindings, we formulate the corresponding membership problem and present a polynomial-time pattern matching algorithm. We also implement the proposed algorithm and conduct computational experiments to evaluate its running time. The experimental results show that the proposed method achieves practical running times.

Authors: Pratyush Avi, Christopher Musco

Graph-based methods like HNSW, DiskANN, NSG, and others have become an increasingly popular choice for implementing approximate nearest neighbor search (ANNS) in Vector Databases (VecDBs). The success of these methods has motivated the study of how to best construct a search graph for a given dataset. To that end, \emph{navigability} has been identified as a desirable graph property which ensures good ANNS performance when combined with greedy search. However, for a dataset with $n$ vectors, the sparsest navigable graph requires $O(n\sqrt{n})$ edges in the worst-case, and we show empirically that, for typical billion node datasets, 100s of edges are needed per node. This leads to slow search and high memory requirements. Moreover, under standard complexity theoretical assumptions, it was recently established that constructing a sparse navigable graph requires $Ω(n^{2-ε})$ time, which is prohibitive for large datasets. We address these concerns by introducing a relaxed notation of navigability called ``$γ$-almost navigability'' for any $γ\in [0,1]$, with $γ= 1$ corresponding to full navigability. We prove that any dataset (under any distance) admits a $γ$-almost navigable graph with just $O\left(\frac{n}{1-γ}\right)$ edges, linear in the dataset size. We present a randomized algorithm for constructing such a graph in near-linear time. While we prove that $γ$-almost navigability sacrifices the worst-case search guarantees enjoyed by navigability, we show empirically that greedy beam search still performs well in such graphs when $γ< 1$. Indeed, we obtain improved recall-runtime tradeoffs on a variety of datasets compared to fully navigable graphs. Moreover, our graphs are more space efficient, with degree typically less than half that of a fully navigable graph for comparable performance.

Authors: Mingjun Liu, Weiping Shang

A set $S \subseteq V$ is called a {\em semitotal dominating set} of $G=(V,E)$ if every vertex in $V \setminus S$ is adjacent to at least one vertex in $S$, and every vertex in $S$ is within distance 2 of another vertex in $S$. The corresponding decision problem is NP-complete even for unit disk graphs. In this paper, we present a 5-factor approximation algorithm for the Minimum Semitotal Domination problem on unit disk graphs in the graph-based input model. The algorithm processes the layers of a Breadth-First-Search tree and constructs a maximal independent set whose vertices satisfy the semitotal condition. For a graph with $n$ vertices and $m$ edges, the algorithm runs in $O(n + m)$ time, and hence in $O(n^2)$ time in the worst case. This improves the previously known 5.75-approximation algorithm with $O(n^3)$ running time.

Authors: David P. Woodruff, Samson Zhou

Sketching and streaming algorithms are vital for handling massive datasets. While classical methods guarantee correctness on fixed inputs, they often fail with adaptive inputs, where future data depends on past algorithm outputs. This is common in settings such as optimization, databases, finance, and network monitoring. This monograph surveys recent advances in adversarial robustness, including techniques for insertion-only streams, connections to differential privacy, and cryptographic methods that achieve adversarial robustness. We also discuss fundamental limitations, especially for linear sketches and streams with insertions and deletions, where robustness often requires polynomial space or sketching dimension. Throughout, we explore core problems like adaptively answering queries for optimization problems, norm estimation, frequency moments, and heavy hitters, and highlight emerging tools and open challenges at the intersection of streaming, sketching, privacy, and adversarial robustness.

Authors: Yingqi Zhang

A uniformly random $m$-subset of $[n]=\{0,\ldots,n-1\}$ has entropy $\log_2\binom{n}{m}$. Standard without-replacement procedures often expose an additional ordering coordinate that is absent from the returned set. We show that Floyd's subset sampler admits an exact round-local factorization of this coordinate. In round $r$, let $S$ be an $(r-1)$-subset of $[j]$, let $T\sim\operatorname{Unif}([j+1])$, and let $S'$ be the result of Floyd's transition. If $D$ is the zero-based rank of the original draw $T$ in $S'$, then $(S,T)\leftrightarrow(S',D)$ is a bijection between $\binom{[j]}{r-1}\times[j+1]$ and $\binom{[j+1]}{r}\times[r]$. Consequently, $S'$ and $D$ are independent and uniform on their respective spaces. The digit $D$ can therefore be merged immediately into a residual uniform random state; an induction shows that the partial subset remains independent of that state after every round. For $k=\min(m,n-m)$, the sampling phase uses $O(k\log k)$ time and $O(k)$ auxiliary space with an order-statistic tree; explicitly materializing a complement incurs the unavoidable output cost. The combinatorial layer avoids binomial-coefficient arithmetic and recovers the complete $k!$ state-space factor exactly. We also give a finite counterexample showing that analogous immediate rank recycling in a partial Fisher-Yates array is invalid because the unselected suffix retains a correlated ordering. A 64-bit Rust implementation is checked by exhaustive state-space enumeration for all $n\leq 8$ and by an entropy-accounting trace for choosing $20{,}000$ of $30{,}000$ items. We make no claim of runtime superiority over existing subset samplers.

Authors: Dylan J. Altschuler, Konstantin Tikhomirov

The Beck--Fiala conjecture asserts that every matrix $A\in\{0,1\}^{n\times T}$ with at most $d$ nonzero entries in each column has discrepancy $O(\sqrt d)$. A major breakthrough result of Bansal and Jiang recently established the validity of the conjecture for $d \ge \log(T)^2$. The present article extends the validity of the classical \textit{offline} Beck--Fiala conjecture to $d \ge \log(T)^{1+o(1)}$; moreover, the main thrust of the result is that it is actually obtained by an efficient \textit{online} algorithm that minimizes prefix discrepancy. The result is also essentially optimal, since online prefix discrepancy is known to scale as $ω(\sqrt{d})$ for $d =o(\log T)$. As an immediate corollary, the open question of online vector balancing in the Spencer setting is also resolved. The algorithm is based on a compactly supported Metropolis fixed-point walk, constructed by combining ideas from several recent works on the online Komlós problem. The proof was generated in conversation with ChatGPT 5.6 Pro; the authors provided high-level guidance in several rounds of prompting, followed by manual checking and rewriting of the proof.

I’ve recently been rereading Steven Levy’s “Hackers” with my daughter. Levy describes how Brautigan’s 1967 poem “All watched over by machines of loving grace”  was inspiring to the California  “Hardware Hackers” of the 1970s and organizations such as Community Memory. 

In 2026, the phrase “all watched over by machines of loving grace” conjures an image of humanity cradled in the arms of a powerful and aligned (“humanity loving”) AI: an AI benevolent dictator. Indeed in his essay titled “machines of loving grace”, Dario Amodei suggests (while acknowledging deep uncertainty) that one form of the future economy might be organized around AI systems (aligned to human values) that determine how to “give out resources … to humans based on some secondary economy of what the AI systems think makes sense to reward in humans.” This seems to place the AIs as parents who control and take care of the material needs of their human children and decide how to reward or punish them. To me, such an “AI parent” looks rather close to a benevolent dictator.¹

Regardless of whether you think AI as a loving parent is a good or bad outcome, Brautigan and (more importantly) the California hackers had quite a different and more decentralized vision. In the 1960s, computers were large machines made by companies such as IBM. They were hated by many on the left and considered part of the military industrial complex. But there was a group who combined leftist politics (or at least an anti establishment attitude) with a love of technology, and believed that computers could become tools of decentralization and liberation. To do that, the giant expensive computers would need to give way to small and cheap machines. This is what the “hardware hackers” were about, and this is the movement that led to the Apple II and the personal computer revolution.

Today, like the IBM mainframes of the 60s,  AI systems are large and expensive, and are  increasingly being integrated in military applications. Once again, many people on the left (and recently on the right as well) have strong hate and fear of this technology. While some apprehension may be justified, by refusing to engage with AI and acknowledge its capabilities, these constituencies are making themselves less relevant to shaping AI’s progress. Also, while the U.S. is leading the frontier, we are falling behind on open weights AI, and closed models are facing increasing restrictions. All of these trends do not bode well for a more decentralized future.

Scaling laws tell us that the way to increase intelligence is through ever more resources—- compute, data, power. Hence, unlike the 1970s, AIs are not getting smaller and more distributed, but rather bigger and in ever larger data centers. In his essay, Amodei described AGI as “a country of geniuses in a data center.” But who is the ruler of this country? Is it the AI company who owns the data center? The AI itself?

Given the trend toward bigger and more expensive systems, it is possible that the few parties that can afford such systems capture all of the economic value they generate. Furthermore, if AIs are more intelligent than us, the temptation to give them more control for economic or military advantages may be hard to resist. I worry that concentration of power, whether in the hands of a few entities or the AI itself, could be the “default path.” But this choice is not inevitable.  

I am as “bitter lesson pilled” and “scaling law pilled” as anyone. I agree that ultimately, intelligence is simply computation, regardless of whether it takes place over proteins or silicon, and increasing the computing units will increase intelligence. But this does not determine the social or economic outcome. Yes, AI systems will become more powerful and far more intelligent than we are. No, it doesn’t mean we need to accept AI dictators, benevolent or otherwise. Nor does it mean that only the government and a few labs should have access to advanced AI. We could go down the path of centralized control but we don’t have to do so. People, institutions and legislators can make choices on how to trade off efficiency, safety, and individual autonomy. They don’t have to sacrifice the latter for the former.

Some might claim that market and capitalism forces will drive people to cede control to AIs. But the economy is ultimately about what humans value. Humans are social animals and we give value to goods (e.g. gold) not because of their intrinsic value but because of how other humans value them. AI will radically change what we value, though it is hard to predict in what ways. I am not even sure that economic concepts such as productivity, labor, capital, and GDP will continue to make sense in the post AGI world. Physicists know that “more is different.” As scientists studied new scales, whether galactic or subatomic, they needed to invent new theories, from Newtonian physics to general relativity and quantum mechanics. Perhaps we would need a new type of economy.

Others might say that given its power, safety requires AI to be controlled by either the government, a “safety conscious” lab, or the aligned AI itself. The risks are real—  I work on AI safety myself. But we should also remember the long history of using threats to take away people’s freedoms. Some of these threats were real— there were actually many Soviet spies during the McCarthy period and the NSA dealt with real terrorist organizations during Snowden’s time there. But in hindsight we realized that the tradeoff wasn’t worth it. We should invest in safeguards but be empirical about both the risks and the efficacy of our methods. Trying to achieve perfect safety against all risks, real and imagined, is not only doomed to fail but will cost us our liberty in the process. 

AI’s risks can lead to an “ends justifies the means” mindset: the “good guys must win” and they or the “good AI” must be in charge. But if we want a human centered and decentralized future, then no one entity should be in charge. No party should have a monopoly on intelligence. That includes the AI itself: while we can and should train in guardrails, the personality of the model, as good as it is, is never a substitute for our democratic process.

The U.S. survived and thrived in the last 250 years not because our presidents have all been saints or geniuses, but because of our system of checks and balances. I hope that we can keep such a system in place for the next 250 years, and to ensure that we humans are free to pursue our happiness in the way we define it. This requires that the distribution of AIs power is “baked into the DNA” of how we build and deploy this technology. If we fail to do so, then just like bloody revolutions often lead to authoritarian regimes, we may not be able to get to a decentralized future via centralized means.

Acknowledgement: I decided to write this post following a discussion on AGI with Sam Altman. However, the views here are my own, and do not represent Sam, OpenAI, or Harvard.

Notes:

¹ As mentioned, Amodei admits uncertainty about the matter; See  also “The Adolescence of Technology”. There are many parts in both essays that I agree with.

By Boaz Barak

Last Monday we had  an afternoon session of the Annual Meeting of the Israeli Mathematical Society celebrating Micha Perles’ 90th birthday. The speakers were Nati Linial, me, Noga Alon,  Ron Adin, and Rom Pinchasi. There was a very nice attendance and quite a few former students of Micha came to the event.

Some photos

  

In the top row Micha with eleven former Ph. D. students and with five former women Ph. D. students. Below: lectures, greetings, and the audience.

The lectures Nati Linial, Adventures with polytopes

Abstract: To the best of my recollection, I first heard about polytopes only when I started to attend Micha’s seminar, but with time, I found myself studying them myself. Fondly remembering the many things that I learned from Micha, I will tell about my most recent foray into this realm.

The bi-stochastic matrices form a polytope, in which every permutation matrix is clearly a vertex. The Birkhoff-von-Neumann theorem says that this exhausts the list of vertices. An array of non-negative reals is called tri-stochasic if every row, column, and shaft in it sums to 1. These arrays form a polytope too, where every Latin squares is clearly a vertex. However, as we show, Latin squares are only a vanishingly small minority of the vertices.

Joint with Zur Luria and Maya Trakhtman arXiv:2604.09290. Nati’s Slides.

Gil Kalai, Reflections on some old problems and results

Abstract: I will describe some problems and results of Micha A. Perles, and his students about polytopes, convex sets and point configurations, from the seventies and eighties of the 20th century, and some progress made over the past decades.

My slides.

Noga Alon, Micha and shattering

Abstract: The Sauer-Perles-Shelah lemma is a fundamental result in extremal combinatorics with applications in discrete geometry, computional learning, probability, combinatorics, model theory, property testing, social choice, and more. After very brief comments about the original result, I will describe some recent variants and extensions.

Noga’s slides.

Ron Adin, Circular sorting

Abstract: What is the maximal number of steps required to sort n labeled points on a circle, by swapping points in adjacent positions? What if we swap adjacent values, rather than adjacent positions? What if we allow arbitrary (not necessarily adjacent) swaps?
These are circular analogues of well-known sorting problems, with applications in various computational sciences. We will describe exact results, as well as bounds, obtained using combinatorial, probabilistic and number theoretic methods.

Based on joint works with Noga Alon, Eli Bagno and Yuval Roichman. Ron’s slides.

Rom Pinchasi, 30 years later– on the occasion of the 90th anniversary of Micha Perles

Abstract: In honor of Micha Perles’ 90th anniversary we will bring some of the many anecdotes that were not mentioned by previous speakers. We will combine these fun and beautiful memories from 30 years ago with some research and results that constitute my own private memories with Micha. The 90th anniversary of Micha Perles is a milestone for many people in the community of discrete geometry and combinatorics. Could it also be the end of the classical era of mathematics in some sense? We will know the answer by the 100th anniversary of Micha Perles. I promise many more anecdotes then.

Rom Pinchasi’s lecture had three parts. The first part was about the Kupitz-Perles conjecture (that I also mentioned more briefly in my lecture; see this post and this one). The second part was about Rom’s M. Sc. thesis about skips (דילוגים) in planar point configurations (but for time constraints, Rom skipped most of it.) The third part described Rom’s daring Program for proving Erdos distance one conjecture. (It is too late now, since the conjecture was refuted ; Seriously, it could still be useful if you want to prove the conjecture for, say, points in .

 

By Gil Kalai

Authors: Beniamin Bibrowski, Tomáš Masařík

Let $\mathcal F$ be a graph class that is closed under topological minors and 1-sums, has decidable membership, contains a triangle, and is not the class of all graphs. Recently, Lee, Liu, and Tsai [ICALP 2026] showed that the edge-decomposition problem into $k \geq 3$ elements of $\mathcal F$ is NP-hard. In particular, their general hardness reduction covers a long-standing problem on outerthickness (when $\mathcal F$ is the class of outerplanar graphs). On the other hand, it is well known that decomposing a graph into forests is polynomial-time solvable, as implied by work of Edmonds [J. Res. Natl. Bur. Stand. B. 1965]. In this paper, we take a first step toward determining the complexity of edge-decomposition problems into just two graphs (the case $k=2$). We consider the simplest possible graph class $\mathcal F$ satisfying the criteria above: the triangular forests, that is, graphs in which every 2-connected component is a triangle. We prove that determining whether a graph can be edge-decomposed into two triangular forests is NP-complete.

Authors: Omid Yaghoubi, Mikołaj Bojańczyk, Aliaume Lopez, Rafał Stefański

The goal of this paper is to propose a unifying model for Nerode-style characterizations of regularity across functions with different output domains. Building on Hauser's work in communication complexity, we generalize the setting by relaxing the computability assumptions and allowing non-Boolean output domains. We consider functions of type $Σ^* \to \domain$, where $Σ$ is a finite alphabet and $\domain$ is an arbitrary domain. For several domains, we show that the model coincides with known models of computation. We further conjecture that an analogous correspondence holds for other domains that currently lack a Nerode-style characterization of regularity, and we provide ample supporting evidence. In the model, an input string $w$ is split as $w = w_1 w_2$ and distributed between two cooperating parties, Alice and Bob, who exchange a constant number of messages to compute the value of the function. Each message is either an element of the output domain or a signal drawn from a finite set of signals, and the parties must produce the correct output for every admissible split $w = w_1 w_2$. We further extend the framework to infinite alphabets in the setting of nominal sets, and investigate its expressiveness on languages of words with atoms.

Authors: Jan Krajicek

Ilango (FOCS 2025) invented effectively zero-knowledge proofs, a new variant of zero-knowledge. We reformulate it in the language of logic and give simple proofs (under the same assumptions as Ilango (FOCS 2025)) of its existence and of the key property defined in Ilango (FOCS 2025) that it is "indistinguishable from true" (that property is in Ilango (FOCS 2025) a part of the definition of the prover, not its consequence). Using the theory of proof complexity generators we show that the concept can be turned it into a genuinely zero-knowledge proofs, assuming a conjecture from the theory about the existence of a hard generator and allowing the parties to share a common random string.

Authors: Phillip Kerger

We study the deterministic query complexity of minimizing a convex Lipschitz function over a $d$-dimensional Euclidean ball using only exact function values. At accuracy $Θ(d^{-1/2})$, the previously applicable lower bound was $Ω(d)$, inherited from the stronger full first-order oracle, while an upper bound from Protasov's value-only method requires $O(d^2\log^2 d)$ evaluations. By providing a lower bound of $Ω(\,\frac{d^2}{\log(d+1)})$ on the oracle complexity in this setting, we thereby close this gap dating back to 1996, up to polylogarithmic factors. Furthermore, we are able to lift this result to the mixed-integer setting: Mixed-integer convex optimization with $d$ continuous and $n$ discrete variables using function values requires $\tildeΩ(d^2\cdot 2^n)$ queries.

Authors: Chinonso Onah, Stuart Hadfield, Kristel Michielsen

We study the separation of geometric effects from quantum interference in quantum optimization algorithms. Constrained optimization problems such as routing, assignment, and scheduling are often encoded as product spaces of local variables, together with global feasibility penalties. The central algorithmic question we address is how a constraint-preserving mixing operator transports quantum amplitude across an exponential search space in the presence of local and global constraints. We develop a framework that separates three effects that are usually intermixed: amplitude transport, coherent interference among transported amplitudes, and problem-dependent classical postprocessing. We show that the mixing operator alone does not have a target-seeking ability. Concretely, the normalized distribution induced by its amplitude transport moves toward the distance profile of a uniformly random configuration. Thus, quantum sampling advantage may only arise when the phases of the many computational paths reaching a target configuration are sufficiently aligned for their amplitudes to reinforce. We show that, when the cost phases are engineered so that these paths add coherently, a number of circuit alternations growing only logarithmically with problem size suffices to convert the sum of their absolute contributions into a lower bound on the target amplitude, yielding a certified success probability independent of the ambient Hilbert-space dimension, the search-space size, or the feasible-set cardinality. We develop applications to problem-specific transpilation diagnostics, scalable hardware probes, constraint-induced classical maps of quantum-generated samples, the attribution of solution quality between the quantum distribution and classical post-processing in hybrid quantum-classical workflows and connections to distance-partitioned product spaces from classical coding theory.

Authors: Tahmina Khanam, Hamid Laga, Mohammed Bennamoun, Guanjin Wang, Ferdous Sohel, Farid Boussaid, Anuj Srivastava

We introduce a novel mathematical framework for analyzing and generating complex tree-shaped 3D objects, such as botanical trees and plants, which deform both in their 3D geometry and branching structure. Unlike previous works, which either consider only the skeletal structure of tree-like objects or approximate their 3D geometry using branch thickness, the proposed framework accurately models both the 3D geometry of the tree branches and the way they are interconnected. In this paper, we first generalize the Square Root Normal Fields (SRNF) representation, originally proposed for the statistical analysis of genus-0 surfaces, to tree-shaped 3D objects. We then treat tree-shaped 3D objects as points on a novel Riemannian tree-shape space equipped with a novel Riemannian metric that measures the amount of surface bending and stretching, and structural changes one needs to apply to one 3D tree-shape to align it with another. This way, deformations become trajectories in this novel tree-shape space. We analyze the theoretical properties of this novel tree-shape space and the corresponding metric and develop algorithms for computing point-wise and branch-wise correspondences and geodesic paths between complex 3D trees. We finally show how to use these building blocks for (1) computing statistical summaries, \ie means and modes of variation, of collections of tree-shaped 3D objects, and (2) synthesizing novel tree-shaped 3D objects by sampling from probability distributions fitted to a population of tree-shaped 3D objects. We demonstrate the performance and utility of the proposed framework on real and synthetic plants and botanical trees and show that it significantly outperforms the state-of-the-art.

Authors: Afonso S. Bandeira, Dmitriy Kunisky, Petar Nizić-Nikolac, Lucas Pesenti, Robert Wang

The hypergraph Moore bound conjectured by Feige (2008) controls the size of the smallest even cover in a $k$-uniform hypergraph in terms of the average density of hyperedges. An even cover is a set of hyperedges covering each vertex an even number of times, generalizing the notion of a cycle in a graph, so the size of the smallest non-trivial even cover provides a notion of hypergraph girth. Recent work starting from the breakthrough result of Guruswami, Kothari, and Manohar (2022) proved the conjecture up to polylogarithmic factors, whose exponents were later gradually improved. We give a simple proof of Feige's original hypergraph Moore bound conjecture for all even $k\ge 4$, with no superfluous polylogarithmic factors. Our proof roughly follows the proof of the graph Moore bound, but works with colored walks in a Kikuchi graph built from a hypergraph and controls their growth using a polynomial interpolation method.

Authors: Rudranarayan Kar, Praneet Kumar Patra, Diya Roy, Abhishek Sahu

Telephone broadcasting is a classical model for spreading information in a network. Given a connected graph $G(V,E)$ with source vertex $s$, each informed vertex may inform exactly one uninformed neighbor in every time step. The \textsc{Broadcasting} problem asks whether all vertices can be informed within $t$ steps; the minimum such value is the broadcast time $b(G,s)$. A related variant considers the worst-case source, $b(G)=\max_{u\in V} b(G,u)$. Both variants are NP-hard, and every $n$-vertex graph satisfies $b(G,s)\ge \log_2 n$. Fomin \textit{et al.}~\cite{fomin2023parameterized} recently gave FPT algorithms for this problem under several structural graph parameters. Instead of computing optimal broadcast schedules, we study faster approximation algorithms that produce valid schedules. We improve the $O^*(3^n)$ exact algorithm of Fomin \textit{et al.} to an $O^*((3-f(x))^n)$ algorithm with a $+x$ additive approximation, where $f(x)>0$ is a constant for every fixed $x$. We also give approximation algorithms on graphs of bounded vertex integrity, including a polynomial-time $+2k$ additive approximation algorithm. Complementing these positive results, we prove parameterized hardness for vertex cover above maximum matching ($\mathrm{VC}-\mathrm{MM}$), dominating set size, and graph diameter, indicating that FPT algorithms for these parameters are unlikely. Finally, we present a $+2$ additive approximation algorithm for distance-to-clique running in $O^*(2^{O(k\log k)})$ time, a $2$-factor approximation algorithm for distance-to-path running in XP time, and a polynomial-time algorithm for polar graphs.

Authors: Tommaso Cesari, Roberto Colomboni

We prove an effective-resistance bound for fixed-rank external-field measures. Let $d\ge2$ be an integer, let $m\in\{1,\ldots,d-1\}$. Let $w\in(0,+\infty)^d$, and let $\mathsf S$ be an $m$-element random subset of $[d]$ distributed according to the rank-$m$ external-field measure with weights $w$, i.e., \[\mathbb P(\mathsf S=S)=\frac{\prod_{i\in S}w_i}{e_m(w)},\qquad S\subseteq\{1,\dots,d\},\quad|S|=m,\] where \[e_m(w):=\sum_{\substack{T\subseteq\{1,\dots,d\}\\|T|=m}}\prod_{\ell\in T}w_\ell\] is the $m$th elementary symmetric polynomial in $w_1,\ldots,w_d$. Let $X:=(X_1,\dots,X_d)^\top$ be its indicator vector, i.e., \[X_i=\mathbb I\{i\in\mathsf S\},\qquad i\in\{1,\dots,d\}.\] Let $Σ:=\operatorname{Cov}(X)$, put $v_i:=Σ_{ii}$ for each $i\in\{1,\dots,d\}$, and let $\mathbf e_1,\ldots,\mathbf e_d$ denote the standard basis of $\mathbb R^d$. Our main result is that, for every $i\ne j$, \[(\mathbf e_i-\mathbf e_j)^\topΣ^\dagger(\mathbf e_i-\mathbf e_j)\le\frac1{v_i}+\frac1{v_j},\] where $Σ^\dagger$ is the Moore-Penrose pseudoinverse of $Σ$. As a consequence, if \[v:=(v_1,\ldots,v_d)^\top,\qquad D:=\operatorname{diag}(v),\qquad V:=\sum_{i=1}^dv_i,\] then, as a corollary, we obtain \[Σ\succeq\frac12\left(D-\frac{vv^\top}{V}\right),\] which establishes a factor-two relaxation of the normalized covariance bound conjectured by Anari, Haqi, and Ma. As a further corollary, combining our theorem with the recent framework of Anari, Haqi, and Ma yields a constant-stretch guarantee for correlated sampling on the hypersimplex without relying on the still-open normalized covariance conjecture assumed in their conditional result. Our result improves the logarithmic-in-$k$ stretch bound of Naor, Raju, Shetty, Srinivasan, Valieva, and Wajc to a constant and resolves the open question posed in their work.

Authors: Hans-Joachim Böckenhauer, Dennis Komm, Emanuel Skodinis, Moritz Stocker, Philip Whittington

We study the online proportional knapsack problem with two paid forms of recourse. Items arrive one by one and must be handled immediately, without knowledge of the future: an algorithm may pack an item $x$, reject it, or reserve it for possible later use at proportional cost $αx$; additionally, it may at any time remove previously packed items, at proportional cost $βy$ for each removed item $y$. Reservation and removal have each been analyzed in isolation, but their combination raises a natural question: is the better of the two mechanisms always optimal on its own, or is there a region in the parameter space spanned by $α$ and $β$ in which they genuinely enter into a symbiosis? So far, this question has only been answered for the special case of free removal ($β= 0$), leaving the vast majority of the parameter space unexplored. We close this gap, determining matching upper and lower bounds on the competitive ratio for every pair of cost parameters $(α, β)$ and revealing three qualitatively different regimes. In some regions, reservation alone already achieves the optimal ratio; in others, removal alone does. However, most interestingly, in the heart of the parameter space lies a symbiosis region in which combining both mechanisms is strictly better than either one on its own. The optimal algorithm in the symbiosis region is a natural blend of the two known single-mechanism strategies: postponing commitment by reserving until a threshold is reached, then packing greedily and revising via removal.

Authors: Yunbum Kook

Inspired by interior-point methods (IPM) for structured convex optimization, Kannan and Narayanan introduced the Dikin walk for sampling uniformly from polytopes in 2009. As in IPMs, the Dikin walk is affine-invariant, and its convergence is governed by the barrier geometry used to define its local proposal. They showed that the Dikin walk with the logarithmic barrier for a polytope in $\mathbb{R}^{d}$ with $m$ linear inequalities mixes in $md$ iterations. In 2017, Chen, Dwivedi, Wainwright, and Yu improved this to $d^{2.5}$ using a Lewis-weight barrier, and conjectured that the correct mixing time should be $d^{2}$. We make progress toward this conjecture by improving the previous $d^{2.5}$-mixing bound. For exponential sampling over a polytope, we prove that the Dikin walk with a scaled Lee--Sidford metric mixes from a warm start in $d^{2.25}$ iterations. This also yields an improved cold-start complexity via a known annealing framework. The main technical ingredient is improved average self-concordance of the Lee--Sidford metric, which gives high acceptance probability for the Metropolis filter along a random Dikin proposal. While previous analyses were effectively limited to second-order control due to technical difficulties, we develop a principled higher-order analysis. The proof combines a selective higher-order expansion of recursive bottleneck terms, a moving orthonormal-frame calculus for higher derivatives of the Lewis weights, and Wiener-chaos decompositions via multiple stochastic integrals to control the resulting Gaussian polynomials.

Authors: Thomas L. Draper, David G. Harris, Feras A. Saad

We develop an efficient online algorithm to sample a sequence of discrete random variables using an entropy source of i.i.d. fair coin flips, in a standard model of real computation where real-valued probabilities are represented by rational approximations. For any sequence $F_1, F_2, \dots$ of probability distributions, our sampler generates $n$ outputs $X_1 \sim F_1, \dots, X_n \sim F_n$ using at most $\mathbb{E}\left[H(F_1) +\dots + H(F_n)\right] + O(\log n)$ coin flips in expectation while carrying $O(\log n)$ bits of persistent space, where $H$ is the Shannon entropy. Under standard assumptions, we prove that the space used by our sampler to achieve this information-theoretically optimal entropy rate is asymptotically optimal. The key idea is to replace the global arithmetic-decoding sampling scheme of Han and Hoshi (1997) with a local discrete uniform state, yielding an exponential reduction in space for a given entropy loss. Our approach applies to distributions with irrational probabilities and countably infinite supports, generalizing recent randomness-recycling methods beyond finite rational distributions with bounded denominator.

Authors: Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo, Konstantin Makarychev

We study phase transitions and algorithms for refuting CSPs arising in hierarchical clustering (as well as ranking, and ordinary CSPs). Here, $n$ variables are assigned to leaves of a tree, so as to satisfy $m$ constraints, specifying evolutionary relationships. Two canonical $NP$-hard optimization problems are Triplet and Quartet Reconstruction, where the input consists of triplets $xy|z$ or quartets $xy|zw$, and the goal is to find a tree $T^*$ maximizing agreement with constraints. Our main results are (as density $λ=m/n$ increases): 1. We show the existence and precisely locate the sharp threshold $λ^*\approx1.2277$ for Triplets (via closed-form solution). To the best of our knowledge, this is the first sharp threshold for the broad family of Phylogenetic CSPs. Moreover, we give a lower and upper bound for Quartets. 2. We provide strong refutation algorithms that certify that $val(T^*)\le5/9 + ε$, where $val(T^*)$ is the fraction of constraints satisfied by the (unknown) optimal tree. For triplets, our algorithm succeeds w.h.p if $m =Ω(n)$, and for quartets if $m = Ω(n^{3/2})$. 3. We obtain strongest possible refutations at slightly larger densities (for triplets $m=O(n^{3/2}\log ^3n)$, for quartets $m=O(n^2)$): we certify that $T^*$ is no better than a random assignment, i.e., $val(T^*)\le 1/3+ε$. In fact, we obtain strongest possible refutations for finite-alphabet CSPs with or without negations. Our refutations above are instantiations of our general theorem that applies more broadly to Phylogenetic and Ordering CSPs (and all CSPs failing to support $t$-wise independence), and generalizes the current algorithmic frontier on refuting random CSPs~\citep{allen2015refute}. A crucial difference here, unlike Boolean CSPs, is that there are no negated variables, so prior works relying on negations -- a source of randomness -- do not apply.

Authors: Han Luo, Ziyi Yang, Jingquan Luo, Ziruo Wang, Yuexin Su, Xiaoming Sun, Lvzhou Li, Tongyang Li

The Elliptic Curve Discrete Logarithm Problem (ECDLP) is a fundamental problem in cryptography, and reducing the resource requirements of quantum algorithms for solving ECDLP is an important goal. In this work, we present a space-efficient quantum algorithm for solving the ECDLP over prime fields, achieving an implementation with only $3n+6\lfloor \log_2 n \rfloor+O(1)$ logical qubits and $919n^3/\log_2 n+O(n^2)$ Toffoli gates, where $n$ is the bit-length of the prime. For a 256-bit prime-field curve, our construction requires only 835 logical qubits, reducing the previous best estimates of 1098 and 1175 logical qubits by Chevignard et al. [EUROCRYPT 2026] and Babbush et al. [ArXiv Preprint 2026], respectively. The key to our improvement is a new space-efficient reversible modular inversion circuit, which addresses the dominant space bottleneck in affine-coordinate point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing technique of Proos and Zalka by introducing length registers and location-controlled arithmetic to compactly store and update intermediate variables. We further optimize the reversible update procedures and construct the corresponding controlled arithmetic circuits, resulting in a modular inversion circuit implemented by only $2n+6\lfloor \log_2 n \rfloor+O(1)$ logical qubits and $195n^2+O(n\log_2 n)$ Toffoli gates. This modular inversion circuit together with mid-circuit measurements and classical feed-forward operations provides a space-efficient controlled affine point-addition circuit and a complete implementation of Shor's algorithm for ECDLP.

Authors: Satyabrata Jana, Shivesh K. Roy, R. B. Sandeep

Vertex splitting replaces a vertex (v) by two nonadjacent vertices whose neighborhoods together equal (N(v)). A split is \emph{exclusive} if these neighborhoods are disjoint and \emph{shallow} if no newly created vertex is split again. For a graph property (Π), \textsc{(Π)-Vertex Splitting} asks whether at most (k) splits can transform a graph (G) into one satisfying (Π). We continue the systematic study of this operation and settle several open problems. First, we prove that \textsc{Cograph Vertex Splitting} is \textsf{NP}-complete, even on graphs of girth at least 5, resolving a question of Firbas and Sorge (ISAAC 2024). More generally, \textsc{(P_t)-free Vertex Splitting} is \textsf{NP}-complete for every fixed (t\geq 4). We also prove that \textsc{Chordal Vertex Splitting} and \textsc{Unit-Interval Vertex Splitting} are \textsf{NP}-complete, resolving two questions of Abu-Khzam, Chakraborty, Isenmann, and Oijid (IWOCA 2026). Our hardness results extend to the exclusive and shallow variants. Assuming the Exponential Time Hypothesis, none of these problems admits an algorithm running in (2^{o(k)}n^{O(1)}) time; moreover, except for the unit-interval cases, none admits an algorithm running in (2^{o(n)}) time.

Authors: Carlos Bravo-Prieto, Weiyuan Gong, Antonio Anna Mele

Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information. In this setting, protocols with quantum memory can coherently store and jointly process quantum information obtained from multiple channel uses, whereas protocols without quantum memory must measure after each use and retain only a classical transcript of the measurement outcomes. A fundamental open question is whether quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments based on all previous outcomes with unbounded classical computational power. In this work, we show that it does. We determine the optimal query complexity of quantum process tomography without quantum memory up to a constant factor to be $Θ(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$, where $d_{\mathrm{in}}$ and $d_{\mathrm{out}}$ are the channel input and output dimensions, respectively, and $\varepsilon$ is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires $Ω(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$ queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound $O(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$. Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case $d_{\mathrm{in}}=1$. By contrast, coherent protocols with quantum memory achieve query complexity $Θ(d_{\mathrm{in}}^2 d_{\mathrm{out}}^2/\varepsilon^2)$. Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.

Authors: Vignesh Viswanathan

We present an $(e^{1/e} - c)$-approximation algorithm for maximizing Nash social welfare under additive valuations, for some constant $c > 0$. This result improves upon the previous best-known approximation factor of $e^{1/e}$ [Barman, Krishnamurthy and Vaish, EC 2018].

Authors: Jan Höckendorff, Felix Hommelsheim, Christian Sohler, Di Yue

The minimum spanning tree (MST) problem is one of the most basic optimization problems on metric spaces and graphs. We study the problem of computing a $(1+ε)$-approximation to the MST of an $n$-point metric space $(X, \mathbf{d})$ of doubling dimension $\mathrm{ddim}$. In doubling metrics, previous deterministic algorithms incur a running time with dependence $ε^{-O(\mathrm{ddim})}$. We give a deterministic algorithm that computes a $(1+ε)$-approximation to MST in time $2^{O(\mathrm{ddim})} n \bigl(\log n + ε^{-1} \log^4(1/ε)\bigr)$. For bounded doubling dimension, this improves the previous dependence on $ε$ from $ε^{-O(\mathrm{ddim})}$ to essentially linear in $ε^{-1}$. Moreover, as a special case, our result improves the previous best deterministic running time for bounded-dimensional Euclidean metrics due to Arya and Mount~[SODA'16] by almost a factor of $ε^{-1}$. We also show that, unlike in bounded-dimensional Euclidean spaces, MSTs in bounded doubling metrics can have arbitrarily large maximum degree, while every doubling metric nevertheless admits a $(1+ε)$-approximate MST of maximum degree $2^{O(\mathrm{ddim})}\log(1/ε)$.

Authors: Yang Hu, William Kuszmaul, Jingxun Liang, Stefan Walzer, Huacheng Yu, Renfei Zhou

Quadratic probing is one of the most widely used open-addressing hash-table schemes in practice, but after more than half a century, even its most basic performance guarantees remain poorly understood. In this paper, we revisit quadratic probing through the lens of a smoothed variant in which each key follows a random probe sequence where its $k$th probe is expected at offset $Θ(k^2)$. This is simultaneously a toy model for better understanding regular quadratic probing and a natural hashing scheme in its own right. We analyse smoothed quadratic probing for both Robin Hood ordering and anti-Robin Hood ordering and reveal a surprising separation: At load factor $1-\varepsilon$, anti-Robin Hood achieves an expected query time of $Θ(\log \varepsilon^{-1})$, which matches the conjectured expected average successful query time for regular quadratic probing, while Robin Hood falls short at $Θ(\varepsilon^{-1/2})$. Our analysis generalises to degree-$d$ probing for any $d \ge 1$ with expected query time $O(\max(\log \varepsilon^{-1}, \varepsilon^{1-2/d}))$ for anti-Robin Hood and $Θ(\varepsilon^{-1/d})$ for Robin Hood. Finally, we go beyond smoothed analysis: using the probabilistic method, we show that for every $d \ge 2$, almost every random fixed-offset degree-$d$ probing sequence achieves expected query time $O(\log \varepsilon^{-1})$ under anti-Robin Hood ordering, simultaneously over all admissible table sizes and load factors. Thus, while quadratic probing itself remains elusive, we prove that essentially all quadratic-probing-like fixed-offset schemes achieve the ideal performance under the anti-Robin Hood ordering.

Authors: Michał Szyfelbein, Dariusz Dereniowski

In this work, we study various graph partitioning problems under a general demand model. In each such task, we are given a graph $G=(V,E,c,w)$ with a capacity function $c\colon E\to \mathbb{N}$ and a demand function $w\colon V\times V\to \mathbb{N}$. Our main focus is the problem of finding a cut $(S, \bar{S})$ minimizing the quantity \[ ψ_w( S ) = \frac{c( S, \bar{S} )}{w( S, V )\cdot w( \bar{S}, V )}. \] Here, $c( S, \bar{S} )$ is the cost of edges between $S$ and the complement of $S$, $\bar{S}$, and $w( S, V )=w( S )+w( S, \bar{S} )$ is the sum of the internal demand within $S$, $w( S )$, and the demand between vertices of $S$ and $\bar{S}$, $w( S, \bar{S} )$. We call $ψ_w( S )$ the \emph{generalized conductance} of the cut $(S, \bar{S})$, and the task of minimizing $ψ_w( S )$ the Generalized Conductance Problem. Our main contribution is an algorithm with an $\mathcal{O}(\log n)$-approximation guarantee for this objective. Our result is achieved via a two-way reduction: first to the well-known Generalized $k$-Multicut Problem, and then to a constrained variant of the classic Sparsest-Cut Problem, with an additional upper-bound constraint on the amount of demand that may be cut. Moreover, we show that the above procedure can be used to obtain an $\mathcal{O}(\log n)$-bicriteria approximation for Graph Partitioning with Demands, where the goal is to find a minimum-cost subset of edges $C$ such that for every component $H$ of $G\setminus C$, $w( H )\leq ρ\cdot w( V )$. This, in turn, yields an $\mathcal{O}(\log n)$-approximation for Hierarchical Clustering with Demands, the problem of finding a hierarchy of cuts that partitions the graph into increasingly refined clusters. For multiplicative demand functions, we improve these guarantees to $\mathcal{O}(\sqrt{\log n})$ and for trees we get an $\mathcal{O}(1)$-approximation for all of our objectives.

Authors: Michał Szyfelbein, Dariusz Dereniowski

Consider the following variation on the Hierarchical Clustering problem: Usually, while building a hierarchical clustering, one recursively partitions the data until each cluster becomes a singleton. We relax the halting condition of the recursive process to stop whenever the remaining cluster is a graph belonging to a class $\mathcal{F}$. We call this problem Hierarchical $\mathcal{F}$-Clustering and we measure the quality of any solution using adapted Dasgupta's clustering objective. We study two natural choices of $\mathcal{F}$: trees and graphs of bounded diameter. We present the first polynomial time $\mathcal{O}(\log n\cdot\log\log n)$ and $\mathcal{O}(\log n)$-approximation algorithms for clustering into trees and bounded diameter graphs respectively. Our main technical contribution is a framework for approximating such problems based on linear programming. In fact, we characterize graphs classes $\mathcal{F}$ for which our approach can be applied and show that it includes both trees and bounded diameter graphs. However, our ideas are not limited to them and might be useful for other structures as well. Broadly speaking, our framework applies whenever the corresponding flat clustering problem, which we call $p_{\mathcal{F}}$-Partitioning, admits a natural ILP formulation together with a rounding procedure with provable approximation guarantees. Intuitively, given a set of vertices called terminals, the problem is to find an edge set whose removal results in satisfying certain vertex-dependent structural predicate for each terminal. We then use these ingredients to build clustering trees with the aforementioned approximation guarantees. To complement these results, we show that both Hierarchical Clustering into trees and into bounded diameter graphs cannot be approximated within any constant factor under the Small Set Expansion Hypothesis.

Authors: Igor Pak, Daniel Soskin

We give an algebraic branching program of polynomial size which computes Cayley determinant of right quantum matrices. This is a rare example of an efficient computation of a noncommutative determinant, and the first such example for quantum groups. We extend the results to the $q$-Cayley determinant of $q$-right quantum matrices, as well as to their multiparameter generalization. The proofs are entirely combinatorial, as we relate Cayley, Moore and Valiant determinants using bijections/involutions on words. We then employ the celebrated determinant construction of Mahajan and Vinay (SODA'97), to obtain the results.

The recent breakthrough work of Chatterjee, Ghosh, Gurjar, Raj and Thierauf [CGGRT26] gives the first deterministic NC algorithm for the bipartite matching problem. They show how to detect as well as find perfect matchings in bipartite graphs in NC. In this note we present an arguably simpler-to-state variation of the NC detection criterion of [CGGRT26], with improved parameters.

• Another mathematics journal leaving its commercial publisher (\(\mathbb{M}\)), but with a twist: usually this is accomplished by a mass resignation of the editorial board. But in this case, Communications on Pure and Applied Mathematics is owned by the Courant Institute and was published by Wiley, so taking it in-house is just a matter of not renewing the contract. The causes of friction were increased publisher interference with editorial decisions (the usual), but also editor dissatisfaction with the publisher’s editorial management software.

• An American privacy emergency (\(\mathbb{M}\)): Cynthia Dwork on how new US government regulations forbidding the Census Bureau from masking its released data under differential privacy will give us less usable data, reduced protection against privacy-violating disclosures, or both. Cynthia also provides information about what you can do to help work against this.

• A reduced planar body with area greater than \(\pi\Delta^2/4\) (\(\mathbb{M}\)), new preprint by Scott Duke Kominers. Here, “reduced” is a concept for two-dimensional convex bodies that is closely related to having constant width. The directional width is the distance between parallel support lines, constant width means that all directional widths are the same, thickness means the minimum directional width, and reduced means that any convex body that is a proper subset has smaller thickness. So bodies of constant width are reduced but not necessarily vice versa. For instance both Reuleaux triangles and equilateral triangles are reduced; the first has constant width, the second does not. A structure theorem described in the paper states that reduced bodies have parts of their boundary with constant width and parts that are flat.

  Anyway, it had been conjectured that the formula in the title was the maximum area for a reduced body of thickness , with bodies attaining that area including the circular disk and quarter-disk. As evidence for the conjecture, it is true both for shapes of constant width and for polygons. But the paper describes a shape resembling a sharper wedge of a disk than a quarter, with a rounded apex, that slightly betters this area.

• Ed Pegg sent me the image below (\(\mathbb{M}\)) illustrating some of the minimal geometric independent dominating sets (small sets of grid points with no three in line to which no additional grid point can be added) from my EuroCG’21/CGTA’23 paper with Aichholzer and Hainzl, “Geometric dominating sets – A minimum version of the no-three-in-line problem”. See also Ed’s Wolfram community post about these sets.

  

• Geometric models by A. Harry Wheeler in the Smithsonian Institution (\(\mathbb{M}\)). Another set of Wheeler models that for some reason doesn’t appear in the main list: Dissected polyhedra transformable into other polyhedra. For more on Wheeler, see Wheeler’s Wikipedia biography

• Shachaf observes that, in the computable reals, you can find the values of a sorted list but you cannot determine its permutation, in response to another post claiming that sorting code that doesn’t explicitly discuss permutations is “awful”. But this raises questions about constructive type theory: how can you specify that this is a sorting algorithm without having a decidable notion of equality?

• Does anyone know a reference for the following easy theorem about estimating area by counting lattice points (\(\mathbb{M}\)), extending Nosarzewska’s inequality from convex to simply-connected regions?

  Let \(J\) be a region of area \(a\) bounded by a Jordan curve of length \(p\). Then:

  \[|a - \#(\mathbb{Z}^2\cap J)| = O(p+1).\]

  Proof: sweep a unit square around the boundary of \(J\); by Cavalieri’s principle the area of the swept region \(B\) is \(\le 1+p\sqrt 2\). Consider the Voronoi cells of the integer lattice; outside of \(B\) they are completely inside or completely outside \(J\). Therefore,

  \[\begin{align}a-1-p\sqrt 2&\le \operatorname{area}(J\setminus B)\\&\le \#(\mathbb{Z}^2\cap J)\\&\le \operatorname{area}(J\cup B)\\&\le a+1+p\sqrt 2.\end{align}\]

• Emacs org-mode adds support for using ltx-talk in \(\rm{\LaTeX}\) to produce accessible slides in tagged pdf format (\(\mathbb{M}\)).

• Two-sided ruler constructions (\(\mathbb{M}\)). A series of blog posts by David K. Butler on how to use an unmarked ruler with two parallel edges to do almost everything that you could do with a ruler and compass.

• Reformatted schedule for the International Congress of Mathematicians (\(\mathbb{M}\)) with MathJax abstracts that don’t require clicky popups to read, by M.-J. Dominus.

• OpenAI claims a very short proof of the cycle double cover conjecture (\(\mathbb{M}\)).

• Chris Staecker live-tweets the figures for an in-progress digital topology book, deliberately omitting any explanations of the figures.

• Terry Tao on Gilbreath’s conjecture (\(\mathbb{M}\)). The first difference sequence of the prime numbers starts 1, 0, 2, 2, 2, 2, 2, 2, 4, … . The second, third, and fourth difference sequences all start with 1, 2, 0, 0. The first numbers in each sequence must be odd and the rest even, but which odd number? Gilbreath and before him Proth conjectured that every difference sequence begins with 1. Merely having the same small gaps and parity properties as the primes does not suffice: see my old blog post “Anti-Gilbreath sequences” for sequences with these properties whose difference sequences have infinitely many non-1 starting values.

  The primes are thought to behave similarly to random sequences, so researchers have attacked the problem by studying prime-like random sequences. Past work by Chase shows that sequences whose gaps between consecutive elements are random with very slow growth (slower than the primes) almost surely have all but finitely many difference sequences beginning with 1. Now a new preprint by Chase, Tao, and Zach Hunter, using a structural characterization of anti-Gilbreath sequences related to my post, extends Chase’s work to a model of random sequences with geometrically distributed random gaps of sizes matching the prime numbers. It still doesn’t address the actual prime numbers but I think by matching their distribution better it provides strong evidence for the conjecture.

• How LLM nonsense is affecting Wikipedia: increased drama and increased volunteer workload triggered by “crap articles generated by LLMs, or people using LLMs to write extremely wordy, unhelpful replies to concerns about their behaviour”.

By David Eppstein

Herman Chernoff passed away on July 6, 5 days after turning 103. Ravi Boppana wrote a guest post about Chernoff's life for his 100th birthday. 

Let me talk about his most famous work, the Chernoff Bounds themselves.

If you have a coin that will be heads with probability \(p\), and you flip it \(n\) times, the expected number of heads is \(pn\). Informally Chernoff bounds says that for large \(n\) the number of heads will be quite close to \(pn\) with an exponentially small probability of being far away from \(pn\). For example, if you flip a coin with probability 30% chance of being heads 10,000 times, the probability that you will get at most 2500 heads is less than \(10^{-18}\).

More formally, for \(\delta \in (0,1)\), Chernoff's bound shows that

\[\Pr[|X - \mu| \geq \delta\mu] \leq 2e^{-\mu\delta^2/3}\]

for \(\mu = \mathbb{E}[X]\). I find the variation known as Hoeffding's inequality \[\Pr[|X - \mu| \geq t] \leq 2e^{-2t^2/n}\] easier to use for computational complexity.

Chernoff bounds play a major role in computational complexity, for example you can use Chernoff Bounds for probabilistic, quantum and interactive proof algorithms to reduce the error to exponentially small. That means using the union bound, a single random sequence will give the correct answer for all inputs, showing that BPP is in P/poly. 

Chernoff bounds are a key ingredient in the proof that MA (prover then verifier) is contained in AM (verifier then prover). Roughly you make the MA error so small that the same random coins work no matter what the prover might say. MA in AM plays a key role in the proof that NP in BPP implies PH in BPP which itself is necessary for Toda's theorem.

The proof of Chernoff bounds comes from a simple trick: Rather than bounding \(\Pr[X \geq a]\) directly via Markov's inequality on \(X\), you apply Markov to \(e^{tX}\) for a free parameter \(t > 0.\) Since \(e^{tX}\) is nonnegative,

\[\Pr[X \geq a] = \Pr[e^{tX} \geq e^{ta}] \leq \frac{\mathbb{E}[e^{tX}]}{e^{ta}},\]

and then you optimize over \(t\). The quantity \(\mathbb{E}[e^{tX}]\) is the moment generating function, and for a sum \(X = \sum_i X_i\) of independent variables it factorizes into \(\prod_i \mathbb{E}[e^{tX_i}]\). That factorization is what converts a linear tail bound into an exponential one, each independent term contributes multiplicatively, so the deviation probability shrinks like a product rather than a sum.

Chernoff did not think of himself as a theorist. 

People regard me as a theoretical statistician, but I’ve decided in recent years that I’m really an applied statistician. My theoretical insights have relied upon my work in thinking about applied problems.

A good lesson for us all.

By Lance Fortnow