Theory of Computing Report

During the heroic age of mathematical exploration (circa 3000 BCE — 2026 CE), mathematicians trailblazed through desolate, inhospitable lands by bare brainpower, carrying nothing except maybe chalk, paper, and pen. They were poor, unkempt, often begging for the meager funds they required. Yet most were happy to dedicate their lives to exploration, which for them was a lifestyle, like farming, and constantly occupied their minds. Sometimes at the cost of great personal sacrifices, they rushed through white deserts covered in chalk dust. They planted their tiny flags in spots undistinguished by anyone except themselves and a few travelers along the same route. They didn’t claim the land, and were happy to show the path ahead, just asking for a little recognition — which to our modern eyes looks childishly petty until we remember the conditions in which their discoveries were made. There have been many Amundsens, ruthlessly competitive and efficient, some Scotts, who alas paid the highest price for their discoveries, and a few Shackletons. In some museums you can still see today samples of their maps inked on paper.

By Manu

Iliad runs fully funded AI safety research programs in London and Berkeley: the four-week Iliad Intensive ($5,000 travel-and-housing allowance) and the three-month Iliad Fellowship ($18,000 of funding), for people with strong mathematics, physics, or theoretical CS backgrounds. Several cohorts run each year and one application covers all of them.

Website: https://www.iliad.ac/programs
Email: admissions@iliad.ac

By shacharlovett

Sipser and Spielman constructed LDPC codes from either bipartite \emph{spectral} expanders or one-sided \emph{lossless} expanders. In higher dimensions, \emph{spectral} expansion similarly played a central role in the constructions of asymptotically good classical LTCs and qLDPC codes by Dinur, Evra, Livne, Lubotzky, and Mozes and by Panteleev and Kalachev. Alternatively, Lin and Hsieh constructed classical LTCs and qLDPC codes from two-dimensional \emph{lossless} cubical complexes. In this work we develop the higher-dimensional \emph{lossless} approach. We do not construct the required high-dimensional lossless cubical complexes; rather, we investigate what their existence would imply. We associate with a high-dimensional cubical complex a \emph{level chain complex}, whose chain groups are supported on the level sets of the Boolean cube rather than on its cells. Our main technical contribution is a clean local-to-global theorem for this structure: suitable one-dimensional lossless expansion in the directional graphs implies small-set coboundary expansion of the global level complex. As a consequence, sufficiently imbalanced, two-sided lossless four-dimensional cubical complexes give rise to asymptotically good quantum locally testable codes. We expect the local-to-global principle developed here to have further applications.

Authors: Christoph Berkholz, Matthäus Micun, Igor Razgon

Tree Decision Diagrams (TDDs) are a data structure recently introduced by Capelli et al. (SAT 2026). They are structured along a vtree and the size of their canonical form lies between Ordered Binary Decision Diagrams (OBDDs) and deterministic structured DNNF circuits (d-SDNNFs). While the succinctness gap between TDD and d-SDNNF is exponential, only a quasipolynomial separation between OBDD and TDD has been shown and it was left as open question whether this is optimal. We answer this question affirmatively by showing that every TDD can be transformed to an equivalent OBDD of quasipolynomial size. Although this might be seen as a weakness, our second result shows that TDDs share another desirable property with OBDDs that is not known to hold for d-SDNNF: Given a TDD and another target vtree, it is possible to construct the minimal and canonical TDD respecting the new vtree in time polynomial in the input and output. As a result we also obtain that the equivalence test between TDDs over different vtrees can be done in polynomial time.

Authors: Matthias Lanzinger

Assuming the Exponential Time Hypothesis (ETH), fixed-parameter tractability and polynomial-time solvability coincide for homomorphism problems specified by classes of pattern hypergraphs of bounded incidence degeneracy or bounded primal independence number. In both cases, tractability is characterised by bounded fractional hypertree width. Grohe (JACM 2007) established the corresponding FPT-PTIME equivalence under bounded arity. Our result allows unbounded arity and covers important cases such as bounded-degree patterns and patterns whose incidence graphs exclude a fixed minor. Building on the recent fractional balanced-separator framework and rounding theorem of Korchemna et al. (FOCS 2024), we prove a near-linear bound on fractional hypertree width ($\mathsf{fhw}$) in terms of adaptive width ($\mathsf{adw}$). For every hypergraph $H$ with $\mathsf{adw}(H)\geq 2$, \[ \mathsf{fhw}(H)=O\bigl(λ(H)\mathsf{adw}(H)\log\mathsf{adw}(H)\bigr), \] where $λ(H)=\min\{μ(H),\max\{1,\logα(H)\}\}$, with $μ(H)$ denoting incidence degeneracy and $α(H)$ the independence number of the primal graph. As a further consequence, we obtain a corresponding FPT-PTIME collapse for exact homomorphism counting on every bounded-$λ$ class. More generally, for every recursively enumerable class of pattern hypergraphs, fixed-parameter tractability of the parameterised homomorphism problem implies quasipolynomial-time solvability of the corresponding unparameterised problem, assuming ETH.

Authors: Yuki Yonemoto

The satisfiability problem for word equations asks whether variables can be replaced by words so that the two sides become equal. For regular word equations, in which each variable occurs at most once on each side, satisfiability is NP-complete. For general quadratic word equations, in which each variable occurs at most twice in total, satisfiability is NP-hard, but its membership in NP remains open. We consider an intermediate class: quadratic word equations with a linear side, where each variable occurs at most once on one designated side. We show that the Nielsen graph of an equation $U=V$ in this class, with total length $N=|U|+|V|$, has diameter $O(N^{12})$, measured over reachable pairs of vertices. Together with the known NP-hardness for regular word equations, this result establishes NP-completeness of satisfiability for this class.

Authors: Rohit Sarma Sarkar, Rupayan Bhattacharjee, Elias F. Combarro, Michele Grossi, Lirandë Pira, Carmen G. Almudéver, Sergi Abadal, Eduard Alarcon

Quantum Signal Processing is a powerful quantum framework for generating and approximating univariate polynomials. However, QSP is often limited by circuit-depth bottlenecks and parity constraints on the class of realizable polynomials. In this work, we introduce Weighted Quantum Signal Processing, an extension of QSP in which a weight function is assigned to the central rotation operator. This formulation provides a deeper understanding of QSP, which emerges as the special case of WQSP with unit weights. The choice of weights determines the structure and expressive capabilities of WQSP circuits. When the weights are natural numbers greater than one, WQSP reduces to a pruned version of QSP, revealing parameter redundancies in the standard framework. Through appropriate selection of integer weights, WQSP achieves linear-to-exponential reductions in the number of parameters required to realize arbitrary bounded univariate polynomials while preserving approximation quality. For generic weights, we establish corresponding approximation error bounds and show that, in many cases, the approximation is exact. We analyze WQSP from both a deterministic perspective, where polynomial generation is formulated as the solution of a linear system, and a quantum machine learning perspective, where WQSP serves as a structured and expressive quantum learning model. We further employ this learning framework to parameterize learnable activation functions in Kolmogorov--Arnold Networks for multivariate function approximation. Our results show that WQSP provides a compact, flexible, and theoretically grounded framework for realizing arbitrary univariate polynomials while requiring significantly fewer trainable parameters than conventional QSP. This yields expressive and parameter-efficient neural architectures, highlighting the potential of WQSP as a scalable primitive for quantum-enhanced machine learning.

Authors: Minglong Qin, Penghui Yao, Mingnan Zhao, Haigang Zhou

We initiate the study of constructing explicit pseudorandom generators for thresholds of halfspaces with seed length polylogarithmic in the number of halfspaces. This class of functions lies at the frontier of circuit complexity [CTW26]. We show that the generator designed by O'Donnell, Servedio, and Tan for polytopes [OST22] also fools this broader class. To analyze the generator, we develop a threshold-specific smooth approximation framework based on a Bentkus-type mollifier. We prove derivative bounds for this mollifier and also establish a Boolean anticoncentration theorem for thresholds of halfspaces via a random thinning argument. These ingredients imply that the generator $δ$-fools every $k$-out-of-$m$ threshold of $m$ halfspaces over $\{-1,1\}^n$ with seed length $\widetilde{O}(κ^{6+2\varepsilon}\log^{6+2\varepsilon}\!m\cdotδ^{-(2+2\varepsilon)}\log n)$, for any arbitrarily small constant $\varepsilon>0$, where $κ=\min\{k,m-k+1\}$. The random thinning argument also yields bounds on the noise sensitivity and Gaussian surface area for thresholds of halfspaces, leading to learning algorithms under both the uniform and Gaussian distributions.

Authors: Sankeerth Rao Karingula, Shachar Lovett

We give an elementary proof of the Komlós conjecture by simplifying the recent proof of Guo, Fang, and Lu. We show that any vectors $v_1,\ldots,v_n\in\mathbb{R}^d$ with $\|v_i\|_2\le1$ admit signs $\varepsilon_i\in\{-1,1\}$ such that $\|\sum_{i=1}^n\varepsilon_i v_i\|_\infty\le36$. The proof uses only elementary combinatorial and probabilistic arguments and basic calculus.

Authors: Kevin Buchin, Carolin Rehs, Torben Scheele

To speed up algorithms on geometric graphs, it is common to approximate the complete Euclidean graph while maintaining certain geometric properties. A (directed) $t$-spanner $G$ for a point set $P$ in the Euclidean space is a (directed) graph such that for every pair of points, the shortest path in $G$ is at most a factor $t$ longer than the Euclidean distance between those points. In this paper, we investigate $t$-spanners that are bounded by certain graph parameters. Let $κ$ be a graph parameter. We show that for path-width, branch-width and cut-width there is an $\mathcal{O}(n/k^{d/(d-1)})$-spanner $G$ on $P$ with $κ(G)=k$ and that this is asymptotically worst-case optimal. In $\mathbb{R}^2$ we show the same bounds for planar graphs of clique-width or rank-width $k$. In contrast, for tree-depth, we show that there are sets of points for which the dilation cannot be bounded. Therefore, we investigate computing a spanner with tree-depth $k$ and minimum dilation. We show that already for tree-depth $3$ this problem is NP-hard to approximate within any factor strictly less than $\sqrt{2}$, and present an XP-algorithm to compute for a given tree-depth $k$ a graph with dilation at most $2t^*$, where $t^*$ is the minimum dilation. We further extend these results to obtain directed $\mathcal{O}(n/k^{d/(d-1)})$-spanners $G$ with $κ(G)=k$ for $κ$ being directed tree-width, directed path-width or DAG-width and show that also in the directed case, this is asymptotically worst-case optimal.

Authors: Ethan Keller

Moser's worm problem asks for a planar region of least area containing a congruent copy of every unit arc. We show that the infimum area $α$ among convex universal covers satisfies $0.239\leα\le0.24633\ldots$, reducing the gap between the previous refereed bounds by over $75\%$. For the lower bound, we choose four unit polygonal arcs and prove by finite subdivision that, however they are placed, their convex hull has area at least $0.239$. For the upper bound, we construct a quadrilateral of area $0.24633\ldots$ and prove cover universality by showing that its support inequalities force uncovered arcs to have length greater than one. The full proof is formalized in Lean 4 and verified by the Lean kernel. Code and certificates are available at https://github.com/ethan-keller/moser-worm-improved-bounds.

Authors: Paul Duetting, Michal Feldman, Mathieu Molina

We initiate the study of $α$-fair prophet inequalities. This interpolates between utilitarian welfare $(α=0)$, Nash welfare $(α=1)$, and Rawlsian max-min fairness $(α\to\infty)$. Given the non-linearity of the objective, it matters when the expectation is applied. For instance, for the Rawlsian objective, it matters whether we aim to maximize $\min \mathbb{E}[u_i]$ or $\mathbb{E}[\min u_i]$. We refer to the former as the ex-ante model, and the latter as the ex-post model. For ex-ante fairness, full distributional knowledge yields a tight competitive ratio of exactly $1/2$ for every $α\ge 0$. Under sample access, $O(n\log n)$ samples per distribution suffice for a constant competitive ratio when $α\in(0,1]$. In contrast, for every $α>1$, no finite number of samples improves upon the trivial $1/n$ guarantee. Thus, unlike in the utilitarian setting, full-information and sample-access prophet inequalities become fundamentally separated. For ex-post fairness, under full information, we obtain a uniform constant ratio for all $α\in(0,1)$, while for every $α>1$ the competitive ratio collapses to $1/n$. In the sample-access model, one sample per distribution suffices for each fixed $α<1$, but no sample budget depending only on $n$ yields a uniform constant guarantee as $α\to 1$. Beyond these phase transitions for $α$-fairness, our results open the door to a broader theory of prophet inequalities for non-linear welfare objectives.

Authors: Chandra Chekuri, Lars Rohwedder, Neta Singer, Jan Vondrák, Rico Zenklusen

Motivated by applications in fairness and foundational questions, we consider the problem of maximizing a monotone submodular function $f\colon 2^E \rightarrow \mathbb{R}_+$ over maximum cardinality sets in the intersection of two matroids on a common ground set $E$. An important special case is submodular perfect matching in bipartite graphs. Prior to this work, its approximability was poorly understood with only constant inapproximability known, despite not even a $\frac{1}{o(\sqrt{|E|})}$-approximation being known. Even when allowing to violate the cardinality constraint slightly, only a bicriteria approximation with a significant loss in the objective was known. Here, we obtain two results. First, we show that, within constant factors, the problem is approximation-equivalent to Submodular Orienteering in directed graphs. This yields an $Ω(1 / \log |E|)$-approximation in quasi-polynomial time together with an almost-matching hardness result. Second, we obtain an improved polynomial-time bicriteria approximation via a local search framework. More precisely, if $f(T^*)$ is the largest submodular value of a common independent set in both matroids of size at least $K$, we find a common independent set $T$ such that $|T| \geq (1 - ε) K$ and $f(T) \geq (1/2 - ε) f(T^*)$. In contrast, previous work only guarantees a value of $Ω(ε) f(T^*)$ while ensuring that $|T| \geq (1 - ε) K$.

Authors: Yansong Feng, Yiming Gao, Jiaqi Liu

Kannan's algorithm, as analyzed by Hanrot and Stehlé in 2007, solves the exact Euclidean shortest vector problem in polynomial space and $n^{\frac{n}{2e}+o(n)}$ time. In the classical setting with polynomial space, we obtain the first improvement on this bound via a randomized algorithm that runs in $n^{\frac{n}{4e}+o(n)}$ time. The main idea is to represent a fixed shortest vector in many ways as a difference of samples, thereby enabling the low-space collision search of Lyu and Zhu (SODA 2023) to replace exhaustive enumeration in the original analysis.

Authors: Nikhil Bansal, Milind Prabhu, Sahil Singla, Siddharth M. Sundaram

We consider the online carpooling problem, where edges arrive online and must be oriented immediately while keeping the discrepancy between the indegree and outdegree at each vertex small. We prove that the natural Greedy algorithm incurs discrepancy $O(\min\{T^{1/3},n\})$ after $T$ arrivals. This resolves a question of Ajtai et al., who showed that any deterministic algorithm must incur $Ω(\min\{T^{1/3},n\})$ discrepancy, and gave an algorithm with $O(\min\{T^{1/2},n\})$ discrepancy. We also show a similar square-root to cube-root improvement in the stochastic setting, where $O(n)$ edges are sampled independently from an underlying $n$-vertex graph $G$. Formally, we show an $O((\log n)^{1/3})$ bound for random arrivals from any $Δ$-regular graph $G$. When $Δ= Ω((\log n)^3)$, we show the more refined bound of $O((\log n/\log Δ)^{1/3}+\log\log n)$ on the discrepancy. We show that the cube-root term in the previous bound is essential, while the $\log\log n$ term is already known to be necessary for random arrivals from complete graphs. The previous upper bounds here were $O((\log n)^{1/2})$, which follow from the breakthrough works on online discrepancy due to Kulkarni, Reis, and Rothvoss, and Aden-Ali. Our techniques for proving such cube-root-type bounds may be of independent interest, as the standard quadratic-potential and subgaussian analyses underlying the previous general bounds appear inherently unable to go below square-root-type guarantees.

Authors: Tarun Kathuria

Let $A_1,\ldots,A_N$ be positive semidefinite matrices of rank at most $r$, with $\sum_iA_i=I$ and $\|A_i\|\le\varepsilon$. We prove that the original matrices admit signs with discrepancy $O(\sqrt\varepsilon\log(2r))$, independently of their dimension and number which is a significantly stronger result than what was known existentially. We give a deterministic algorithm with polynomial real-arithmetic work, and a separate existence proof requiring no computational assumptions. This extends our companion paper on rank-one Kadison--Singer discrepancy. A concave matrix power interpolates between the trace source, which pays a factor $r$, and the sandwich source, whose density response is harder to control. We prove that source concavity controls this additional response in the same inverse-Sylvester metric as the optimized spectral potential. As an application, a single spanning tree can be chosen simultaneously $O(\varepsilon\log^2(2s))$-spectrally thin for $s$ positive edge weightings of a common graph, provided every edge has leverage at most $\varepsilon$ in every weighting. The reduction preserves one common selection decision per edge. For incidence matrices with at most $t$ ones in every row and column, the diagonal specialization gives a deterministic walk on fractional colorings with discrepancy $O(\sqrt t\log(2t))$. The local-walk mechanism gives both existence and an efficient construction without using the Lovász local lemma. A Lean formalization of our existence proof has been completed and will be released shortly.

Authors: Sotiris Kanellopoulos, Ioannis Koutras, Aris Pagourtzis

We study the problem of computing class probabilities in block-independent disjoint (BID) probabilistic databases. Given the probability with which each block in the database realizes each feasible tuple type, the goal is to compute the probability of a class of worlds specified by a given tuple multiplicity vector, thus grouping together worlds with the same bag (multiset) of realized tuple types. For this problem, we prove $\#\mathsf{P}$-hardness even for very restricted and structured inputs. On the other hand, we show that it admits an FPRAS, as well as $\mathsf{XP}$-time algorithms parameterized by the number of tuple types and the treewidth of an incidence graph modeling the connections between blocks and tuples. Finally, we show that augmenting the problem with certain compatibility constraints between block realizations renders it $\#\mathsf{XLP}$- and $\#\mathsf{XALP}$-hard parameterized by pathwidth and treewidth respectively, ruling out $\mathsf{FPT}$ algorithms under standard assumptions. We leave as an open question whether this also holds in the absence of compatibility constraints.

Authors: Seungbum Jo, Nodari Sitchinava

A search tree on trees (STT) is a data structure for performing a search for a target vertex in a reference tree. A standard binary search tree is a special case of an STT, where the reference tree is a path of totally ordered elements. In this paper, we study the problem of succinct representation of STTs. We consider two cases: (1) general search trees on trees, and (2) Steiner-closed search trees on trees [Bose et al. TALG 2023]. For both cases, we present representations that can be constructed in polynomial time and achieve optimal space up to the lower-order additive terms. We also present data structures for supporting fast traversals of both general and Steiner-closed STTs. For general STTs our data structure still takes optimal space up to lower-order additive terms.

Authors: Lawry Sorenson, Michael Crandall, Eric K. Ringger, Stephen D. Richardson

The Viterbi algorithm has been previously used to perform forced alignment of audio to text to mine training data from online resources. However, many existing implementations have quadratic time and space complexity, scaling poorly to long input sequences. We propose two optimizations to address this issue. First, we apply the Hirschberg algorithm to perform the alignment in place using linear memory. Second, we model the alignment between speech and text as a constrained random walk, allowing us to prune the search space with arbitrary confidence while accounting for transcription errors. The Hirschberg optimization reduces memory usage from 140 GB to 5 MB for three-hour inputs while producing identical alignments in one-third the time of torchaudio when both run on a CPU. We achieve an additional 2x speedup with pruning on inputs longer than 20 minutes while preserving alignment accuracy in more than 98% of tested cases.

Authors: Calum MacRury, Pranav Nuti, Jan Vondrák

In the classical prophet inequality, an algorithm observes a sequence of random variables with known distributions in an online fashion, and it must select one of the random variables with the goal of maximizing the expected value of its selection. The performance of the algorithm is compared to an \textit{omniscient prophet} who observes all of the random variables before having to make its selection. Combinatorial extensions of the classical prophet inequality in which the algorithm gets to pick a subset of the random variables (constrained to belong to some family of feasible sets) have been studied extensively. We study prophet inequalities with a $k$-matchoid constraint (a common generalization of a $k$-matroid intersection constraint and a $k$-bounded hypergraph matching constraint) in two common online arrival models. We give guarantees with respect to the \textit{ex-ante} fractional relaxation of the omniscient prophet, obtaining an ex-ante competitive ratio of $\frac{1}{k+1}$ in the adversarial order case, and $\frac{1-e^{-k}}{k}$ in the random order case. Using the duality framework of Lee and Singla \cite{Lee2018}, this also yields online contention resolution schemes in these settings. Our adversarial-order prophet inequality can be viewed as a generalization of a recent $\frac12$-competitive matroid prophet inequality by Kalantarzadeh and Pashkovich, 2026. This generalization introduces a new framework: coordinated weighted principal partitions across multiple matroids. Our random-order prophet inequality is a generalization of the $k=1$ matroid case of Lee and Singla, 2018. The two results improve previously known competitive ratios for $k$-matroid intersection, which were $\frac{1}{(e+o(1))k}$ and $\frac{1}{k+1}$, respectively.

Authors: Askar Tsyganov, Uliana Parkina, Sergey Samsonov, Maxim Rakhuba

We prove that, over any field, the bilinear complexity of multiplying a $3\times 2$ matrix by a $2\times m$ matrix is strictly greater than $24m/5$. In particular, every exact bilinear algorithm for multiplying a $3\times 2$ matrix by a $2\times 5$ matrix requires at least $25$ multiplications. Together with the Hopcroft-Kerr upper bound, this proves that the $\langle 3,2,5\rangle$ matrix multiplication tensor has rank exactly $25$. The proof has been formally verified in Lean 4, with the formalization available at https://github.com/fallnlove/mm325_proof.

Authors: Moran Feldman, Gregory Kehne, Roie Levin, Sherry Sarkar

We introduce a low-recourse rounding paradigm for packing problems in fully dynamic settings, which we name Dynamic Contention Resolution Schemes (DCRSs). These are dynamic analogs of (Online) Contention Resolution Schemes (or (O)CRSs) for low-recourse dynamic optimization and offer a variety of benefits. Similarly to their offline and online counterparts, DCRSs for different constraints can be combined to obtain DCRSs for the constraints' intersection. Furthermore, together with the Positive Body Chasing framework of Bhattacharya, Buchbinder, Levin, and Saranurak [FOCS 2023], DCRSs imply competitive recourse algorithms for fully dynamic packing problems with submodular objectives: these are algorithms that, for any input sequence, incur recourse that is itself competitive with the best possible recourse for that sequence. We show the existence of $Ω(1)$-balanced and $O(\log \mathrm{rank})$-recourse DCRSs for matroid constraints, and $Ω(1)$-balanced/$O(1)$-recourse DCRSs for matching and knapsack constraints. In particular, these yield the first non-trivial recourse bound for fully dynamic knapsack, as well as the first competitive-recourse algorithm for non-bipartite matching, and both of these apply even to monotone submodular objectives. Beyond our particular results, we view the DCRS framework as a principled step towards mechanizing the relax-and-round paradigm of approximation algorithms in the context of dynamic optimization.

Authors: Tianshun Miao, Yitong Yin

For every fixed activity $λ>0$, we establish three results for the monomer--dimer model on an $n$-vertex simple graph $G$ with $m\ge1$ edges and maximum degree $Δ$. 1. Near-linear mixing and sampling. Single-edge Glauber dynamics has mixing time $O_λ(m[\log^2 n+\log(1/\varepsilon)])$, giving a near-linear-time approximate sampler. 2. Work-efficient parallel sampling. We simulate the same Glauber dynamics in parallel using $\tilde{O}_λ(m+n)$ work and $\tilde{O}_λ(\min\{Δ,m^{1/3},\sqrt n\})$ depth with high probability. 3. Fast approximate counting. We estimate the partition function within relative error $\varepsilon$ in $\tilde{O}_λ(n^2/\varepsilon^2)$ work. For dense graphs with $m=Θ(n^2)$, this is near-linear in the input size. For the mixing theorem, we establish a general log--Sobolev criterion based on field-dynamics spectral stability, with only logarithmic dependence on the inverse occupied-marginal lower bound. Parallelism uses a matching-specific analysis of occupation-interval dependencies. Counting uses monomer-preconditioned Jerrum--Sinclair dynamics, whose parameters are learned efficiently by Glauber dynamics.

Authors: Anish Hebbar, Ravi Kumar, Roie Levin, Joseph, Naor, Debmalya Panigrahi

Suppose an online algorithm is given an unbiased $p$-sample of its input as offline advice; can the algorithm exploit the sample to achieve beyond-worst-case performance? We study this online algorithms with a sample (OAS) model. We show a tight $O\left(\log (1/p) \cdot \log m + \log n\right)$-competitive algorithm for set cover, exponentially improving upon the $O\left(1/p \cdot \log (mn)\right)$ guarantee of Gupta et al. (SODA'24) and answering an open question therein. Our techniques extend to covering integer programs and non-metric facility location, also yielding tight bounds for these problems. Further, we give an $O(\log (1/p)/ \log \log (1/p))$-competitive algorithm for metric facility location, answering an open question of Argue et al. (NeurIPS'22). We then introduce and study the robust variant of the OAS model, in which an adversary is allowed to arbitrarily modify $k$ elements of the $p$-sample. For set cover, covering integer programs, and non-metric facility location, we obtain a tight competitive ratio of $O\left(\log (k/p) \cdot \log m + \log n\right)$. For metric facility location and Steiner tree, we obtain tight competitive ratios of $O\left(\log (k/p) / \log \log (k/p) \right)$ and $O\left(\log (k/p)\right)$ respectively. To the best of our knowledge, these are the first results for robust algorithms in the OAS setting.

The following conversation is fictional.

---------------------------

ALICE: (Looking over a student's record.) Hmm, let's see. She wants to work in quantum computing. She's had the year-long quantum sequence in the physics department and has taken a course in quantum computing in the computer science department. She has done a project in quantum computing in an REU program.  Grades good, letters good. I think we should admit her.

BOB: Wait! Did she get a minor in Physics? This is very important!

--------------------------

When looking over a student's record the questions

Does she have a minor in X? or

Did she double major?  or

Did she graduate with honors? 

never dawn on me.

1) When I am on an admissions committee I look at:

a) Transcript: What did they take? The grades are generally good so that's a minor factor.

b) Letters that tell me what they did within STEM. I don't care about ballroom dancing or moral character. 

c) Papers they've written whether or not they have been published.

d) Their personal statement. They need to tell me:

i) Why they want to get a PhD.  When Ted Kennedy challenged Jimmy Carter for the presidential nomination in 1980, Ted Kennedy was asked Why do you want to be president? See here for his rambling and incoherent answer.

Despite his background in proving lower bounds on approximation contingent on the Unique Games Conjecture, Ted Kennedy would not have gotten into our graduate program.

ii) What they are interested in (this may have been covered in part (i)).

iii) Why they are qualified.

2) Do I care what the major is? No. I care that they know computer science which I can get off of their transcript.

3) Do I care if they double major in (say) Math. No. I can look at the transcript and see what math courses they took.  I don't care what (possibly arbitrary) rules their school has for double majoring.

4) Do I care if they minored in (say) physics? Not even a little. If they want to do quantum computing I care if they have taken courses in that area.  I don't care what (likely arbitrary) rules their school has for minors.  I took five courses in Philosophy as an undergraduate. Did I get a minor? I don't recall.  Two of them were in logic so I don't think I deserve a minor.

5) Are they in their school's CS honors program? Some other honor program? Are they on track to graduate with CS honors? Some other honors?  I don't care what (definitely arbitrary) rules their school has for honors programs.  If they are writing a paper, honors thesis or not, I will want to hear about it from their letter writer and from their personal statement. 

6) Do I care if they are in phi-beta-kappa? Sigma-Xi? Tau-Beta-Pi?  The last two I only know about since I googled  is there an analog of phi-beta-kappa geared toward STEM  for this post. You can probably guess that I don't care about any of those things. 

7) The point is that these formal criteria: major, minor, honors are not important when I am doing admissions.

a) Are they important to students?

I've heard that high school students who are honors students get a bumper sticker for their parents car that says:

                 My kid is an honors student at blah high school.

I would be more impressed if the bumper sticker said

                 My kid can prove the polynomial van der Waerden theorem.

b) Are they important to other people on the admissions committee?

8) Has the scenario I paint at the beginning of this post ever happened?

By gasarch

Assume indistinguishability obfuscation (iO) and one-way functions, both secure against nonuniform polynomial-size adversaries. We show that no randomized polynomial-size pruning procedure isolates a witness with probability at least a/log L, for any constant a > 0, where L is the length of the circuit description. Dell, Kabanets, van Melkebeek, and Watanabe (DKMW) proved without cryptographic assumptions that success 2/3 + 1/poly(L) implies NP ? P/poly. Under iO alone we get the same collapse from success a/log L, and the guarantee only has to hold on nonempty affine-subspace inputs. The isolator is given no affine basis, it may use the circuit description in any way, and the obfuscator may have negligible correctness error. The reduction hides a known affine subspace inside a larger solution space whose dimension does not depend on the scale being tested. Obfuscation then lets us compare the isolator's output, computationally, with an independent reference output. Along the way we prove an unconditional preprocessing criterion. It characterizes presentation-invariant isolation and, unless NP ? P/poly, gives common and efficiently testable witnesses that a constant-success isolator depends on the presentation. For isolators that see the target only through adaptive membership queries, we determine the optimal tradeoff between queries and success up to absolute constants. Finally, a matching restriction-law construction shows why tests on the planted region stop at the logarithmic scale.

Local LCL properties [Levi, Mosheiff, and Shagrithaya (LMS), FOCS 2025] give a language to express a broad range of linear properties of codes. Subspace design [Guruswami and Xing, 2013] is an elegant property about the linear structure of codes, and it governs important code behavior. In this note, we show that the subspace design property can be phrased as an LCL property. This allows us to recover the recent Goyal, Guruswami, and Hsieh result of constant-alphabet subspace-design codes from the earlier LCL derandomization framework [Jeronimo--Shagrithaya (JS), STOC 2026], with the same coarse alphabet dependence.

We prove that every finite two-player game $G$ with entangled value $\omega^*(G)=1-\epsilon$ satisfies \[ \omega^*(G^{\otimes n}) \le\exp(-\Omega(\frac{\epsilon^3}{\epsilon+ \ell }n)) \] for every $n\ge1$, where $\ell:=\log(|A| |B|)$, and $A$ and $B$ are the answer alphabets. Compared with Chapter 6 of the OpenAI report [Ope26], this improves the gap exponent from thirteen to three and matches the cubic gap dependence in Holenstein's general classical bound [Hol09]: \[ \omega(G^{\otimes n})\le\exp(-\Omega( \frac{ (1-\omega(G))^3}{1+\ell} n)). \] The proof replaces the randomly shifted logarithmic grid used in quantum correlated sampling by smooth soft labels. This makes the relevant label infidelity quadratic in the distance between state descriptions and avoids a Jensen loss when averaging over questions. Together with the postselection argument, these improvements yield the cubic gap dependence stated above.

Let f be a product of D generic linear forms in m variables over a field of characteristic 0, and for integers k, l >= 0 let Gamma_{k,l}(f) = dim S_l * partial^k f be its shifted partial derivative measure, the complexity measure behind the known lower bounds for homogeneous depth-four algebraic circuits. Two universal upper bounds hold for every homogeneous f of degree D: Gamma_{k,l}(f) = 0. For every fixed m >= 3 we prove that for all (k,l) and all D >= D_0(m,k,l) = poly(k,l), a generic product of D linear forms satisfies Gamma_{k,l}(f) = min(N_k N_l, N_{D-k+l}) -- full saturation of the universal cap. For derivative spaces (l = 0) we prove exact equality dim partial^k f = min(N_k, N_{D-k}) for all k = D - D/m, and (once D >= 2m^2) within a factor (2/e)^{m-1}/(2e^2 m) of the cap at every k, via a standalone combinatorial comparison lemma for capped compositions (a Polya-urn coupling plus log-concavity). We also compute exactly, by a filtration calculus, the measure of products with disjoint-pair block structure, and show these are genuinely deficient in the row-dominated regime -- for even m >= 6 and k = l >= m^2, by a factor at least (k/32m)^{(m-4)/2} -- witness choice, not analysis slack, is what previously kept this regime open. The complexity-theoretic reading: against a single product gate of generic linear forms in any fixed number of variables, shifted partial derivatives certify nothing beyond a polynomial degree threshold. This is an exact, per-gate form of the saturation phenomenon underlying the rank-measure barriers of Efremenko-Landsberg-Schenck-Weyman, Efremenko-Garg-Oliveira-Wigderson, and Bhargav-Dutta-Saxena, here established with exact constants in the few-variable, high-degree regime relevant to algebraic hardness-randomness bootstrapping. Characteristic 0 is essential: over small finite fields the evaluation variant of the measure (Armand-Behera-Tavenas, 2026) reverses the polarity. The commutative-algebra reading: we determine the Hilbert function of the ideal generated by partial^k f in each degree k+l -- for f a generic hyperplane multi-arrangement form -- extending the study of apolar algebras of products of linear forms initiated by DiPasquale-Flores-Peterson. The proofs are elementary throughout (no recourse to Froberg-type conjectures or Alexander-Hirschowitz): the main theorem reduces, by an exact "master reduction," to the rank of an explicit Laurent-polynomial family, which is resolved by a zero-multiplicity bound for exponential polynomials, layered confluent and twist Vandermonde arguments, and a residual core lemma valid over any field. Every machine-checkable step of the derivation has been verified exactly (integer or modular arithmetic, multiple primes and seeds), including the full generic-m code path at m = 4, ..., 9.

For several reasons, I have attended very few conferences and workshops for quite a while. However, I made an exception for GandALF 2026, which was held in Aalborg in the period 15-17 September 2026. I am glad that I did so.  

By Luca Aceto

We provide a digest of the paper of Fei and Rubinfeld (arXiv 2026), which provides an alternative analysis of the Bipartite Tester of Goldreich and Ron ({\em Combinatorica}, 1999), which operates in the bounded-degree graph model. Loosely speaking, on input an $n$-vertex graph $G$, the tester selects few vertices, conducts $\tildeO(n^{1/2})$ random walks of polylogarithmic length from each selected vertex, and rejects if and only if an odd cycle is formed by a pair of walks. While the analysis of the foregoing tester in the rapid-mixing case is quite appealing, the original analysis of the general case is quite imposing; it involves the introduction and analysis of Markov Chains that capture the behavior of random walks on a sequence of residual subgraphs that are iteratively defined by the analysis. In contrast, Fei and Rubinfeld avoid this iterative process, and present an analysis that only refers to the random walks on the input graph. More specifically, the original analysis derives a sequence of (non-overlapping) partial 2-partitions of the graph, and stitches them together. In contrast, the new analysis combines a set of ``fractional'' 2-partitions of the entire graph, where the combination is obtained by defining adequate vectors that represent these fractional 2-partitions and employing randomized rounding (a la Goemans and Williamson ({\em JACM}, 1995)). In addition, the new analysis allows for presenting an extremely efficient interactive proof of proximity for Bipartiteness. Such an interactive proof was known before for the rapid-mixing case (Rothblum, Vadhan, and Wigderson ({\em STOC}, 2013)).

For a propositional proof system $\mathcal{P}$ and a polynomial-time function $G: \{0, 1\}^n \to \{0, 1\}^N$ ($N > 10n$), we say that $G$ is a *proof complexity generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the (suitably encoded) statement "$y\not\in\mathrm{Range}(G)$" for every $y \in \{0, 1\}^N$, and $G$ is a *demi-bits generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the statement "$y \not\in\mathrm{Range}(G)$" for a noticeable fraction of $y \in \{0, 1\}^N$. As can be seen from the definitions, proof complexity generators are qualitatively stronger objects than demi-bits generators. Our main result is that, perhaps counter-intuitively, every demi-bits generator "contains" exponentially many proof complexity generators. In fact, a random subset of output bits of a demi-bits generator forms a proof complexity generator with constant probability. This result is an extremely simple corollary of Pajor's Lemma (a strengthening of the well-known Sauer--Shelah Lemma). This result allows us to exhibit the hardness of the Range Avoidance problem ($\text{Avoid}$) in several new, restricted settings of interest: * We show that demi-bits generators computable in $\text{NC}^0$ implies the hardness of $\text{NC}^0$-$\text{Avoid}$ up to constant factors in the stretch, demonstrating a barrier to further improvements on the recent progress on this problem (Korten--Pitassi--Impagliazzo, FOCS'25; Guruswami--Lyu--Yuan, SODA'26). * Given a linear space $V\subseteq \mathrm{GF}(2)^n$ of dimension $k$, the $\text{XOR}$-$\text{Remote-Point}$ problem asks to find a vector far from $V$ (Alon--Panigrahy--Yekhanin, RANDOM'09). Assuming a demi-hardness version of LPN (Learning Parity with Noise), we show that $\text{XOR}$-$\text{Remote-Point}$ cannot be solved by efficient nondeterministic algorithms. * An intriguing challenge in circuit complexity is to build a partial Boolean function on a given domain that has high circuit complexity (Arvind--Srinivasan, ICS'10; Chen--Huang--Li--Ren, STOC'23). Even for hardness against *polynomial-size DNFs*, no efficient algorithm is known for this task. We show that under a version of the random $k$-SAT Hypothesis against $\text{AM}$ algorithms, such hard functions cannot be constructed in nondeterministic polynomial time. Along the way, we introduce the notion of *zero-error disperser families* that can transform demi-bits generators into proof complexity generators, and show that this family can be computed by projections (i.e., without any circuit complexity overhead). Using a different instantiation of this family, we construct proof complexity generators from *barely non-trivial* demi-bits generators $G: \{0, 1\}^n \to \{0, 1\}^N$, where the number of hard-to-prove statements of the form "$y \not \in \mathrm{Range}(G)$" just slightly exceeds $2^n$ (which is the number of *false* statements of this form).

Scott’s foreword: I’m extremely grateful to my brilliant colleagues, Pravesh Kothari, Raghu Meka, and Prasad Raghavendra, for sharing the guest post below about how theoretical computer science (and in particlar, the STOC/FOCS/SODA conferences) should evolve to deal with the AI asteroid that’s right now slamming into our field, at least as we human theorists have practiced it since its inception. While Pravesh, Raghu, and Prasad speak only for themselves, not for myself and not for the theory community as a whole, I found their proposal of a separate “conceptual track” to be an excellent starting point for further discussion. –SA

Considering the pace of developments in AI theorem provers, most would concede that the following scenario is at least plausible in the very near future:

AI theorem provers could prove well-specified mathematical claims, even many well-studied ones that have been open for years, in a matter of hours. Moreover, these systems could be widely available to consumers at nominal cost.

As TCS researchers, let us pretend that the above scenario has come to the fore, and ask ourselves: What is our role in such a world? Does it mean the end of theory research?

As we ponder this question, let us ignore all of these other confounders:

1. Recent controversies surrounding the developments on the Millennium Prize Problems
2. Motivations and actions of the AI companies
3. Observed faults in existing AI systems when it comes to writing, exposition or attribution to previous work.

None of the above confounders have any impact on our answer to the question: What should theorists do, in the presence of superhuman AI theorem provers?

Notice that we use the term “AI theorem provers” instead of just “AI”. We believe that this conceptual distinction is important as we consider this question.

At the outset, we would like to admit that for a generation of theorists like us (and many from earlier), research was mainly centered around problem-solving. Even when we developed conceptual insights, it was mostly in service of answering well-specified long-standing questions. We don’t intend this proposal as judging one form of research to be better than others; it only reflects that AI theorem provers accelerate a certain type of research activity and want to make the best of it. There is also a tremendous human cost of this upheaval, which is perhaps a more important question, and one which this proposal does not address directly (we do not have any good ideas as such). Similar points have also been made in various contexts
before, but the timing now is more pressing.

Definitions, Questions & Theories:

The goal of any theoretical science is to advance human understanding of observed phenomena. Apart from theorems and proofs, a theoretical science has definitions, questions, and theories.

Definitions identify the objects to observe. Curiosity and context drive the questions to ask. Theories explain the phenomena observed. We believe humans will continue to play a central role in generating definitions, questions & theories, even in the presence of a super-human AI theorem prover.

Definitions: Could an AI define randomness extractors, streaming algorithms, or zero-knowledge proofs? Maybe. But there are some reasons to believe, humans will still have a big role to play in coming up with definitions.

For instance, the notion of extractors arises from the real-world problem of lacking perfect random sources. Zero-knowledge proofs seem to arise purely out of human curiosity, guided by taste. Human context and curiosity will continue to drive theoretical research. After all, we get to decide what objects we choose to observe!

Theories: Consider the following thought experiment. Suppose in 1965, we had a magic machine that at the press of a button, given any computational problem, would tell us if it had a polynomial-time algorithm or not.

Would that have been the end of computational complexity theory? No. Humans would find it entirely unsatisfactory, and ask, why do these problems not have a polynomial-time algorithm? Why do these others have?

The theory of NP-completeness identifies some patterns among problems that don’t seem to have efficient algorithms. This theory would still be a crown jewel of theoretical computer science, even in a world where we had a magic machine to tell if a problem had an efficient algorithm or not, at the press of a button. Similarly, if we had a machine to predict whether a CSP is NP-complete or in P, we would then ask: what makes 3-SAT NP-complete, while 2-SAT is in P? This question leads to the theory of polymorphisms, which yields a satisfactory answer.

Theories aren’t just succinct or efficient mechanisms to answer questions. The best theories provide are those which humans deem to be a “satisfactory explanation” – whatever that means.

Finally, even as the capabilities of AI theorem provers advance, human curiosity will probe grander and deeper questions. Previously, even if we wanted to build new models and theories, proving something about them was a prerequisite, and given that the grand questions were already at the limit in long-studied domains, we had to scale things down. If each theorem proven by AI is treated as an experimental datapoint, humans can ask grander questions that look for patterns across these theorems.

A concrete proposal:

We think theorists should embrace these AI theorem provers in our research. To a certain extent this is already happening explicitly or implicitly.

As theorists, we have been parsimonious in introducing new models or asking entirely new questions, and careful about adopting new ones too quickly. This was partly because formally proving the properties of a new definition or a model was an onerous task that could take a decade, and tens of papers. AI theorem provers might completely change this dynamic. This is precisely the moment to refocus our work on definitions, questions, and theories. We need explicit systems to encourage and reinforce these parts of theoretical research. You might also say the next generation of AI models can do this; it may be so, but we believe you have to take the current opportunity.

To this end, we suggest that STOC/FOCS/SODA create a separate track of papers. This track is meant specifically for papers that introduce new definitions, ask novel questions or build explanatory theories. The papers in this track are short, say less than 10 pages. Papers may, and should, contain theorems as usual and as needed. Most importantly, the radical shift is that the papers need not contain the proofs of the theorems. Instead, the authors supply a Lean certificate as a supplement to the paper. The evaluation will also in a sense “orthogonalize’’ against the difficulty of these proofs.

The papers in this track should be judged exclusively on the conceptual merits, completely agnostic to the difficulty of the proofs.

Reviewing must be completely agnostic to the proof for two reasons. The main track at STOC/FOCS already includes papers in the former category. Second, a major barrier to producing truly novel conceptual papers is that they often get judged poorly for a lack of technical depth in their proofs. We think these two aspects separate it from (ITCS/SOSA) and, regardless, it’s something we urgently need for all our conferences, including STOC/FOCS (the ‘flagship’ conferences).

To be clear, we ourselves admit that we need to hone these skills of making new definitions, asking deep and interesting questions or building new theories. A separate track of conceptual papers will provide a systematic mechanism for both junior and senior researchers, and the field as a whole to do so.

We believe that upcoming generations of grad students will tackle research directions that seemed completely out of reach to us. We just need to set up systems that nurture new ways of doing research in theory.

— Pravesh Kothari, Raghu Meka, Prasad Raghavendra.

By Scott

Applications are invited for a postdoctoral position in Dean Doron’s group at Ben-Gurion University, supported by an ERC Starting Grant. Candidates interested in complexity theory and pseudorandomness, broadly construed, are welcome to apply.
Further details and application instructions are available on the website. You are also welcome to contact me with any questions before applying.

Website: https://deandoron.github.io/#derand
Email: deand@bgu.ac.il

By shacharlovett

We introduce and study a new model of decision trees that lies at the frontier of provable circuit lower bounds. We study $\ell$-local decision trees, in which each internal node queries an $\ell$-local function of the input. We show that sufficiently strong lower bounds for $\ell$-local decision trees would imply several breakthrough circuit lower bounds, including super-linear size lower bounds for log-depth circuits and improved bounds for unrestricted-depth circuits. Previously, such consequences were known to follow from strong lower bounds for depth-$3$ circuits, which has been the main prior approach in attempting to prove these results. Since local decision trees are strictly weaker than depth-$3$ circuits, this provides a formally easier route to the same circuit lower-bound consequences. We prove essentially optimal lower bounds for a weaker variant that we call oblivious $\ell$-local decision trees, where all nodes at the same depth query the same function. Our lower bounds follow from a new technique that uncovers sumset structure in local maps, and our hard functions are sumset dispersers, sumset condensers, and directional affine dispersers. Along the way, we give an explicit construction of a sumset condenser with small entropy loss. As an additional contribution, we initiate the study of degree-$2$ decision trees, in which each query is a quadratic polynomial of the input. We show that proving lower bounds in this model is a natural stepping stone toward constructing dispersers for degree-$2$ variety sources, which imply improved circuit lower bounds for unrestricted depth circuits. We prove nearly maximal lower bounds for the oblivious variant of the model.

Private information retrieval (PIR) inherently requires public-key cryptography. A recent line of work suggests that this barrier can be avoided in secret-key PIR, where the client first preprocesses an N-bit database and retains only a short secret key. This line of work has yielded communication O(N^\epsilon) for any constant \epsilon under the Learning Parity with Noise (LPN) assumption in a high-noise regime not known to imply public-key cryptography, and communication O(N^{1/2}) under one-way functions. Whether compression beyond N^{1/2} can be achieved without relying on structured assumptions such as LPN has remained open. We show that interaction enables polylogarithmic communication in the random oracle model. We construct a secret-key PIR protocol with O(log N ) rounds and polylogarithmic total communication. Alternatively, for any constant \epsilon, we obtain a constant-round protocol with communication O(N^\epsilon). We also obtain protocols with similar communication in the plain model under the weakest version of LPN, with maximal noise rate 1/2 ? o(1). Our main idea, inspired by the free-XOR technique for circuit garbling, is to make secret-key preprocessing homomorphic under XOR, while relying on security against related-key attacks.

An outstanding open problem asks if there exists a boolean matrix with unbounded sign-rank, but bounded randomised communication complexity. We make progress towards this question by proving lower bounds against real linear sketches (a model weaker than sign-rank): Alice and Bob send few linear measurements to a referee, who makes a decision based on the evaluation of a low-degree polynomial. Our proof uses the Combinatorial Nullstellensatz and the rank method from algebraic circuit complexity.

Hi there, argmin readers! As the fall semester picks up, posting volume will, too. So I’m going to commit to writing short descriptive headers to help you sort through the different threads.

Many readers have asked me to write about AI companies’ conquest of mathematics. Today’s post is a first, but by no means final, attempt at grappling with our new mathematical condition.

Early in my career, I was fortunate to get caught up in a fascinating research frenzy at the intersection of pure and applied math, the compressed sensing gold rush. Compressed sensing asked whether signals could be compressed at the time of measurement. Rather than sampling an image with a high-resolution camera and then compressing it to a JPEG, could we collect a number of samples equal to the number of bytes in the JPEG? Compressed sensing rested on deep mathematics from geometric functional analysis, convex geometry, and probability theory. It yielded multiple engineering artifacts, from faster MRI capture times to better systems for content recommendation.

Though we can see the influence of the field across many applied domains, the math of compressed sensing was never decidedly prescriptive. The theorems always assumed things about reality that couldn’t be verified or required measurement systems that were too costly or impractical. Yet the math of compressed sensing helped us focus on a shared narrative of design principles. It helped us design new algorithms. It helped us construct new measurement schemes that were robust to noise. It helped us map out which other system structures were amenable to compressive techniques. Pure math gave us a frame to see what was possible.

While this mathematical formalism was unreasonably effective, it came with a decidedly unhealthy downside. Shahar Mendelson best described this general problem of applied pure mathematics in a talk he gave at COLT 2014. Applied mathematicians often need to build a giant scaffolding of mathematical modeling to solve a problem. This scaffolding creates new mathematical puzzles that aren’t directly connected to the original problem of interest, but that entice problem solvers. You’ll then see dozens of follow-up papers solving the puzzles but forgetting the problem we cared about in the first place.

This is open problem culture, and it’s corrosive. It leads to trophy hunting, where people race to scoop each other, consult expert friends for secret insights, or steamroll each other with ever more complicated math.

This fetishization of puzzle-solving as genius has long been a destructive tendency in mathematics more broadly. It’s easy to get caught up in the thrill of it. Mathematics is arguably the most meritocratic academic discipline. There are set problems, and the people who solve them are the smart ones. Everyone forgets that the only reason problems confer status is that (a) they are currently unsolved and (b) enough mathematicians have decided these are worth solving. That (b) part is not meritocratic.

This is why many are confused and angry at the practicing mathematicians who try to explain that the discipline of mathematics is about understanding, not proving stuff. To many observers, even those who strive to become mathematicians, math seems set up as a competition from the get-go. It’s rote testing all the way up through college. Ace the SAT as a 7-year-old. Win the IMO gold as a 14-year-old. Max the Putnam Exam as a 19-year-old.

Your reward is the permission to work on whatever puzzles you want, without questions, for the rest of your life. There is no requirement for the winners to explain anything. Maybe they have to teach calculus, but they don’t have to do a good job at it.

From the outside, you can see why people think mathematics is just about winning those competitions and proving what is true. Math doesn’t send many outward signals that “understanding” is a core part of the pursuit. Most people see math as a quiz show culture. Math culture is ruthlessly competitive, and it makes a lot of people feel stupid.

The actions of many notable mathematicians have only lent credibility to their critics. Wars over credit and who gets there first have now ruined two of Clay’s Millennium Problems. This will have to change in light of recent events with AI companies solving math problems few thought they’d be able to. When computers do something we think they wouldn’t, the reaction should not be writing insanely long posts about how Eliezer Yudkowsky was right and the machines are going to kill everyone. Instead, we have to adjust our reference narrative about what we thought was true.

Indeed, I didn’t learn anything about fluid dynamics from OpenAI’s proposed solution to the Clay Millennium Prize Navier-Stokes problem. This problem is exactly the sort of puzzle artifact that I lamented above. The resolution of the Navier-Stokes problem itself tells us nothing about the dynamics of fluids that the equations attempt to model.

That said, I’ve learned a lot from the supposed resolution. I learned that the jump from rote IMO solving to the Millennium Prizes was much shorter than I expected. If you build an algorithm that’s good at solving IMO problems, and you present it with the right ingredients and computational resources, you can solve hard math problems too. That is, a lot of mathematics is training people to benchmaxx. We have already created a battery of tests, carefully tuned with the best psychometrics to find mathematical genius. Training computers to maximize those benchmarks ends up solving the benchmarks. What are millennium problems other than humanity’s final math exam?

This unfortunately makes a lot of sense with the benefit of hindsight!

If this is the lesson, there’s a funny takeaway. While it feels like you need to be an IMO prodigy to set foot in the mathematical arena, being a great IMO solver doesn’t mean you’ll become a great mathematician. For that, you need to bring other talents to bear. Despite the efforts of many smart and caring people, those talents remain ineffable. They certainly aren’t benchmarkable.

In an age of the decidedly anti-intellectual culture of artificial intelligence, mathematicians, both pure and applied, need to keep working to articulate what on earth those talents are. The statements so far, describing how mathematical programs are more than the truth values of their associated theorems, are a good start even if they are not met with universal acclaim. More need to chime in with stories about how mathematics, even the very pure variety, is valuable for scientists, engineers, and everyone else.

I can describe my own experience. Though I’m much less concerned with proving theorems than I was earlier in my career, I still consider myself an applied pure mathematician. Applied mathematics is a formal language that bridges two unbridgeable worlds. Mathematics is a deductive practice that combines axioms via a set of well-specified rules to generate lemmas, theorems, and corollaries. Empirical science and engineering are inductive. We confirm theories when they make correct predictions, willfully committing the logical fallacy of affirming the consequent. This does not make science wrong. It just means, as David Hume told us three hundred years ago, that mathematics can’t justify science.1

Applied mathematics is thus a logical language for describing inductive processes. It’s, um, unreasonably effective at this task. As captured above in my discussion of compressed sensing, it can never perfectly specify what you should do in practice. Instead, it acts as a form of linguistic technical drawing, allowing communities of scientists to build complex theories and engineers to build complex systems. Pure mathematics gives applied mathematicians new pens and brushes for those drawings.

This is why I like (and have been using throughout) Jordan Ellenberg’s term applied pure mathematics. Applied mathematics often just means the mathematics of partial differential equations. Applied pure mathematics is any application of any mathematics to anything outside of the closed world of mathematics itself. You never know which weird corner of the vast libraries of “apparently useless” mathematics will help you make sense of reality.

Let me give an example of unexpected brushwork from my time in the compressed sensing gold rush. Did I need to learn p-adic analysis as an undergrad? Maybe not, but it fixed a set of regularities and patterns in my head. I remembered Bochner’s theorem on locally compact abelian groups when Ali Rahimi and I were trying to make sense of our code generating random features. This turned into a very cool paper with a lot of practical impact. The web of facts I had gathered sitting through weird courses and reading esoteric math books shaped how I saw this applied machine learning problem. AI could likely make that connection today, but my personal education is still needed to create the prompt.

In the first lecture of my first college math course, the legendary Chicago Professor Paul Sally (IYKYK) barked that he wasn’t there to teach us facts, but to fix our brains. Sally dedicated his career to mathematics education, passionately broadening the conception of who could be a mathematician. Math wasn’t a competition for Sally. It was a way of seeing. It still can be, even if our computers now outcompete us.

Subscribe now

By Ben Recht

Authors: Srinivasan Arunachalam, Arkopal Dutt, Sabee Grewal, Aparna Gupte

Gowers, Green, Manners, and Tao (Annals '25) recently resolved Marton's polynomial Freiman-Ruzsa conjecture. We give an algorithmic counterpart to their result: given uniform sampling and membership-oracle access to a set $A \subseteq \mathbb{F}_2^n$ with doubling constant at most $K$, our algorithm outputs a subspace of size at most $|A|$ whose $K^{O(1)}$ translates cover $A$. The algorithm runs in $\textsf{poly}(n,K)$ time. As applications, we obtain polynomial-time algorithms for a variety of learning problems, including quadratic Goldreich-Levin, improper agnostic tomography of stabilizer states, and tomography of quantum states with bounded stabilizer extent.

Authors: Haoyu Wang, Pei Wu

In this paper, we construct a total Boolean function with $\widetilde{O}(\log n)$ randomized communication protocol, while any monochromatic rectangle has density at most $O(2^{-\mathrm{poly}(n)})$. As a corollary, it gives the first total function separation for $\mathrm{BPP}\not\subseteq\mathrm{P}^{\mathrm{NP}}$ in the communication world. Inspired by Gavinsky's recent work (arXiv:2608.18784), our construction combines the cheat-sheet framework with fully linear PCPs.

Authors: Lorenzo Ciardo, Iris Hebbeker, Gideo Joubert, Jana Kreiß, Antoine Mottet

We prove RE-completeness of the quantum homomorphism problem parameterised by families of graphs derived from the classic metric association schemes. These include Kneser graphs, $q$-Kneser graphs, and the complements of Johnson, Grassmann, and Hamming graphs. Our proof develops a spectral method for establishing non-contextuality of quantum polymorphisms. It combines an equality analysis of Roberson's bound on the projective packing number in terms of Schrijver's theta with a structural argument inspired by Erdős-Ko-Rado theory.

Authors: David Miloschewsky, Supartha Podder

Starting from the entrance of a welded tree, a quantum walk algorithm can find its exit vertex exponentially faster than any classical algorithm. However, it has been an open question whether any quantum algorithm is able to efficiently find a path from the entrance to the exit. We answer this by proving an exponential quantum query lower bound for finding such path. Specifically, for trees of height $n$, any quantum query algorithm requires at least $Ω(2^{n/24})$ queries in order to succeed with constant probability. Our proof uses the compressed permutation oracle technique in order to construct databases which track the graph information an algorithm has learned and forgotten, and show that no efficient quantum algorithm can build an entrance-to-exit path in these records.

Authors: Amir Ali Ahmadi, Abraar Chaudhry, Ijay Narang, Yukai Tang

We show that unless P = NP, there cannot be a polynomial-time (or even pseudo-polynomial-time) algorithm for output feedback stabilization of a linear dynamical system with a linear controller. This settles one of the best-known open problems in control theory. The result holds in both continuous and discrete time. We also present a family of stabilizable linear dynamical systems for which no polynomial-time algorithm can write down a stabilizing controller in its standard representation.

Authors: Yimu Qiao, Lijia Yu, Ruichen Qiu, Xiao-Shan Gao

Transformers have emerged as the dominant architecture in sequence modeling, achieving remarkable success in natural language processing and reasoning tasks. While existing literature has established the Turing completeness of transformers under bounded input length, the reasoning power of a single transformer operating on inputs of unbounded length is not fully explored. In this paper, we theoretically investigate the reasoning limitations of a single transformer and the enhanced capabilities of agent systems. We show that a single fixed finite precision transformer cannot memorize certain Turing machines with inputs of arbitrary length, such as the arithmetic; and a single fixed infinite precision transformer trained with a random algorithm is not Turing complete with probability one under reasonable conditions. To overcome the limitation of a single transformer, we define a formal agent architecture consisting of decision, execution, and memory modules and show that for any Turing machine $\mathbb{T}$, there exists an agent that can memorize $\mathbb{T}$ and is computationally the same as $\mathbb{T}$. Thus, agents are Turing complete.

Authors: Yusuke Kobayashi, Bingkai Lin, Joseph Swernofsky

An instance of {\sc Pinwheel Packing} is a list of positive integers $a_1,\ldots,a_k$. A feasible schedule assigns one task to every integer time so that every interval of $a_i$ consecutive times contains task $i$. The instance is \emph{dense} when $\sum_i1/a_i=1$. We prove that {\sc Dense Pinwheel Packing} is NP-complete even when every period is encoded in unary and equal periods are listed as distinct tasks. Consequently, the usual binary-encoded problem is strongly NP-complete. Kleinberg and Mishra also prove NP-completeness \cite[Corollary~5.1]{KleinbergMishra2026}, but their reduction uses periods of exponential numerical size and therefore yields only weak NP-hardness. Our proof uses a direct reduction from triangle partition in a sparse tripartite graph. If each of the three parts of the source graph has $n$ vertices, the reduction produces $O(n^4\log^3 n)$ explicitly listed tasks, each with period $O(n^4\log^3 n)$; consequently, its full unary encoding has length $O(n^8\log^6 n)$.

Authors: Shyamal Patel

We show that there exists a class of boolean functions C such that $(i)$ there is a distribution-independent statistical query algorithm for learning C that makes a polynomial number of queries of inverse polynomial tolerance and $(ii)$ for any set of functions $Φ_1, \dots, Φ_r$ such that for all $f \in$ C we can write $f(x) = \text{sign} \left( \sum_{i = 1}^r w_i Φ_i(x) \right)$ for some set of weights $w_i \in \mathbb{R}$, we must have that $r \geq n^{ω(1)}$. This gives a superpolynomial separation between dimension complexity and the query complexity of distribution-free learning in the statistical query model, negatively answering a question of Feldman, Kamath, and Srebro [FKS26]. Our construction C is a subclass of DNFs, and the proof is a simple consequence of recent progress on agnostically learning conjunctions [DKR25,CPS26] and the work of Razborov and Sherstov on the sign rank of DNFs [RS10].

Authors: Bingkai Lin, Xin Zheng

We study the approximability of \textnormal{\textsc{Set Cover}} parameterized by the target cover size $k$. Let $n$ be the universe size, $m$ the number of available sets, and $|Γ|$ the explicit input length. We prove that, for some absolute constant $c>0$, distinguishing \[ \operatorname{opt}(Γ)\le k \quad\text{from}\quad \operatorname{opt}(Γ)>k\cdot\frac{c\log n}{k^2\log\log n} \] is $\mathsf{W[1]}$-hard. Assuming the Exponential Time Hypothesis, there is also an absolute constant $\varepsilon>0$ for which no deterministic algorithm solves this gap problem in time $f(k)|Γ|^{\varepsilon k}$, for any computable function $f$. For every fixed $α>0$, both hardness results hold even when $n=O((\log m)^{1+α})$, with constants allowed to depend on $α$. For fixed $k$, the gap is within an $O_k(\log\log n)$ factor of the greedy algorithm's guarantee. Under the Strong Exponential Time Hypothesis, we further rule out $o(\log n/\log\log n)$ approximation in time $O(|Γ|^{k-δ})$ for every fixed $k\ge 2$ and $δ>0$. Thus a near-logarithmic hardness factor persists even when the exponent is reduced from exhaustive search by only a fixed constant. The constant in this SETH hardness factor may depend on $k$ and $δ$.

Authors: Zhiyang Dou, Ang Zhao, Chen Peng, Minghao Guo, Haixu Wu, Cheng Lin, Yuan Liu, Junfeng Yao, Xiaohu Guo, Wenping Wang, Wojciech Matusik

Rigid-body interpenetration frequently occurs in procedurally assembled and generated scenes and must be removed before downstream applications such as physical simulation. We present S4R (Scaling for Rigid-Body Interpenetration Resolution), a scale-continuation method for static interpenetration repair. S4R first uniformly shrinks each body about a fixed reference center to a small initial scale, at which the layout is penetration-free, and then restores full scale through a sequence of minimum-norm convex contact quadratic programs (QPs) that target the linearized separation margin during continuation. Resolution thereby replaces one deep correction with a sequence of shallow-contact subproblems. A conservative scale-event bound and frozen-witness gap predictions cut the number of exact mesh queries; the continuation then ends with a full-scale evaluator check and bounded tail refinement. We evaluate S4R on Kubric, HY3D-Bench, and Thingi10K using a shared mesh-level evaluator and a unified per-scene timing protocol. In the main comparisons on all three benchmarks, up to N=5000 bodies, S4R reaches zero reported penetration with displacement that stays small and nearly independent of scene size, and at the lowest wall time within each hardware tier among the compared methods. A GPU implementation extends these results to large-scale scenes. Our code and data can be found on our project page: https://frank-zy-dou.github.io/projects/S4R/index.html.

Authors: Venkatesan Guruswami, Xuandi Ren

We show that $\bigl(\frac{\log n}{\log\log n}\bigr)$-approximate parameterized $k$-SetCover is W[1]-hard, and has no $n^{o(k/\log k)}$-time algorithms under ETH. This improves upon the previous best factors $\bigl(\frac{\log n}{\log\log n}\bigr)^{1/k}$ in (Lin, 2019) and $(\log n)^{1/\operatorname{poly}(k)}$ in (Karthik, Laekhanukit, and Manurangsi, 2019). Here $k$ is the yes-case guarantee and $n$ is the number of candidate sets. While the best approximation ratio is still $O(\log n)$ via the greedy algorithm, closing this $1/k$ gap in the exponent has been a longstanding open problem; we remove this loss via a simple direct reduction. The construction is self-contained and does not rely on the parameterized inapproximability hypothesis (PIH). Starting with sparse parameterized 2-CSP instances (Karthik, Marx, Pilipczuk, and Souza, 2024), we build a monotone CNF formula, which is equivalent to a SetCover instance. To obtain a $k$-versus-$h$ gap, the reduction enumerates all hash functions from $Σ$ to $[2h]$ and all unsatisfiable 2-CSP instances on the same constraint graph with alphabet $[2h]$. For each such instance, it asks for a certificate that the hashed label pairs are not all contained in that instance. Perfect hashing makes this enumeration efficient for $h=\log n/\log\log n$.

Authors: Kristóf Bérczi, Shaddin Dughmi, Vasilis Livanos, José A. Soto, Victor Verdugo

We prove a $1/e$ guarantee for the matroid secretary problem on linear matroids, therefore settling the strong secretary conjecture in this class of matroids. The result holds both when the matroid is known in advance and when a linear representation over a finite field is given online. In the known-matroid model, the result extends more generally to matroids admitting a finitary modular extension. Each element of a fixed optimal basis is selected with probability at least $1/e$. $\mathbf{\text{Concurrent Discovery Disclosure:}}$ The proof of the main result in this manuscript was obtained in a conversation with ChatGPT-6 Astra on Tuesday, September 15, 2026 at 1:02 AM PDT. We then prepared this manuscript for public release, with the intent of uploading it on the morning of Thursday, September 17, 2026. In the early morning hours of September 17, while finalizing the submission, we discovered the manuscript https://arxiv.org/abs/2609.19118 of Abdi, Banihashem, Hajiaghayi, and Mittal, uploaded on September 16, 2026, which contains the same result via an essentially identical approach. We are sharing our manuscript nonetheless in case our exposition is of independent utility to the community, and we hope this experience stimulates broader discussion about concurrent discovery in the AI era.