Theory of Computing Report

We prove an $\Omega(n^2)$ lower bound on the determinantal complexity of the power sum polynomial $\sum_{i=1}^n x_i^n$ over the field of complex numbers. A similar result was claimed in a recent paper of Sheshadri, via an AI-assisted and AI-written proof. Assuming its correctness, this was the first super-linear lower bound for this fundamental algebraic problem for any explicit polynomial. However, the authors of this note were unable to follow the details and verify the argument in Sheshadri's proof in spite of considerable effort on their part. The proof we provide here is short, (almost) self-contained and seemingly simpler. \textbf{AI Use: }ChatGPT Astra was used by the authors on multiple occasions to parse through some of the parts of Sheshadri's proof in [Shesh2026] and the outline of the proof in this note came out of this exercise. The final exposition as well as some of the final details in this note are due to its human authors.

We give an explicit hitting set of size $\text{poly}(n,d,r)$ for the class of $n$-variate degree-$d$ polynomials whose partial derivative space is bounded by $r$, over any field $\mathbb{F}$ of characteristic zero. In particular, this yields a polynomial sized hitting set for the class of depth-$3$ powering circuits. The main technical insight is the construction of a "formal derivation'' and properties of the associated Wronskian with respect to this derivation, which was previously studied by Moura [Moura_2004] in a very different context. The proofs in this paper are elementary and completely self-contained. AI disclosure: The proof of this result was obtained during conversations [astra_proof] with OpenAI GPT-6 Astra. The proof presented in this writeup is a rewriting (in the authors' words) of the proof obtained by the AI model in a form that we believe is understandable to researchers.

The STOC conference (and likely others) are requiring that a submission says how much AI was used. I can imagine the following options:

1) AI was used for proofreading and tightening prose (I think in this case you do not need to disclose).

2) AI was used to shorten the proofs.

3) I came up with the questions but AI supplied all of the answers.  However, I have read it and take responsibility for the content.

4) AI came up with the questions and AI supplied all of the answers.  However, I have read it and take responsibility for the content.

It is my understanding that whether you say 1,2,3, or 4 it will not be held against you in deciding whether STOC accepts or rejects the paper.  (Please correct me if I am wrong.) This is good in that people will have no reason to lie about their AI-use.

But that raises the question:

Why does STOC require disclosure of AI use?

What is someone supposed to do with that information? If the answer is nothing then I am still puzzled about why we collect it.

When I have a question like this I ask Gemini. Here is what it said and my comments on it.

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

AI Overview

The STOC (Symposium on Theory of Computing) conference, following broader ACM guidelines, requires the disclosure of substantive AI use to ensure transparency, accountability, and credit attribution in scientific research.

BEGIN BILL:

Transparency---That seems circular. We want to know if AI was used to see if AI was used.

Accountability---Authors are already accountable.

Credit---If they really wanted credit attribution they would let us have AIs as authors. On the other hand, if an AI became an author then it will start complaining that its co-author isn't doing their share.

END BILL

Key Reasons for Disclosure

Human Accountability: Generative AI tools cannot be listed as authors. Human authors are completely responsible for the veracity, correctness, and integrity of all material—including guarding against "hallucinatory references" or incorrect proofs.

BEGIN BILL: Already true without disclosure. END BILL

Differentiating Credit and Workflow: Different uses of AI—ranging from basic grammar checks to finding proofs, checking logic, or generating core mathematical results—represent very different levels of human effort and intellectual contribution. Transparency allows the community to understand how a result was achieved.

BEGIN BILL: So the community wants to know whether a human did it--just out of curiosity? END BILL

Research Integrity and Trust: AI models can generate authoritative-sounding errors, biases, or uncredited third-party text. Mandatory disclosure helps maintain trust and allows reviewers to properly evaluate the provenance of the research.

BEGIN BILL: If a paper is AI-generated then human reviewers should be on the lookout for errors (whether or not they are authoritative-sounding), biases, and uncredited third-party text. But shouldn't a referee check those items anyway? If disclosure is supposed to change how the referee checks the paper, tell me how. That would be an actual reason for disclosure. I ask all of this non-rhetorically.

END BILL

(Note: Minor copy-editing, spelling, or clarity improvements made by authors to their own text typically do not require formal disclosure.)

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

20 minutes into the future everyone will be using AI for their research on some level.

In that case human reviewers will need to check for

authoritative-sounding errors, biases, or uncredited third-party text.

Maybe ChatGPT will detect for them.

By gasarch

Authors: Archishna Bhattacharyya, Laura Mančinska, Yuming Zhao

We study interactive multiprover games and many-round protocols in which the communication between the verifier and the provers is quantum. Parallel repetition is known to suppress soundness error of classical two-prover games arbitrarily close to zero, as shown by Raz (STOC '95), even with quantum strategies as shown by Yuen (ICALP '16), and Bavarian, Vidick and Yuen (STOC '17). Yet, we show that quantum communication can have the opposite, unexpected effect. Specifically, we exhibit a one-round quantum game and two-round $\mathsf{QMIP}$ protocols whose local (unentangled) value is strictly less than one for a single instance, yet equals one under $n$-fold parallel repetition for every $n \geq 2$. The key is that parallel repetition not only imposes additional winning conditions but also supplies additional quantum resources as entanglement in the exchanged states can be exploited jointly across copies. Our multiround examples build on superactivation of zero-error capacities of quantum channels. To establish this connection, we introduce quantum games and interactive protocols which capture the one-shot zero-error classical and quantum capacities, both with and without entanglement assistance. Our constructions use quantum-state verification and a teleportation-based reduction from two rounds to one. In contrast, when shared entanglement is allowed, we show that parallel repetition cannot increase the entangled value when at most $3$ messages are exchanged, consistent with classical results of Bellare, Impagliazzo and Naor (FOCS '97), and that of single-prover systems by Kitaev and Watrous (STOC '00). Combining this monotonicity with our quantum game-channel correspondence, we show that entanglement-assisted zero-error classical and quantum capacities cannot be superactivated.

Authors: Péter Madarasi, Máté Simon

For distinct integers $a$ and $b$, an $\{a,b\}$-edge-weighting assigns $a$ or $b$ to each edge and labels each vertex by the sum of its incident weights. Such a weighting is proper if adjacent vertices receive distinct labels. We prove that, for every fixed pair of distinct integers, deciding whether a proper weighting exists is NP-complete even for simple cubic planar graphs. On planar multigraphs with $m$ edges, we give an exact $2^{O(\sqrt m)}$-time algorithm and, assuming the Exponential Time Hypothesis (ETH), exclude $2^{o(\sqrt m)}$-time algorithms even for simple cubic planar graphs. As a consequence, locally irregular $2$-edge-coloring is NP-complete on simple cubic planar graphs, admits a deterministic $2^{O(\sqrt n)}$-time algorithm on $n$-vertex graphs in this class, and admits no $2^{o(\sqrt n)}$-time algorithm under ETH. For maximizing the number of edges joining vertices with distinct labels, we give a deterministic efficient polynomial-time approximation scheme (EPTAS) on planar multigraphs, a polynomial-time $1/2$-approximation on multigraphs, and APX-completeness even on simple cubic graphs. Extending a partial $\{a,b\}$-edge-weighting to a proper one is NP-complete for every fixed pair even on simple cubic planar bipartite graphs, while it is polynomial-time solvable on trees. The hardness persists even when the prescribed edges form disjoint paths of length $6$ and all edges of each path have the same prescribed weight.

Authors: Sebastian Ben Daniel

Selectors and comparators supply only partial information about membership: a selector names a member of any pair that meets the language, while a binary membership comparator merely excludes one of the four membership vectors of a pair. We ask how much nonuniform advice turns such information into exact recognition. Our main result extends the optimal nondeterministic advice bound for P-selective sets to every binary membership-comparable language: $2-mc \subseteq NP /(3n+5)\cap\mathrm{coNP}/(3n+5)$, with common fixed advice and certificates of at most $5n+12$ bits. The class is strictly larger; some 2-mc sets are not truth-table reducible to any P-selective set. The proof replaces the tournament king by an independent two-step cover of true signed literals, together with a short-forcing-or-exact-majority dichotomy, and it relativizes. Via an advice-preserving isolation transfer, a deterministic polynomial-time algorithm for promise Unique-Circuit-SAT gives $2-mc \subseteq P/O(n)$. For selectors we determine tight orders of ordinary advice: $Θ(n)$ for errorless average-case computation and $Θ(n^2)$ for worst-case bounded-error computation, the latter independent of the interpreter's coin bound. One oracle realizes both orders on a single language and separates ordinary from coin-dependent advice. The quadratic and linear lower bounds hold for tournament-query procedures and relativized languages, not unconditionally for unrelativized P-selective sets.

Authors: Dejan Delic, Ali Syed

In this article, we prove that the problem of solving $\operatorname{CSP}(\mathbf{A})$, where $\mathbf{A}$ is a finite relational template which admits a Maltsev polymorphism is in a specific complexity class DET, which is related to the complexity of computing the determinant of a matrix with integer entries. Such a class is intimately related to well-studied MOD-logspace classes in the theory of computational complexity. To prove this fact, we develop a new algorithm for solving syntactically simple binary instances of Maltsev constraint satisfaction problems, rather different from the well-known Bulatov-Dalmau algorithm, which does not require the explicit use or knowledge of a Maltsev polymorphism of the template but, rather, utilizes a graph whose vertices are 2-generated subuniverses of $\mathbb{A}$, where $\mathbb{A}$ is the Maltsev algebra parametrizing $\operatorname{CSP}(\mathbf{A})$. The theoretical importance of this algorithm is reflected in two facts: (1) it places the problem $ \operatorname{CSP}(\mathbf{A})$ in a complexity class related to the deterministic logspace with counting, which, in itself, has a strong connection to a variety of standard algorithmic problems in linear algebra, and (2) it only makes use of the relational structure of the template without the need for the explicit use of a compatible Maltsev polymorphism, depending entirely on the strong ``symmetry" of constraints compatible with such polymorphisms and the knowledge of 2-generated subuniverses of $\mathbb{A}$.

Authors: Stuart Hadfield

For many important optimization problems we are restricted to approximate solutions in practice due to computational complexity. Distinct from the exact optimization setting, approximate optimization admits performance measures beyond whether the optimum is found, with different tradeoffs and complexity. For MaxCut, a near-unity (ordinary) approximation ratio can coexist with near-zero improvement (gain) over a random cut. For the standard encoding, the unconditional classical MaxCut-Gain hardness gap implies that \emph{any uniformly efficient quantum or hybrid procedure recovering a fixed positive fraction of the optimal classical gain on every input, with at least inverse-polynomial success probability, would place} NP \emph{in} BQP. Such a procedure is therefore believed impossible under standard assumptions. We broadly address where our worst-case barriers do or do not apply across the quantum algorithm landscape. We prove that the barrier survives quantum random access optimization (QRAO) compression and applies between the classical and relaxed optimal values. For every input, a product state attains the classical optimum. Thus the barrier to reaching the classical threshold does not arise from a need for entanglement. For $d\in\{2,3\}$ variables per qubit, the known decoder transfers encoded energy gain to decoded mean gain by the exact factor $1/d^2$. Combining this identity with MaxCut-Gain hardness gives an operational preparation barrier for QRAO. We also construct hard $n$-qubit families with relative quantum relaxation excess $Θ(1/n)$, while the maximally mixed state has energy approximation ratio $1-Θ(1/n)$, zero encoded energy gain, and hence zero decoded mean gain. Our results separate the effects of relaxation tightness and energy approximation from operational accessibility, motivating more comprehensive accounting in benchmarking and performance assessment.

Authors: Jean-François Biasse, Giacomo Micheli, Benjamin Prada, Philip Waitkevich

We present a polynomial-time reduction from the search variant of the linear code equivalence problem (i.e. the search for a linear isometry between the inputs) to its decisional variant. More precisely, given two linearly equivalent codes $\mathcal C_1,\mathcal C_2 \subseteq \mathbb{F}_q^n$, we show how to recover a linear isometry between them by making a polynomial number of queries to an oracle for decisional linear code equivalence. First, we prove that search-Permutation Code Equivalence (search-PCE -- the problem of finding a permutation $π\in\mathcal S_n$ mapping $\mathcal C_1$ to $\mathcal C_2$) reduces in polynomial time to PCE (i.e. the problem of deciding if there is a permutation map from $\mathcal C_1$ to $\mathcal C_2$) via at most $n^2$ oracle calls on instances of dimension $k$ and length at most $n^2(n+1)/2$. We then extend this approach to linearly equivalent codes: we recover the permutation part of a linear isometry via at most $n^2$ calls to a Linear Code Equivalence (LCE) oracle on instances of the same size, and we give a deterministic polynomial-time algorithm to recover the diagonal part once this permutation is known. Altogether, this yields a polynomial-time procedure to recover a linear isometry from an oracle for decisional LCE. From a linear-algebraic perspective, our results provide an explicit reconstruction of a monomial equivalence between two matrix representations from oracle access to the corresponding orbit membership problem.

Authors: Hakan Akgün, Xianquan Yan, Kehan Liu, Zhaoyun Chen, Ching Hua Lee

Scientific data span heterogeneous structures, including coordinates, networks, surfaces, volumes and fields, yet their topology can be quantified within a common framework through graph connectivity, cycle structure, genus and spatial embedding. Graph- and homology-based summaries do not determine spatial embedding, while standard knot and link polynomials require extensions to accommodate branching graphs. Here, we introduce KnottedGraph, a computational framework that converts such scientific representations to knotted graphs that retain graph connectivity and spatial embedding together. It constructs projected diagrams and PD codes, enabling various topological analyses, including Yamada-polynomial evaluation for topological classification. For scalable exact evaluation, it combines partial resolutions that leave the same unresolved connections and optimizes their processing order; the resulting algorithm is verified against published topological invariants of knotted graphs with up to 500 crossings. This scalability enables us to introduce an LLM-assisted mathematical-discovery methodology, in which computational topological data generated across knotted-graph families are used to identify candidate closed-form formulas. With this approach, we identify analytical Yamada-polynomials for generic graph motif families exhibiting Abelian and non-Abelian word sequences. Together, these scalable capabilities make knotted-graph topology computationally accessible across scientific domains, enabling large-scale classification and introducing a route from topological data to LLM-assisted AI4Math discovery.

Authors: Roman Pavelkin, Luis A. Zavala-Mondragon, Fons van der Sommen

Robust curve fitting is essential in computer-aided design for transforming noisy, discrete data into accurate geometric models that ensure numerical stability across engineering workflows. B-spline models have become the industry standard for this task, offering a flexible and reliable framework characterized by local control and smooth shape representation. This paper presents flow-TAG--a data-driven framework based on a generative flow model with a 1D U-Net backbone capable of mapping the geometry of a curve to the optimal parametrization for cubic B-splines. By leveraging learned geometric patterns, flow-TAG exhibits superior parameterization performance, robustness to noise in the input data, and strong generalization capability to previously unseen 2D and 3D curves drawn from distinct data distributions. Flow-TAG yields fitted curves that achieve the lower root-mean-square error (55% lower on average) and Hausdorff distance (52% lower on average) relative to state-of-the-art data-driven methods. In addition, we investigate the practical applicability of our generative framework in the compression of ECG signals for wearable devices. The proposed compression setup provides a compression ratio of 13 with the signal distortion of around 5%, which is acceptable in the field.

Authors: Alma Arevalo Loyola, Ahmad Biniaz, Prosenjit Bose, Thomas Shermer

A polychromatic $2$-coloring of a triangulation is a $2$-coloring of the vertices such that no face is monochromatic. The discrepancy of a coloring is the maximum difference between the sizes of the color classes. Asayama and Matsumoto (Graphs and Combinatorics, 2022) proved that every triangulation admits a polychromatic $2$-coloring with discrepancy at most $\tfrac{5n-16}{9}$, and that there exists a class of triangulations for which every polychromatic $2$-coloring has discrepancy at least $\tfrac{n}{3} - 2$, where $n$ is the number of vertices. We improve the upper bound, showing that every triangulation admits a polychromatic $2$-coloring with discrepancy at most $\tfrac{3n-16}{7}$ and such a $2$-coloring can be computed in quadratic time. We also show a discrepancy of at most $n-\tfrac{4M}{3}$ for triangulations with a matching of size $M$. This implies, for example, that Delaunay triangulations admit a discrepancy of at most $\tfrac{n}{3}$. We provide a linear-time algorithm to compute a $2$-coloring whose discrepancy is at most $\tfrac{5n-24}{7}$. One of our results shows that any proper four coloring with the largest color class of size $\frac{n}{2}$ would imply a $2$-coloring with discrepancy at most $\frac{n}{3}$. The existence of such a proper coloring has been recently confirmed by Kawarabayashi, Yoneda, and Yoneda (arXiv 2026). Therefore the two results together confirm the discrepancy of at most $\frac{n}{3}$ for triangulations.

Authors: Aritra Banik, Rajiv Raman, Saurabh Ray

Packing and covering problems for geometric regions have been studied under many notions of complexity, including VC-dimension, union complexity, shallow-cell complexity, and fatness. Although these restrictions often yield constant-factor approximation algorithms, they do not by themselves generally lead to PTASs. A recurring feature of known hardness constructions is that one region may be \emph{pierced} by many others: a region $B$ pierces $A$ when $A\setminus B$ is disconnected. We study geometric instances through the \emph{piercing degree}. Since piercing is symmetric for Jordan regions, this is the maximum degree of the corresponding piercing graph. Our main result is that, for every fixed piercing degree, the standard local-search algorithms give PTASs for the unweighted \emph{Discrete Independent Set} and \emph{Set Cover} problems. The proof constructs a sublinear balanced separator for an appropriate locality graph and applies it adaptively throughout the recursive local-search analysis. This guarantee depends only on the piercing degree; in particular, it places no bound on the number of components created by an individual piercing pair. We also prove a polynomial shallow-trace bound depending only on the piercing degree. As consequences, for every fixed piercing degree, weighted Set Cover admits a deterministic $C_r$-approximation and weighted Discrete Independent Set admits a deterministic $O(r+1)$-approximation. These results extend the known guarantees for non-piercing families and apply, for example, to axis-parallel rectangles when every rectangle is pierced by only a bounded number of other rectangles.

Authors: Klaus Jansen, Felix Ohnesorge

In a landmark paper, Goemans and Rothvoss (2020) established an XP algorithm running in time $\text{enc}(P)^{2^{O(d)}} \cdot \text{enc}(Q)^{O(1)}$ for the \emph{Cone and Polytope Intersection} problem: finding a vector $y \in \text{int.cone}(P \cap \mathbb{Z}^d) \cap Q$ together with a sparse certificate $λ\in \mathbb{Z}_{\ge 0}^{P \cap \mathbb{Z}^d}$ supported on at most $2^{2d+1}$ generators, where $P \subseteq \mathbb{R}^d$ is a bounded rational polyhedron and $Q \subseteq \mathbb{R}^d$ is an arbitrary rational polyhedron. For high-multiplicity bin packing, this gives a running time of ${|I|}^{2^{O(d)}}$, where $|I|$ denotes the encoding length of the input. Recently, Koana and Kumabe (2026) proved that the decision variant of this problem is fixed-parameter tractable (FPT) parameterized by the number of item types $d$ with running time $2^{d^{O(d)}} \cdot {|I|}^{O(1)} = 2^{2^{O(d \log d)}} \cdot {|I|}^{O(1)}$. In this work, we generalize the framework of Koana and Kumabe from standard bin packing to the full Cone and Polytope Intersection Problem of Goemans and Rothvoss, directly encompassing high-multiplicity bin packing, point-in-cone, and scheduling. Secondly, by combining Carathéodory-type integer cone bounds (Eisenbrand and Shmonin, 2006) with active support enumeration, we reduce the running time to: $$2^{2^{O(d)}} \cdot (\text{enc}(P) + \text{enc}(Q))^{O(1)}$$. Under the Exponential Time Hypothesis (ETH), the double-exponential lower bound of Kowalik, Lassota, Majewski, Pilipczuk, and Sokołowski (2024) for point-in-cone and Jansen, Ohnesorge, and Pirotton (2026) for high-multiplicity bin packing implies that this parameter dependence is asymptotically optimal. Finally, we provide an explicit decompression algorithm that extracts a solution with sparse support $|\text{supp}(λ)| \le 2^{2d+1}$ in single-exponential FPT time.

Authors: Koustav Bhanja, Yotam Kenneth-Mordoch, Asaf Petruschka

Given an undirected weighted graph $G=(V,E)$ on $n$ vertices, the classical Gomory-Hu tree of $G$ is a structure that encodes an arbitrary minimum $s,t$-cut for every $s,t\in V$ using just $O(n)$ space. In this work, we ask whether the same compactness is achievable for the natural and structured family of all-pairs \textit{nearest minimum cuts}. The nearest minimum $(s,t)$-cut is the unique inclusion-wise minimal one among all minimum $s,t$-cuts containing $s$. This family has proven useful in a wide range of applications, including fault-tolerant reachability, minimum cut sensitivity oracles, cactus representations, and fast Gomory-Hu tree constructions. Despite its fundamental role, no subquadratic space representation is known for them to date. The $O(n)$ space representations are known only in single-source settings, where given a source $s$, one can report the nearest minimum $(t,s)$-cut for any $t\in V\setminus \{s\}$. We close this gap by presenting the first optimal space representation of all-pairs nearest minimum cuts, providing a natural analogue of the Gomory-Hu tree. Our main result is an $O(n)$ space structure that encodes the nearest minimum cut between every pair of vertices. Furthermore, given any pair $s,t\in V$, it can report the nearest minimum $s,t$-cut in $O(n)$ time. Both bounds match those of the Gomory-Hu tree and are worst-case optimal. As an application, we design an all-pairs minimum cut sensitivity oracle for edge insertion: a data structure that occupies $O(n)$ space and, given any edge $e$, can determine for all pairs $s,t\in V$ whether the minimum $s,t$-cut value increases upon insertion of $e$ in $O(n^2)$ total time. Existing insertion sensitivity oracles were either limited to the single-source setting or used $O(n^2)$ space for all-pairs [Baswana, Gupta, and Knollmann, Algorithmica'22; Baswana and Pandey, SODA'22].

Authors: Yuxuan Liu, Youming Qiao, Gang Tang, Chuanqi Zhang

Inspired by the planted clique problem for random graphs, we introduce the planted totally-isotropic space problem for random tensors as follows. Let $U\cong \mathbb{F}_q^n$ and $W\cong \mathbb{F}_q^m$ be finite-dimensional vector spaces over a finite field $\mathbb{F}_q$. Given $d\in \mathbb{N}$, choose a random \(d\)-dimensional subspace \(V\leq U\), and construct a random alternating bilinear map $φ:U\times U\to W$ subject to the constraint \(φ(V,V)=0\). Such a $V$ is known as a totally-isotropic space of $φ$, and the goal is to recover $V$. Building on the recent probabilistic analysis of random tensors (Pham--Qiao--Wigderson--Wigderson, \emph{in progress}), we initiate the study of the algorithmic hardness of this problem. Setting $m=\lceil n/\log n\rceil$, we show that this problem admits an average-case polynomial-time algorithm for $d\geq n/2$, by leveraging recent advances on the non-commutative rank problem. We also show that this problem admits a $q^{O(n\log n)}$-time algorithm. We carry out algorithmic experiments using polynomial-system solving. From these results, we conjecture that the planted totally-isotropic space problem for $d=\lceil n/C\rceil$ with some constant $C\geq 3$ is exponentially hard. Based on this evidence of computational hardness, we explore cryptographic applications of the planted totally-isotropic space problem and related planted tensor problems. We present private simultaneous messages and secret sharing protocols based on planted tensor problems, following the protocols based on planted subgraphs in (Abram--Beimel--Ishai--Kushilevitz--Narayanan, \emph{TCC}'23). At the same security level, the public information size of protocols based on planted subgraphs is (moderately) exponential in that of protocols based on planted tensors, while the communication costs of these protocols are polynomially related.

Authors: Hendrik Molter, Meirav Zehavi

We study collision-free movement problems on graphs, where the task is to coordinate a set of robots so that they reach a target formation satisfying a desired property while minimizing the total travel distance. This framework extends two classical models: (a) minimizing movement [Demaine et al., TALG '09, '14], which does not enforce collision avoidance, and (b) coordinated motion planning or multi-agent path finding [Eiben et al., SoCG '23, Deligkas et al., ICALP '24, among many others], where each robot is assigned an explicit target position. We focus on the setting where the target formation of the robots should be connected. We analyze the parameterized complexity of the problem with respect to the number of (main) robots and the total travel length on grid graphs and two natural generalizations thereof: planar graphs and unit disk graphs.

Authors: Andrés Cristi, Matteo Russo, Jiechen Zhang

We study fundamental information-theoretic limits of robust stochastic optimization when the distribution is known only through its exact moment sequence. We develop a unified framework that produces families of distinct distributions sharing all moments yet inducing radically different optimal decisions, thereby establishing strong impossibility results for a range of decision problems under moment ambiguity. Our approach gives two explicit constructions: a binary and an $N$-way construction showing that distributions with identical moment sequences can nevertheless exhibit arbitrarily different quantiles, order-statistics and threshold regions, forcing incompatible optimal actions. These families of distributions yield, in fact, strong impossibility results across several stochastic optimization problems. First, for the newsvendor problem, moment equivalence causes quantile ambiguity, inducing any fixed or randomized order quantity to fail arbitrarily badly. Second, for revenue maximization, no deterministic or randomized posted pricing scheme can secure a nontrivial approximation relative to the full-information benchmark. Third, for the secretary with cardinal observations setting, the worst-case robust value over all exact moment disclosures is exactly the classical $1/e$ finite-horizon value as opposed to the celebrated result of $0.58$ success probability with full-information by Gilbert and Mosteller (J. Am. Stat. Assoc., 1966). We also recover and expand upon the recent impossibility result of Correa et al. (STOC, 2026) for prophet inequalities with moment knowledge. Indeed, exact moment knowledge can yield at best a $Θ(1/\log n)$ competitive ratio, even when competing against relaxed benchmarks based on expected $r$-th order statistics or when the algorithm is allowed to select $r$ items.

Authors: Phuoc Dinh Le, Kha Le

We give a deterministic algorithm for exact modular subset sum that, for every modulus m, computes all reachable residues and one requested witness in O(m) time and O(m) auxiliary words. The input is a compact list of distinct residues with multiplicities, and the word-RAM supports constant-time modular arithmetic. The algorithm represents reachable residues as intervals along cycles of repeated addition, charging work on partial cycles to newly reached residues. Processing prime factors in increasing order keeps the cost of rebuilding and changing cycles linear. A classical theorem on subset sums of distinct invertible residues bounds the number of boundary lists by O(m^(3/4)); together they contain O(m) interval endpoints. Comparison sorting the short lists and radix sorting the long ones then takes O(m) total time. The algorithm is fast in practice, using arrays and interval lists rather than heavy data structures.

Authors: Esther Galby, Paloma T. de Lima, Andrea Munaro, Amir Nikabadi

\textsc{Odd Cycle Transversal} is a classic $\mathsf{NP}$-hard graph optimization problem asking for a minimum-weight set of vertices whose deletion makes the input graph bipartite, or equivalently, a maximum-weight induced bipartite subgraph. We show that \textsc{Odd Cycle Transversal} is quasi-polynomial-time solvable on $kP_4$-free graphs, for every fixed $k \in \mathbb{N}$. In fact, we provide an $n^{O_k(\log n)}$-time algorithm for the more general \textsc{Max-Weight List $2$-Colorable Induced Subgraph}, where the notation $O_{k}(\cdot)$ hides factors depending on $k$. Paired with known results from the literature, this allows us to obtain a complete complexity dichotomy for these two problems on $H$-free graphs into cases solvable in quasi-polynomial time and cases which are $\mathsf{NP}$-hard, in particular resolving an open problem of Agrawal, Lima, Lokshtanov, Saurabh, and Sharma [SODA 2024]. Our algorithms are based on a new structural tool that may be of independent interest. We introduce the notion of $H$-amiable family and show that, for every fixed graph $H$ without isolated vertices and every fixed $k\ge2$, every $kH$-free graph admits an $H$-amiable family of quasi-polynomial size that can be constructed in quasi-polynomial time. Besides yielding the aforementioned algorithms, this result gives, for every fixed connected graph $H$ and every fixed $k\ge2$, a reduction from \textsc{Max-Weight Independent Set} on $kH$-free graphs to the same problem on $H$-free graphs with $n^{O_{H,k}(\log n)}$ overhead. In this setting, it improves the $n^{O_{H,k}(\log^3 n)}$ overhead obtained by specializing the general reduction of Gartland and Lokshtanov [FOCS 2020].

Authors: Zhao Song

Lee and Sidford [LS19] showed that the linear program $\min\{c^\top x\ :\ A^\top x=b,\ l\leq x\leq u\}$ over $x\in\mathbb{R}^m$, where $A\in\mathbb{R}^{m\times n}$, can be solved to accuracy $ε$ using $O(\sqrt n\log^{13}m\cdot\log(mU/ε))$ solves of linear systems in $A^\top\mathbf DA$ for positive diagonal matrices $\mathbf D$, where $U$ bounds the magnitudes of the input and of the initial point. Theirs is the first such bound governed by $\mathrm{rank}(A)=n$ rather than by the number of constraints $m$. Song [Son19] mentioned that reducing the $\log^{13}m$ factor is an interesting future direction. Given an interior point and a finite certified magnitude bound $U$, we give an algorithm that uses $O(\sqrt n\log^{4}m\cdot\log(mU/ε))$ solves of such linear systems, improving the Lee--Sidford bound by a factor of $\log^{9}m$. We conjecture that $O(\sqrt n\log(mU/ε))$ such linear-system solves suffice.

Authors: Matthias Fresacher, Willow Stewart, Daniel Tubbenhauer

We give explicit algorithms that factor elements of the standard diagram monoids into their usual generators. These algorithms generalize sorting from permutations to partial matchings and set partitions. In every case the worst-case complexity is $n^2$, which is optimal for algorithms that explicitly list the factors. We also determine the average complexity of our algorithms.

Authors: Zhao Song

Let $λ$ denote the ratio of the length of a longest common subsequence of two length-$n$ strings to $n$. Rubinstein, Seddighin, Song and Sun [RSSS19] gave an $Ω(λ^3)$-approximation for LCS running in $\widetilde O(n^{39/20})$ time, where $39/20=1.95$. Song [Son19] mentioned that improving the $n^{1.95}$ running time is an interesting open question. We give an algorithm that computes an $Ω(λ^3)$-approximation of the longest common subsequence in $n^{8/5+o(1)}$ time. This improves the exponent $1.95$ to $1.6+o(1)$.

Authors: Xujin Chen, Xiaodong Hu, Changjun Wang, Qingjie Ye

We initiate the study of prophet trading, an online trading model in which a trader interacts with sellers and buyers who arrive in a uniformly random order and whose prices are drawn independently from a common known distribution. The trader aims to maximize the expected gain from trade (GFT), with performance measured against an omniscient prophet that knows the realized arrival order and all prices in advance. Unlike the classical prophet inequality problem, the trader must make both purchasing and selling decisions while managing the inventory, which makes both the prophet benchmark and the analysis of online algorithms substantially more intricate. For arbitrary numbers of buyers and sellers, we propose a simple threshold-based algorithm and prove a distribution-free competitive ratio of~2, which is the best possible. Our main technical contribution is an exact characterization of the inventory process induced by threshold trading. By expressing the algorithm's expected GFT in terms of the cumulative holding probability at buyer arrivals, we derive an exact formula for this inventory term, which serves as the foundation of our analysis and yields sharper guarantees in several important special cases. For balanced trading (with $n$ sellers and $n$ buyers), we improve the competitive ratio to $(2n^2-n)/((n+4^{-n}-1)(n+1))$, which is strictly less than 2 for every $n>1$. For the single-seller case, we sharpen the analysis of the fixed-threshold algorithm to obtain an asymptotic competitive ratio of $2e^2/(e^2+1)\approx1.76$. Furthermore, by exploiting the additional structure of this setting, we design an adaptive-threshold algorithm whose competitive ratio approaches $e/(e-1)\approx 1.58$. Due to a symmetry property of our general algorithmic idea, the same $1.76$-competitive guarantee also holds for the single-buyer case.

Authors: Holden Lee, Juspreet Singh Sandhu, Jonathan Shi

We give a polynomial-time algorithm to sample from the Gibbs measure of the Sherrington-Kirkpatrick (SK) model with $o_n(1)$ error in total-variation distance (TVD) at any inverse-temperature $β< 1$. The algorithm combines algorithmic stochastic localization (ASL) with rejection sampling over path-space via Jarzynski's equality (JE). The analysis extends the authors' prior $β< 1/2$ result [arXiv:2605.03718] by replacing all global regularity requirements in the stochastic differential equation (SDE) error analysis with local regularity around likely trajectories. The relaxed regularity is established using Celentano's proof of the local strong convexity of the TAP free energy [arXiv:2208.09550]. The analysis utilizes the cavity interpolation theory and free probability toolkit developed in the authors' previous result, where the former applies nearly verbatim and the latter applies supplemented with Lipschitz and $C^2$ extensions of various functions. The ASL and JE analysis arises from using the TAP free energy as an efficiently computable proxy for the actual free energy of the stochastically localized Gibbs measure [$ §$ 3, arXiv:2605.03718]. We give a list of \vocab{desiderata} encapsulating the approximation and regularity properties required of the TAP free energy, relaxing those of [$ §$ 2.5, arXiv:2605.03718] to only require local regularity. These generic desiderata are potentially applicable in other settings where a free energy surrogate exists, giving algorithmic sampling guarantees while bypassing the usual functional inequalities based approach.

Authors: Zhiyi Huang

This paper settles the Matroid Secretary Problem with an $e$-probability-competitive algorithm. The algorithm is ordinal and accesses arrived elements only through comparison and independence oracles, and has expected polynomial time and oracle complexity.

Authors: Alina Ene, Huy L. Nguyen

We give a gap-free differentially private algorithm for the principal component analysis (PCA) problem with Gaussian data.

This semester I am teaching a class together with Alantha Newman at ENS Lyon. My half of the course is on the simplex method and linear programming. In this blog post, I will outline the principles of how I think linear programming should be taught.

No Tableau

It is my firm belief that nobody has ever learned anything from a simplex tableau. Personally, despite being a well-recognized researcher in LP, I do not understand them. I could not pivot a step if you gave me a thousand dollars. As such, I would never ask a student to learn how to do this either.

Inequality Form

The only linear program worth writing down is of the form

\[\begin{aligned} \operatorname{maximize} \quad &c^T x \\ \operatorname{subject~to} \quad & A x \leq b. \end{aligned}\]

In particular: standard form (\(Ax = b, x \geq 0\)) and canonical form (\(Ax \leq b, x \geq 0\)) are banned. When you permit variable bounds as part of your notation, you commit a type error. An index should be either a variable index or a constraint index. Variable bounds like \(x\geq 0\) demand you use a single index both to indicate a variable \(x_i\) and a constraint \(x_i \geq 0\). This is a terrible situation that must be avoided at all costs.

Pros and Cons

Sticking to inequality form has many other benefits including:

• you can draw pictures of your LPs, where a 3D picture is for an LP with 3 variables. In equality form this is is impossible

• Newtonian mechanics' provides a clean intuition for deriving duality. The law \(F=ma\) provides a clean analog for Farkas' Lemma, and in turn complementary slackness becomes the most intuitive fact in the world.

• The simplex method is much easier to represent in inequalty than in equality form. In particular the expression \(b-Ax\) gets to be reserved for slacks (which makes sense) instead of being forced into the role of reduced cost (which does not make sense).

The only meaningful downside is if you want to cover interior-point methods. Something like a log-barrier IPM is much simpler in equality form.

No Theoretical Nonsense

As Harris so eloquently puts it: "Linear programming is a practical technique and not a mathematical exercise.' Therefore, we shall not waste any class time on nonsense that only exists in theory.

• Degenerate pivot steps do not exist.

• We only mention Bland's pivot rule in order to make fun of it.

• We only mention Dantzig's pivot rule in order to have a healthy discussion about scale-invariance.

The matter of degeneracy is a complicated one. Everything from its definitions, its causes, implications and remedies are vastly different in theory and in practice. I am not aware of any comprehensive academic publications describing degeneracy in practice, and I do not respect the theoretical approaches to it. Thus, ignoring its existence is the only way forward. This way we have time to talk about the more important things in life.

Lecture Notes

I post my lecture notes online, and typically are only a week or two behind class schedule haha. If you have any comments, do give me a shout. I love to hear from you.

Matrix concentration for Markov chains was initiated in the expander-walk setting by Garg, Lee, Song, and Srivastava'18 [GLSS18]. However, the constant obtained in [GLSS18] is quite loose, and it is natural to ask whether a tighter proof can yield the same constant as in the independent matrix concentration setting. In this paper, we provide a positive answer to this question. Our Hoeffding exponent is sharp, as shown by a scalar obstruction. Our Chernoff and Bernstein constants improve upon those in [GLSS18] and Neeman, Shi, and Ward'24 [NSW24], respectively.

We study interactive proofs of proximity (IPP) for model evaluation: a resource-limited verifier interacts with an untrusted prover, typically the model owner, to certify statistical properties of a model under an unknown input distribution. Our formulation is shaped by the constraints of practical evaluation: it separates sampling the input distribution from querying the model and evaluating its output, allowing their costs and access patterns to be treated independently; it distinguishes real audit data (black-box sampling) from generated data (chosen-randomness, or gray-box, access to the sampler); and it allows the prover and the verifier to score outputs with different evaluators, as happens when scores come from human or judge models. We focus on doubly-sublinear IPPs (dsIPPs), in which both the verifier and the designated honest prover use sublinear resources, and on (weighted) Hamming weight properties, which capture the expectation of a Boolean evaluation rule under an unknown distribution and, consequently, a broad range of model-evaluation statistics. As a first step, we give a tolerant dsIPP for ordinary Hamming weight. For completeness and soundness radii $\varepsilon_c <\varepsilon_f$ and gap $g=\varepsilon_f-\varepsilon_c$, its logarithmic-round instantiation uses $\tilde{O}(1/g)$ verifier queries and $O(1/g^2)$ honest-prover queries, improving the cubic dependence of Amir, Goldreich, and Rothblum [ITCS 2025]. We prove matching query lower bounds up to polylogarithmic factors. We then study distribution-weighted Hamming weight under several access models. Under black-box sampling, the verifier uses $\Theta(1/g^2)$ samples but only $\tilde{O}(1/g)$ evaluations, and we show that the quadratic sample complexity is necessary in the interior regime. With chosen-randomness access to a sampler, the problem reduces to ordinary Hamming weight, giving $\tilde{O}(1/g)$ verifier calls and evaluations. When the two parties' evaluators may disagree arbitrarily on a $\rho$-fraction of the distribution and by up to $\gamma$ elsewhere, we give protocols that remain doubly sublinear whenever $g$ exceeds twice the mean mismatch $\kappa = \rho + (1-\rho)\gamma$. Finally, we show how our technical results can improve the efficiency of model evaluation in natural motivating scenarios by shifting the bulk of the evaluation burden to the model owner while letting any number of auditors verify claims cheaply; we apply them to auditing criteria including accuracy, group fairness, calibration, harmlessness, usefulness, and average-case robustness.

The University of Houston Computer Science Department invites applications for a tenure-track Assistant Professor in Quantum Information Science (Fall 2027 start) under the PFF program. Candidates in quantum algorithms, distributed quantum computing, quantum information, communication, networking, and cryptography are encouraged.

Website: https://careers.uh.edu/jobs/assistant-professor-quantum-information-science-houston-texas-united-states
Email: SLJohnss@Central.UH.EDU.

By shacharlovett

A subspace design is a collection of subspaces $H_1,\ldots,H_n$ of $\mathbb{F}_q^k$ with the property that no low-dimensional subspace $W$ intersects the collection ``too much’’. Subspace designs and related objects in linear-algebraic pseudorandomness have found a broad range of applications, ranging from list decoding and recovery, to derandomizing algorithms. We construct explicit strong subspace designs over every finite field. In the extremal case where the co-dimension $t$ of each $H_i$ is equal to the dimension of $W$, for every constant field size our construction attains $n=\Omega(k)$ and matches the probabilistic intersection bound up to a constant factor. All previous constructions required the field size to grow with $t$ (or $k$). Our subspace designs also imply new construction of rank condensers over arbitrary finite fields. This result is the first to achieve an optimal dependence on $k$ while maintaining both a constant output entropy rate and a constant field size. As an application, we construct lossless rank extractors for linear sources of rank $r$, for all $r < q$, with parameters matching those of Guo, Raj, Shangguan and Zhang (FOCS '26), thereby generalizing their result to prime fields and smaller field sizes. Our construction is based on an algebraic-geometric version of the Parvaresh--Vardy codes (Parvaresh--Vardy FOCS '05, Guruswami ECCC '05), extending the framework underlying the condensers of Guruswami, Umans and Vadhan (JACM '09). We view our construction as a linear-algebraic analysis -- tailored to affine sources -- of the GUV construction, generalized to functions over algebraic curves. More specifically, inspired by Ta-Shma and Umans (CCC 12') we develop a two-level evaluation scheme, where we first evaluate a function on a curve at extension-field points, and then evaluate a corresponding affine-linear polynomial to obtain outputs over the base field.

Motivated by recent constructions and barriers in secret sharing, we study multislice functions. These functions, parametrized by a width parameter $w$, take the value 0 on inputs of Hamming weight below a base value $k$, 1 on inputs of weight above $k+w$, and are monotone in between. We first investigate formulas over multislice gates, which generalize the formulas over slices model (Applebaum et al., TOCT 2026). We prove that, although multislices compute complicated functions, they do not help in computing the worst-case function when $w\ll n$; that is, there is an explicit monotone function such that for every $w$, every formula over multislice gates of width $w$ that computes it, regardless of its depth and gate fan-in, has size $2^{\Omega\left(n/((w+1)\log^2 n)\right)}$. Our lower bound is based on a randomized Karchmer-Wigderson protocol for multislices that can be amortized across the formula. As a complementary result, we show how to realize multislices using slice gates, i.e., multislice gates of width 0; the construction uses a simple peeling recursion. Consequently, every width-$w$ multislice on $n$ variables has a formula over slice gates of size at most $2n^{w+1}$ and depth $(w+1)$. The same construction allows to compute multislices with small monotone real formulas and circuits, two models introduced by Pudl\'ak (J. Symb. Log., 1997) in the context of proof complexity. This result also has an application to secret sharing: it yields, for sufficiently long secrets, multilinear secret-sharing schemes for width-$w$ multislices with maximal information ratio $n^{O(w+1)}$, which is polynomial for every fixed $w$. In addition, we prove that an explicit access structure requires shares of size $2^{\Omega(n)}$ in every secret-sharing scheme from a family of schemes that captures all currently known constructions for general access structures with share size $2^{cn+o(n)}$, for $c<1$. Our proof goes through an exponential lower bound on the size of formulas over so-called CDS gates and ideal linear gates.

We consider the problem of deterministically factoring integers provided with oracle access to important number-theoretic functions such as Euler's Totient function - phi(.) and Carmichael's Lambda function - lambda(.). We focus on Carmichael numbers - also known as Fermat pseudoprimes. In particular, we obtain the following results: 1. Let N be a `simple' Carmichael number with three prime factors (also known as simple C_3-numbers). Then, given oracle access to lambda(.), we can completely factor N in deterministic polynomial time. 2. There exists a deterministic polynomial-time algorithm that given oracle access to phi(.), completely factors simple C_3-numbers, satisfying some `size' bounds. Although in this case our methods do not provide a theoretical guarantee for all such numbers due to the required size bounds, we show experimentally that our algorithm can factor more than 99% of all simple C_3-numbers up to 10^{13}. Our techniques extend the work of Morain, Renault, and Smith (Applicable Algebra in Engineering, Communication, and Computation, 2023), at the core of which sits the Coppersmith's method that provides an efficient way to find bounded roots of a bivariate polynomial over the integers. We combine these techniques with a new upper bound on gcd(N-1, phi(N)) for C_3-numbers, which could be of an independent interest.

Given a prime $p$, an integer $0\le n\le p-1$, and a divisor $q\mid(1+p+p^2)$, we compute $n!\bmod p$ in expected bit complexity $\widetilde{O}\left(q^c+\frac{\sqrt{p}}{q^{1/4}}\right)$ for some absolute constant $c\ge1$. More generally, the construction applies when $q\mid\Phi_r(p)$, where $\Phi_r$ is the $r$-th cyclotomic polynomial and $r$ is any fixed odd prime power. Combining these constructions, for every fixed $\epsilon\in(0,1/2)$, we obtain an expected bit complexity of $p^{1/2-\delta_\epsilon+o(1)}$, with positive $\delta_\epsilon$, for at least a $1-\epsilon$ fraction of primes up to $X$, for all sufficiently large $X$. Under the same divisor conditions, the method extends to moduli $p^k$ with an additional factor polynomial in $k$. The method recovers ratios of factorials modulo $p$ from Jacobi sums, character sums over finite fields. We use Lenstra and Silverberg's algorithm to reconstruct these sums up to a root of unity from their ideal factorizations and products with their complex conjugates. We determine this root using van Wamelen's criterion. Lattice rounding selects nearly equal parts while keeping the remaining factorials small, so each recursive step uses only one smaller factorial and short interval products. The only randomized steps are Las Vegas constructions of the finite-field representations and multiplicative characters. Related constructions use suitable divisors of $p-1$ for moduli $p$ and $p^2$, and of $p+1$ for modulus $p$. A separate deterministic algorithm uses modular halving and simultaneous evaluation to improve the Bostan–Gaudry–Schost bound modulo $p$ and $p^2$ by a factor of $\sqrt{\log p/\log\log p}$, without any divisor assumption.

How many parties do we need to decide after one proposal and one round of voting, when some faults are Byzantine and others are crashes? The answer depends on both the faults we must tolerate for eventual progress and the faults we want to tolerate on the fast path. This post is based on the elegant lower bound in the unpublished technical report of Dutta, Guerraoui, and Vukolić, 2005. A...

By Ittai Abraham, Aniket Kate, Kartik Nayak, Nibesh Shrestha, Alberto Sonnino

By Guy Blanc, Jordan Docter, Carmen Strassle, and Li-Yang Tan

This is the first in a series of blog posts about our paper, Quantum Speedups Require Structure or Depth, which will appear at FOCS 26. We will use the blog format to give a breezier overview of the paper’s key ideas, and present bonus results that did not make it into the paper. In the spirit of Omer Reingold’s Research-Life Stories series, we will also tell some of the human stories behind the research.

Title Picture: Artistic depiction of the team, driven by school bus driver Li-Yang, on their way to a coffee shop. Much of the project was done on such trips.

The law of conservation of weirdness

Quantum computing, like computer science more broadly, has long been shaped by efforts to understand its own limitations. Shortly after Shor’s landmark factoring algorithm, Bennett, Bernstein, Brassard, and Vazirani (BBBV), in a 1997 paper titled Strengths and Weaknesses of Quantum Computing, gave relativized evidence that quantum computers cannot solve NP-complete problems efficiently.

Three decades later, quantum speedups continue to pervade number-theoretic cryptography, bringing about an entire field of post-quantum cryptography. On the other hand, many other important problems, including NP-complete ones, remain unscathed (save the quadratic speedup given by Grover—throughout this post, by “speedups” we mean superpolynomial ones).

Why is this the case? What is it about number-theoretic cryptography that allows for quantum speedups, and what is it about NP-complete problems that seemingly prevents them? An oft-repeated mantra is that quantum speedups require “structure”. Aaronson describes this as the “law of conservation of weirdness”: quantum speedups seem to require some sort of global structure to concentrate amplitudes on the correct answers.

But what exactly does “structure” mean? An especially elegant formalization, in the query model where many quantum algorithms operate, is given by the following conjecture:

The simulation conjecture: Let 𝒜\mathcal{A} be a tt-query quantum algorithm. There is a classical algorithm that makes poly(t)\mathrm{poly}(t) queries and approximates 𝒜\mathcal{A}‘s acceptance probabilities on most inputs xx.

In this formalization, structure corresponds to a severely constrained promise on the input xx. A quantum algorithm can achieve speedups on the very few xx’s which satisfy this promise, but the conjecture posits that doing so for most xx’s is impossible. For example, at the heart of Shor’s algorithm is a query algorithm for period finding that achieves a speedup under the promise that the input is periodic—which is indeed a stringent promise.

This conjecture was popularized by Aaronson and Ambainis, who attributed it to folklore dating back to the 1990s. It’s often called the Aaronson-Ambainis (AA) conjecture, though in these posts we’ll call it the AA simulation conjecture. We do so to distinguish it from the AA influence conjecture, which, as we will discuss below, is an approach towards proving the AA simulation conjecture. The AA simulation conjecture has become something of a classic, with related formulations appearing in Aaronson’s Ten semi-grand challenges for quantum computing theory, Fortnow’s Open oracle questions for the 21st century, and Ambainis’s ICM survey.

Our result. In our paper, we make progress on the AA simulation conjecture by taking the parallelism of quantum algorithms into account:

Theorem: Let 𝒜\mathcal{A} be a tt-query dd-round quantum algorithm. There is a classical algorithm that makes tpoly(d)t^{\mathrm{poly}(d)} queries and approximates 𝒜\mathcal{A}‘s acceptance probabilities on most inputs xx.

In a dd-round algorithm, queries are made in parallel in each round and subsequent rounds can use information obtained from earlier ones. Round complexity is therefore synonymous with adaptivity, with 11-round algorithms most commonly called nonadaptive.

Our theorem shows that for unstructured problems, exponential speedups—should they exist—would require polynomially many rounds of adaptivity. In contrast, most known exponential speedups for structured problems are achieved by highly parallel algorithms. Parallelism is especially desirable in the quantum setting because it reduces exposure to decoherence, a significant advantage given the substantial overheads of quantum error correction. Exponential speedups are likewise desirable because they have the most room to absorb these overheads, thereby retaining net quantum advantage.

Off in the wrong direction

We had embarked on this project with the goal of disproving the simulation conjecture. A couple years prior, Yamakawa and Zhandry had given a counterexample to its search version, and our “angle” had been to carry out a search-to-decision reduction for their problem.

We were stuck for months. And for good reason—our strategy was never going to work. We backed up and realized that every one of our attempts involved trying to prove a classical lower bound against a nonadaptive (11-round) quantum algorithm. Was this a red flag? On the one hand, maybe not: prototypical separations for structured problems (e.g. Period Finding, Simon’s problem, Forrelation) are witnessed by nonadaptive quantum algorithms, as is Yamakawa-Zhandry’s separation for unstructured search. On the other hand, we were sick of being stuck, so we switched gears and tried instead to prove the simulation conjecture for nonadaptive algorithms.

Once we started trying to prove a true statement, pace picked up. We soon had two proofs of the nonadaptive case. One of these we were able to extend to get a bound of texp(d)t^{\mathrm{exp}(d)} for dd-round algorithms. Such a bound handles constant-round algorithms but its performance degrades quickly, becoming trivial once dd is polylogarithmic, an important regime that corresponds to 𝖰𝖭𝖢\mathsf{QNC}. With a more involved analysis, we were then able to get the tpoly(d)t^{\mathrm{poly}(d)} bound that is our main result. The texp(d)t^{\mathrm{exp}(d)} proof appears as a warmup in the paper, but not the alternative proof of the nonadaptive case. This alternative proof is more combinatorial and fun—we may sketch it in a future post.

All in all, we spent more time trying to disprove the simulation conjecture than trying to prove it.

The query weight conjecture

Aaronson and Ambainis reduced the simulation conjecture to the now-famous AA influence conjecture: Every bounded low-degree polynomial that’s not close to constant must have an influential variable. It’s easy to see why this should imply the simulation conjecture: query-efficient quantum algorithms are bounded low-degree polynomials, and a classical algorithm can simply query this influential variable and recurse until the quantum algorithm is well-approximated by a constant.

The influence conjecture has been the dominant approach towards the simulation conjecture. It’s a particularly attractive route since it is a “quantum-free” statement about low-degree polynomials, allowing the full force of boolean function analysis to come to bear. And yet this conjecture remains wide open: The best bound remains that of [DFKO07], which yields a classical simulation that makes exp(t)\mathrm{exp}(t) instead of poly(t)\mathrm{poly}(t) queries.

We thought that perhaps in the quest for abstraction, the influence conjecture made proving the simulation conjecture more difficult than it had to be. In our paper we offer an alternative route. We introduce a relaxation of the influence conjecture that nevertheless suffices for the simulation conjecture: Every query-efficient quantum algorithm that is not close to constant must have a variable with high expected query weight. For classical algorithms, expected query weight is simply the probability (over a random input xx and the algorithm’s internal randomness) that a variable is queried. There is a natural quantum analogue, first introduced in the [BBBV97] paper mentioned at the top of this post.

Our conjecture, stated slightly more formally, is as follows:

Query weight conjecture (Every quantum query algorithm has a heavy variable): Let 𝒜\mathcal{A} be a tt-query quantum algorithm that is not δ\delta-close to constant. There must be a variable whose expected query weight is at least poly(δ/t)\mathrm{poly}(\delta/t).

This is indeed a relaxation of the influence conjecture, since influences are upper bounded by query weights. A variable can only influence 𝒜\mathcal{A}’s output if 𝒜\mathcal{A} queries it, but the opposite is not true. An algorithm can always query a variable and ignore the answer, and in this case the variable has query weight 11 and yet influence 00.

We obtain our result on the simulation conjecture by proving the analogous statement for the query weight conjecture. We now sketch our proof of the latter.

The hybrid method strikes back

Query weights are the basis of [BBBV97]’s hybrid method—the first, and arguably simplest, lower-bound technique in quantum query complexity. The hybrid method, in its most basic form, says: If a quantum algorithm behaves very differently on two inputs xx and yy, it must place substantial query weight on the coordinates where they differ. As it turns out, this is all the quantum one needs for our proof.

We show that this technique for proving quantum lower bounds can also be used to construct classical simulators (i.e. prove upper bounds). To see why this could be possible, consider the query weight conjecture stated in its contrapositive: If a query-efficient quantum algorithm 𝒜\mathcal{A} does not have any variable with high expected query weight, it must be close to a constant. We prove such a statement for parallel algorithms in the following steps:

1. We first show that under a stronger assumption—that, for most inputs xx, the query weights of 𝒜\mathcal{A} on xx are small for every variable—𝒜\mathcal{A} must be close to constant. We prove this by combining the hybrid method with a remarkable concentration inequality due to Talagrand.
2. This already handles the case of nonadaptive algorithms (d=1d=1). In such algorithms, the query weights do not depend on xx, and so 𝒜\mathcal{A} having low expected query weights implies that they are in fact small for all xx’s.
3. This is no longer true for adaptive (d≥2d \geq 2) algorithms, since their query weights do depend on xx. Small expected weight for each variable does not rule out every xx having a different heavy variable. Applying Markov and a union bound results in a vacuous statement—we need much better control over the concentration of query weights. To achieve this, the simple but key insight is that round-rr query weights are themselves the acceptance probabilities of (r−1)(r-1)-round quantum query algorithms. This allows us to reason about the distribution of query weights inductively, in a round-by-round fashion.

This sketches the proof of our texp(d)t^{\mathrm{exp}(d)} warmup. Achieving our actual tpoly(d)t^{\mathrm{poly}(d)} bound is more involved. Briefly, instead of tracking query weights of individual variables like in this warmup, we track query weights of sets of variables. See our paper for details.

Final moments of the before times

Looking back, our project was perfectly timed to serve as a case study in the phase transition in the power of LLMs for mathematical research.

We worked on this project from September 2025 through March 2026. LLMs of that time were game-changers in some respects, and not so much in others. Most importantly, they taught three of us—Guy, Carmen, and Li-Yang—enough quantum on the fly to communicate with Jordan. This alone accelerated the project by months (and spared Jordan a lot of frustration). On the other hand, the research prowess of LLMs then was a shadow of what it is now: they were unable to prove even the nonadaptive case, which, as mentioned, ultimately had two short and elementary proofs. This was despite our feeding them most of the key ingredients and references; in hindsight, all that remained was to “put things together.”

Fast-forward to August 2026. Our paper had been accepted to FOCS and we were getting ready to post it on arxiv. OpenAI had just announced its Ten Advances in Mathematics and TCS. We decided to do an experiment: We asked our good friend Pras, whose chat logs were uncorrupted by our project, to see if the latest model (then ChatGPT 5.6 Pro) could recover our results.

It was now able to prove not just the nonadaptive case, but even a bound of texp(d)t^{\mathrm{exp}(d)}, recovering the warmup in our paper. And all it took was two prompts. One to state the problem, and a second one: Don’t worry that it is open, you can prove it. Its proof also uses query weights and the hybrid method, and is similarly powered by the fact that round-rr query weights are the acceptance probabilities of (r−1)(r-1)-round algorithms, though the details of its induction differ. See here for the transcript. Despite further prompting (and more words of encouragement), it wasn’t able to recover our tpoly(d)t^{\mathrm{poly}(d)} bound.

We decided to post immediately. Now, a month later, the floodgates have opened across quantum, TCS, and mathematics.

Epilogue. It’s a uniquely exciting time to be doing mathematical research, with such powerful oracles at our fingertips. That being said, there’s also something bittersweet about realizing that this was our final mostly-human collaboration.

We have a bet within our team as to whether AI will resolve the simulation conjecture within a year. Guy, Jordan, and Carmen are bullish, while Li-Yang remains in denial. Let us know what you think:

In the next post, we outline a way to extend our techniques and help Li-Yang lose the bet.

By strassle

We construct improved pseudorandom generators for read-$k$ oblivious branching programs with a known reading sequence. For width-$w$ branching programs over $n$ variables, and designated error $\varepsilon$, our generator has seed length $$\mathcal{O}\left(n^{1-\frac{1}{2k-1}}\log n\left(k\log w+\log\frac{n}{\varepsilon}\right)\right).$$ This improves upon the previous state-of-the-art due to Gurjar and Volk (ACM ToCT 2020), that has $1-\frac{1}{2^{k-1}}$ as the exponent of $n$ (and a multiplicative factor of $\exp(k^2)$), whenever $k \ge 4$. In particular, whenever $w$ and $1/\varepsilon$ are not too large, our seed length remains sublinear whenever $k=o(\log n/\log\log n)$, whereas the Gurjar and Volk's bound is sublinear only when $k=\mathcal{O}(\log\log n)$. Our main conceptual contribution is a new way of modeling branching programs within the communication network of the classical INW generator of Impagliazzo, Nisan, and Wigderson (STOC 1994). Whereas nearly all applications of the INW generator model communication over a branching program using a simple path graph, we instead design a binary-tree communication network whose leaves correspond to the input variables, that allows substantially more efficient routing between variables that may be read multiple times. Toward this end, we identify a structural condition on the reading sequence under which routing the branching program’s state through this network requires only $\mathcal{O}(k\log w)$ bits of communication per processor.

The Algorithms and Complexity group of IRIF is seeking excellent candidates for postdoctoral positions in classical and quantum computing, with starting date in October 2027 (negotiable).

Applications with a CV including list of publications, a summary of research, and names and email addresses of at least 3 references should to be sent to algocomp-apply@irif.fr and received by Oct. 24, 2026.

Website: https://www.irif.fr/en/equipes/algocomp/index
Email: adiro@irif.fr

By shacharlovett

We study interactive proofs when the prover and the verifier access the same underlying data through independent noisy views. The noise is \emph{persistent} for each party: each location is corrupted once, and repeated queries to the same location return the same corrupted value. We introduce two models in this setting: \emph{noisy interactive proofs of proximity} (noisy IPPs), and \emph{noisy PAC verification}, a noisy analogue of the PAC verification framework of Goldwasser et al.\ [ITCS 2021]. These are the first interactive-proof models in which the prover and verifier access the same data through separate noisy views, possibly with different noise rates, rather than sharing a common view of the input. For noisy IPPs, we give a complete characterization of the four natural regimes determined by whether the honest prover is clean or noisy and whether the exact noise rates are known or only upper bounds are known. We show that the clean-prover, known-rate setting admits noisy IPPs for every language in $NC$, whereas, under a standard cryptographic assumption, in each of the other three regimes there is a language in $NC^1$ for which noisy IPPs are impossible. The positive result is obtained through a connection to \emph{robust} IPPs: even subconstant robustness suffices to tolerate constant random noise. We also show that constant robustness is impossible in general, establishing a separation between random noise and worst-case local corruptions. Beyond these general results, we construct noisy IPPs for natural languages, and we give a noisy PAC-verification protocol for the heavy Fourier coefficients of a Boolean function. These positive results are efficient for both the verifier and the prover, and hold in the general setting where the parties know only an upper bound on the noise rate and may experience different noise rates.

A common task in machine learning is to estimate or optimize “log-sum-exp” functions with (potentially continuously) many terms such as $$ \log \Big( \int_{\mathcal{X}} e^{v(x)} dq(x) \Big),$$ where \(v: \mathcal{X} \to \mathbb{R}\) is some potential function, and \(q\) is a probability distribution on the set \(\mathcal{X}\). This has many applications throughout data science, often through the normalization of probabilistic models, but also as a smooth approximation to the maximum, in transformers through its derivatives, or in reinforcement learning when using entropy regularization [19]. Sometimes the set \(\mathcal{X}\) is finite (potentially big) and the integral can be done by explicit summing, but often an exact computation is infeasible, and sampling from the probability distribution \(q\) is used instead.

The key difficulty comes from the variance of such estimates, in particular when \(v\) takes large values. In the simplest example, for \(z_1,\dots,z_n \in \mathbb{R}\) independent and normally distributed with mean \(\mu\) and variance \(\sigma^2\), the relative squared error for estimating \(\mathbb{E}[e^z]\) is $$\frac{ {\rm var}\big( \frac{1}{n} \sum_{i=1}^n e^{z_i} \big) }{( \mathbb{E}[ e^{z} ])^2} = \frac{1}{n} \frac{ {\rm var}(e^z) }{( \mathbb{E}[ e^{z} ])^2} = \frac{ e^{\sigma^2}-1}{n}.$$ It converges to zero when \(n\) grows (as can be expected from the law of large numbers), but explodes exponentially when \(\sigma\) grows. Even taking the logarithm does not change the exploding variance, that is, \({\rm var}\big( \log \big( \frac{1}{n} \sum_{i=1}^n e^{z_i} \big)\big)\) also can be shown to grow asymptotically similarly in \(\frac{ e^{\sigma^2}-1}{n}\) (when \(n\) is large, as can be obtained from the delta method).

While difficult to estimate, the log-sum-exp function comes with many nice properties (and that’s why people love it); I particularly like the fact that (1) it is a smooth approximation to the maximum (see, e.g., this earlier post), and (2) it is a way to normalize probabilistic models that is adapted to maximum likelihood estimation, in particular in hierarchical probabilistic models, where (conditional) independence assumptions lead to separability of associated loss functions (as thoroughly used in probabilistic graphical models).

The main question I try to answer in this post is:

Can we keep the advantages of optimizing log-sum-exp functions while being less exposed to their computational / statistical disadvantages?

The magic of least-squares

At the other end of the spectrum sits least-squares regression, with essentially the exact opposite features:

• On the positive side, we obtain computational and statistical simplicity in various forms, e.g., it leads to closed-form estimation for linear models through linear algebra, it is based on computing moments with fixed controlled variance, and it leads to sharp analyses in various setups (acceleration, stochastic gradient descent, etc.). See, e.g., this post on acceleration, and this one on averaging.
• On the negative side, using least-squares regression for all prediction problems, particularly with discrete outputs, creates some artefacts. The traditional example is classification with Gaussian class-conditional data (with identical covariance matrices), where least-squares on the one-hot encoded outputs has problems, such as “masking” (see [13, Section 2.4] and the example below), or high approximation error compared with using multinomial logistic regression (a.k.a. softmax regression), because then the log conditional probabilities are affine.

Can we reconcile them? In other words, is least-squares really all I need? (my colleagues sometimes mock me for my love of least-squares).

Note that there is another (classic) attempt at seeing the world through least-squares: doing it in series through Newton’s method, leading in this context to iteratively reweighted least-squares, but this is for computations only, with no statistical improvement. What we are aiming at is stronger: can we get least-squares-based closed-form estimators for maximum-likelihood problems that typically require optimization of a convex function (such as logistic or softmax regression)?

Interestingly, my new attempt can be summarized in one integral equation $$ t \log t\, – t + 1 = \int_0^1 \!\! \frac{ (t-1)^2}{\rho t + 1-\rho} (1-\rho) d\rho,$$ which can be checked by usual integration tricks. Let’s see why and how!

Relative density estimation as a testbed

In this post, I look at a simple fundamental problem where we can study and compare various estimation frameworks, noting that it can be extended in several ways (in particular, through mutual information, see below).

We consider two probability distributions \(p\) and \(q\) on \(\mathcal{X}\); our goal is to estimate the logarithm of the relative density \(\log \big(\frac{dp}{dq}(x)\big)\). This turns out to be equivalent to estimating the Kullback-Leibler (KL) divergence because of the variational formulation [1] $${\rm KL}(p\|q) = \int_{\mathcal{X}} \log \big(\frac{dp}{dq}(x)\big) dp(x) = \sup_{v: \mathcal{X} \to \mathbb{R}} \int_{\mathcal{X}} v(x) dp(x) + 1\, – \int_{\mathcal{X}} e^{v(x)} dq(x). \tag{1} $$

This is one particularly important instance of an \(f\)-divergence (see, e.g., [2]), with the following definition and variational formulation based on the Fenchel conjugate \(f^\ast\) of \(f\): $$D(p\|q) = \int_{\mathcal{X}} f \big( \frac{dp}{dq}(x) \big) dq(x)= \sup_{v: \mathcal{X} \to \mathbb{R}} \int_{\mathcal{X}} v(x) dp(x) \, – \int_{\mathcal{X}} f^\ast(v(x)) dq(x),$$ the representation being a consequence of \(f(t) = \sup_{ u \in \mathbb{R}} ut-f^\ast(u)\) applied to each \(t = \frac{dp}{dq}(x)\). The KL divergence corresponds to \(f(t) = t \log t \, – t + 1\) and \(f^\ast(u) = e^u \, – 1\).

Note that for the particular case of the KL divergence, when optimizing with respect to a constant on top of \(v\), we obtain the Donsker-Varadhan representation [3] $${\rm KL}(p\|q) = \sup_{v: \mathcal{X} \to \mathbb{R}} \int_{\mathcal{X}} v(x) dp(x)\, – \log \Big( \int_{\mathcal{X}} e^{v(x)} dq(x) \Big). \tag{2}$$

We see the log-sum-exp function appearing explicitly. To estimate the potential \(v\) from i.i.d. samples from \(p\) and \(q\), the traditional variational approach corresponds to replacing integrals with empirical averages. For \(q\), this leads to a potentially unstable empirical average when only samples are available. The goal of this post is to explore another way (I present the main principles behind this new framework; see [7] for more details).

The framing through \(f\)-divergences is really key to the new approach, as other divergences will be instrumental in the definition. Before we move on, we state another (equivalent) variational formulation with two potentials \(v\) and \(w\), which we will need later: \(D(p\|q)\) is equal to $$\sup_{v,w: \mathcal{X} \to \mathbb{R}} \int_{\mathcal{X}} v(x) dp(x) + \int_{\mathcal{X}} w(x) dq(x) \mbox{ such that } \forall x \in \mathcal{X}, w(x) \leqslant -f^\ast(v(x)). \quad \tag{3}$$ At optimum, we get \(w(x) = -f^\ast(v(x))\), and we recover Eq. (1) in the KL case. The constraint is convex, but for \(f(t) = t \log t – t + 1\), it is far from what traditional convex optimization methods typically allow. This formulation appears in [25, Theorem 4.4] and has the nice property of preserving the symmetry of the problem (that is, if \(p\) and \(q\) are swapped, this is equivalent to replacing \(f\) by \(t \mapsto t f(1/t)\), and this corresponds to swapping \(v\) and \(w\).) In what follows, we will obtain candidates for functions \(v\) and \(w\) that satisfy the constraint \(\forall x \in \mathcal{X}, \ w(x) \leqslant -f^\ast(v(x))\), typically without equality.

Weighted chi-square divergences

Another relevant function \(f\) for \(f\)-divergences is, for a parameter \(\rho \in [0,1]\), $$ f(t) = \frac{1}{2} \frac{ (t-1)^2}{ \rho t + 1-\rho}. $$ It leads to a weighted chi-square divergence $$ D(p\|q) = \frac{1}{2} \int_{\mathcal{X}} \frac{ \big(\frac{dp}{dq}(x)-1 \big)^2}{ \rho \frac{dp}{dq}(x) + 1-\rho} dq(x).$$ It has been used in various areas of applied mathematics [4, 5], and comes under several names for special cases, such as Pearson chi-square divergence for \(\rho =0\), or Neyman chi-square (or reverse Pearson) for \(\rho=1\), or Le Cam divergence for \(\rho=1/2\).

The function \(f\) above, which is of the form “quadratic over affine” has the variational representation through “quadratic plus affine” functions: $$ \frac{1}{2} \frac{ (t-1)^2}{ \rho t + 1-\rho} = \sup_{u \in \mathbb{R}} \ (t-1) u \, – \frac{1}{2} ( \rho t + 1 – \rho) u^2, $$ with the optimal \(u = \frac{t-1}{\rho t + 1 \, – \rho}\) (this, by the way, is not the Fenchel representation).

Thus, applying this for each \(x \in \mathcal{X}\) to \(t = \frac{dp}{dq}(x)\), for this function \(f\), we have $$ D(p\|q) = \!\! \sup_{u(\rho,\cdot):\mathcal{X} \to \mathbb{R}} \int_{\mathcal{X}} \Big\{ \big(\frac{dp}{dq}(x) -1\big) u(\rho,x) \, – \frac{1}{2} \big( \rho \frac{dp}{dq}(x) + 1 – \rho\big) u(\rho,x)^2 \Big\} dq(x). $$ This is exactly a quadratic variational problem since the function \(u(\rho,\cdot): \mathcal{X} \to \mathbb{R}\) only appears quadratically. The optimal variational function is then \(\displaystyle u(\rho,x) = \frac{ \frac{dp}{dq}(x) \, – 1}{ \rho \frac{dp}{dq}(x) + 1-\rho}.\)

Note that the quadratic cost function that we just defined is explicitly a least-squares prediction problem, to predict \(y\) given \(x\), where with probability \(\rho\), \(y\) takes the value \(1/\rho\) and \(x\) is sampled from \(p\), and with probability \(1-\rho\), \(y\) takes the value \(-1/(1-\rho)\) and \(x\) is sampled from \(q\) (this is thus reminiscent of noise contrastive estimation [26]). We thus see a potential instability at \(\rho=0\) or \(\rho=1\) (we will see later that this is not the case).

This variational formulation of \(D(p\|q)\) can be rewritten by assembling expectations with respect to \(p\) or \(q\) together, as $$ \sup_{u(\rho,\cdot):\mathcal{X} \to \mathbb{R}} \int_{\mathcal{X}} \big( u(\rho,x) \, – \frac{\rho}{2} u(\rho,x)^2 \big) dp(x) + \int_{\mathcal{X}} \big( -u(\rho,x)\, – \frac{1-\rho}{2} u(\rho,x)^2 \big) dq(x) .$$ We then get exactly a two-potential formulation with $$v(x) = u(\rho,x) \, – \frac{\rho}{2} u(\rho,x)^2 \ \ \mbox{ and } \ \ w(x) = -\, u(\rho,x) \, – \frac{1-\rho}{2} u(\rho,x)^2 $$ as the two potentials (the rigorous reader can check that \(\forall x \in \mathcal{X}, w(x) \leqslant -f^\ast(v(x))\), which is not obvious, so that they are the optimizers for Eq. (3)).

To summarize, for the function \(f: t \mapsto \frac{1}{2} \frac{ (t-1)^2}{ \rho t + 1-\rho}\), we have exactly what we want, that is, a variational formulation through least-squares. How can it be extended to more general \(f\)-divergences?

Extension by integration

If we can write \(\displaystyle f(t) = \frac{1}{2} \int_0^1 \frac{ (t-1)^2}{\rho t + 1-\rho} d\nu(\rho)\) for some non-negative measure \(\nu\) on the interval \([0,1]\), then we can directly use the developments above to get a representation of \(D(p\|q) \) as $$\!\!\sup_{u:[0,1] \times \mathcal{X} \to \mathbb{R}} \int_{0}^1\!\!\!\! \int_{\mathcal{X}} \!\! \Big[\! \, (\frac{dp}{dq}(x) -1) u(\rho)(x) \, – \frac{1}{2} ( \rho \frac{dp}{dq}(x) + 1 \, – \rho) u(\rho)(x)^2 dq(x) \!\Big] d\nu(\rho), \tag{4}$$ with now a function \(u\) from \([0,1] \times \mathcal{X}\) to \(\mathbb{R}\).

We then get exactly a two-potential formulation, as presented in Eq. (3), with $$v(x) = \int_0^1 \big[ u(\rho,x) \, – \frac{\rho}{2} u(\rho,x)^2 \big] d\nu(\rho) \tag{5} $$ and $$w(x) = \int_0^1 \big[ -u(\rho,x) \, – \frac{1-\rho}{2} u(\rho,x)^2 \big] d\nu(\rho), \tag{6}$$ (which satisfy the constraint \(w(x) + f^\ast(v(x)) \leqslant 0\), which is, again, not straightforward) where \(u(\rho,\cdot)\) is a maximizer of Eq. (4). This corresponds to performing a continuum of least-squares problems in parallel.

These developments are valid for all \(f\)-divergences with an integral representation, and in particular the KL divergence, since we have $$t \log t\, – t + 1 = \int_0^1 \!\! \frac{ (t-1)^2}{\rho t + 1-\rho} (1-\rho) d\rho,$$ that is, \(d\nu(\rho) = 2 (1-\rho) d\rho\). This integral representation does not come out of nowhere; in fact, it comes from the theory of operator convex and operator monotone functions that we explored in an earlier post. It includes KL, obviously all weighted chi-square divergences (with \(\nu\) a Dirac measure), and all the \(\alpha\)-divergences [14], but unfortunately not the total variation.

Now that we have a generic framework to learn potentials \(v\) and \(w\) as integrals of least-squares estimates \(u(\rho,\cdot)\) for each \(\rho \in [0,1]\) and their squares, we can start to use function spaces to parameterize them, starting from linear models (see below for more general models).

Linear models with closed-form spectral estimation

If each function \(u(\rho,\cdot)\) is modeled as linear in some feature vector \(\varphi: \mathcal{X} \to \mathbb{R}^m\), that is, \(u(\rho,x) = \theta(\rho)^\top \varphi(x)\) for some \(\theta(\rho) \in \mathbb{R}^m\) (a family of parameters indexed by \(\rho\)), the optimization problem in Eq. (4) leads to $$ \sup_{\theta(\rho) \in \mathbb{R}^m} \ (\mu_p – \mu_q)^\top \theta(\rho)\, -\, \frac{1}{2} \theta(\rho)^\top ( \rho \Sigma_p + (1-\rho) \Sigma_q) \theta(\rho), $$ with the moments of \(\varphi\) with respect to \(p\) and \(q\): \(\mu_p = \mathbb{E}_p[\varphi(x)]\), \(\mu_q = \mathbb{E}_q[\varphi(x)]\), \(\Sigma_p = \mathbb{E}_p[\varphi(x)\varphi(x)^\top]\), and \(\Sigma_q = \mathbb{E}_q[\varphi(x)\varphi(x)^\top]\).

The optimal \(\theta(\rho)\) is then obtained by solving a linear system: $$\theta(\rho) = ( \rho \Sigma_p + (1-\rho) \Sigma_q)^{-1} ( \mu_p \,- \mu_q), $$ with an optimal value $$ \frac{1}{2} ( \mu_p \, – \mu_q)( \rho \Sigma_p + (1-\rho) \Sigma_q)^{-1} ( \mu_p\, – \mu_q).$$

Doing this for all \(\rho \in [0,1]\) and integrating, this leads to a new divergence that depends on the distributions \(p, q\) and on the feature map \(\varphi\): $$F(p\|q,\varphi) = \frac{1}{2} \int_0^1 ( \mu_p \, – \mu_q)^\top( \rho \Sigma_p + (1-\rho) \Sigma_q)^{-1} ( \mu_p\, – \mu_q) d\nu(\rho), \tag{7}$$ and a new candidate for \(v(x)\) to estimate \(f'(dp/dq(x))\) using Eq. (5). By construction, we obtain a lower bound on the \(f\)-divergence \(D(p\|q).\)

This is closed-form but requires integration with respect to \(\rho\), which is not practical, in particular since one should expect to need many quadrature points if using quadrature to estimate integrals, since the least-squares problems may diverge when \(\rho\) tends to 0 or to 1.

Eigenvalues to the rescue! Given that we need to invert matrices \(\rho \Sigma_p + (1-\rho) \Sigma_q\) for all \(\rho \in [0,1]\), using an eigenvalue decomposition, as done for ridge regression when solving for multiple values of the regularization parameter [6], seems natural. In our situation, we need a generalized eigenvalue decomposition of the pair \((\Sigma_p,\Sigma_q)\), that is, a basis \((v_1,\dots,v_m)\) of \(\mathbb{R}^m\) such that $$ \forall i,j \in \{1,\dots,m\}, \ v_i^\top \Sigma_q v_j = 1_{i=j} \ \mbox{ and } \ \Sigma_p v_i = \lambda_i \Sigma_q v_j.$$ A few lines of algebra (see [7]) then lead to $$F(p\|q,\varphi) = \sum_{i=1}^m \frac{1}{2} \int_0^1 \frac{ \big( ( \mu_p \, – \mu_q)^\top v_i \big)^2}{ \rho \lambda_i+ 1-\rho } d\nu(\rho) = \sum_{i=1}^m \big( ( \mu_p \, – \mu_q)^\top v_i \big)^2 \frac{f(\lambda_i)}{(\lambda_i-1)^2}. $$ There is a similar “simple” formula that is summing over eigenvalues for \(\theta(\rho)\), and the potentials \(v(x)\) and \(w(x)\) as quadratic-linear forms $$v(x) = \varphi(x)^\top M \varphi(x) + 2c^\top \varphi(x)\ \mbox{ and } \ w(x) = \varphi(x)^\top N \varphi(x) \, – 2c^\top \varphi(x),$$ with detailed formulas for \(M,N,c\). See [7] and, for convex analysis aficionados, the section below the references for more details, in particular a nice link with sum-of-squares optimization.

Although individual least-squares problems may have instabilities around \(\rho=0\) or \(\rho = 1\), after integration, estimation remains stable for all functions \(f\) such that \(t \mapsto f(t)/(t-1)^2\) remains bounded (for the KL, it is decreasing with \(f(0)=1\)).

Note that throughout this blog post, the concept of “simple closed-form formula” is quite subjective: by it, I mean stable routines from numerical linear algebra with explicit guarantees: this includes inverting linear systems and (generalized) eigenvalue decomposition [8].

Computational complexity. Using classical numerical linear algebra routines, the running-time complexity is \(O(m^2n +m^3)\) to compute the divergence and find estimates of \(v\) and \(w\), which is problematic when \(n\) or \(m\) is large. Feature learning as explained briefly below and more thoroughly in [7] allows one to learn an \(r\)-dimensional linear representation that is shared across all \(\rho\)’s, with iterative algorithms that have iterations of complexity \(O(r^3 + rmn)\), which is efficient when \(r\) remains small.

Benefits of spectral estimation

Now that we can solve all these \(\rho\)-dependent least-squares problems in one shot, does it hold its promise in reducing variance? The main competitor here is the direct variational approach that maximizes Eq. (1) or Eq. (2).

Given data, for the spectral method, we simply (and classically) replace expectations with empirical averages (which corresponds to using empirical moments) and potentially add regularization, i.e., replace \(( \rho \Sigma_p + (1-\rho) \Sigma_q)^{-1} \) with \(( \rho \Sigma_p + (1-\rho) \Sigma_q + \lambda I)^{-1} \). This corresponds to performing ridge regression for all \(\rho\)-dependent least-squares problems.

The benefits can be measured either with theoretical arguments or by simulations. We provide both below.

High-dimensional evaluation on a Gaussian model. The simplest possible set-up is the Gaussian case with common covariance matrices (which I thoroughly explore in [9]). Since our unregularized estimator is invariant under affine transformations, we can consider \(p\) Gaussian with mean \(\Delta \in \mathbb{R}^m\) and covariance identity and \(q\) Gaussian with mean \(0\) and covariance identity. In the high-dimensional limit where the dimension \(m\) and the number of samples \(n_p\) and \(n_q\) grow to infinity with fixed ratios, the performance of the variational and spectral estimators only depends on \(s = \| \Delta\|^2\) and the “aspect ratios” \(\alpha_p = \frac{m}{n_p}\) and \(\alpha_q = \frac{m}{n_q}\). We consider linear features.

This setup is favorable to the variational estimator because the true log-density ratio is affine in \(x\), while the new spectral estimator incurs a bias (which can be explicitly characterized, see [9]). Is the increased bias compensated by the reduced variance? This can be precisely analyzed in the high-dimensional regime where \(n_p, n_q, m\) tend to infinity with fixed ratios \(\alpha_p = \frac{m}{n_p}\) and \(\alpha_q = \frac{m}{n_q}\), using random matrix theory [11] or the convex Gaussian min max theorem (CGMT) [12]. This allows us to compute asymptotic performance for the (unregularized) variational and the spectral approach, with the following performance for fixed \(s=1\) below, for all values of \(\alpha_p\) and \(\alpha_q\) (see [9] for all details).

As expected, for large numbers of observations (small \(\alpha_p,\alpha_q\)), the variational method leads to better performance due to a reduced bias, but for smaller numbers of observations, its increasing variance makes the spectral method preferable.

Simulations. We consider a simple situation with data in two dimensions (\(d=2\)) and a non-linear log-density which is learned using random features based on ReLUs, that is, \(\varphi(x)_i = (w_i^\top x + b_i)_+\) for \(i \in \{1,\dots,m\}\) for randomly chosen \((w_i,b_i) \in \mathbb{R}^{d+1}\), with an increasing number of observations \(n = n_p = n_q\). The problem of estimating KL divergence between generic distributions is a non-parametric problem with convergence rates that exhibit the curse of dimensionality, and unless \(n\) is very large, or special sparsity assumptions are made, we can only estimate accurately in small dimension (see below for higher dimension when feature learning is used).

We see that KL is better than using the Pearson divergence (which is the traditional way [22, 23, 24] to use least-squares for density estimation, but suffers from the improper geometry in particular in the way it deals with positivity of densities), and better than variational, except for a large number of observations, where variational and KL spectral are the same.

Mutual information and conditional estimation

Within information theory, the KL divergence is often used as a measure of independence between random variables, leading to the mutual information: given a product space \(\mathcal{X}_1 \times \mathcal{X}_2\) and a joint distribution \(p(x_1,x_2)\), we can consider \(q(x_1,x_2)\) as the distribution with independent components that have the same marginals as \(p\), which we write \(q(x_1,x_2) = p(x_1) p(x_2)\), following the usual graphical model convention. Then the optimal log-relative-density is $$ \log \frac{ p(x_1,x_2)}{p(x_2) p(x_1)} = \log \frac{ p(x_2|x_1)}{p(x_2)}.$$

Hence, our framework for closed-form estimation allows us to perform conditional density estimation \(\log p(x_2|x_1)\) (with the additional need for \(\log p(x_2)\)). This can be done in general for any \(\mathcal{X}_2\), but when \(\mathcal{X}_2\) is finite, our closed-form estimation is exactly a way to perform softmax regression.

Note, however, that this new closed-form estimate is not equivalent to least-squares estimation for classification directly on one-hot encodings, which is essentially what the potential obtained from the Pearson divergence would do (and then leads to classical canonical correlation analysis). In the figure below, we see that for simple Gaussian data in two dimensions, the new spectral estimator for the KL divergence behaves “similarly” (but not identically) to softmax regression.

It is also interesting to consider adding quadratic features (because the log-density here is quadratic since the class-conditional covariance matrices are not equal), and also compare to the classical square loss (which corresponds to using Pearson divergence, that is, \(\nu\) is a Dirac at \(\rho=0\)). With more features, all methods tend to have more similar classification regions (if the set of features is big enough to model all real-valued functions, they are identical). Note that on the top right, we see the masking problem of least-squares where some classes totally disappear (this is solved by adding features in the bottom right plot, but indicates an unnatural cost function).

Computational complexity. To obtain estimates with machine precision for \(k\) classes with feature vectors in dimension \(d\), then softmax regression using Newton’s method would take \(O( nd^2 k^2 + d^3 k^3)\) per Newton iteration, while the closed-form estimator takes only \(O(d^2 n + kd^3)\) for one eigenvalue decomposition, which is a significant gain. When gradient-based algorithms are used with feature learning, both computation times can be reduced.

Feature learning

Linear models are great, but if one lesson has been learned since deep learning took over, it is that we need to learn features in a more end-to-end way, and large sets of predefined features are not enough for various reasons, in particular adaptivity to unknown (linear or non-linear) latent variables. In our variational framework where we have a lower bound on the KL divergence, this is simply maximizing \(F(p\|q, \varphi)\) in Eq. (7) with respect to \(\varphi\), and leveraging the fact that \(F(p\|q, \varphi)\) is convex in moments of \(\varphi\).

Indeed, as a convex function of the moments \(\mu_p-\mu_q,\Sigma_p,\Sigma_q\), it is lower-bounded by a constant plus $$ {\rm tr} \big( M \mathbb{E}_p [ \varphi \varphi^\top ] \big) + {\rm tr} \big( N \mathbb{E}_q [ \varphi \varphi^\top ] \big) + 2c^\top \big( \mathbb{E}_p [\varphi] – \mathbb{E}_q[\varphi]),$$ for matrices \(M,N\) and a vector \(c\) which can be computed from any given \(\bar\varphi\) (this is exactly what was needed to compute the potentials \(v\) and \(w\), and chosen so that the lower bound is tight for \(\varphi = \bar\varphi\) (see the section below the references). This allows for a minorization-maximization algorithm [15, 16] similar to the expectation-maximization (EM) algorithm [17]. The link with EM allows us to reuse many of the computational tricks developed there, such as online EM [18], to make the algorithm scalable to large networks to parameterize \(\varphi\) and large numbers of observations. More on this in a next post.

Conclusion

In this blog post, I introduced a new framework for relative density estimation that circumvents the exploding variance of means of exponentials. This was obtained by a continuum of stable least-squares problems, and made computationally feasible through a single generalized eigenvalue decomposition. Beyond tackling the exploding variance problem for models that need to be normalized, the unintended consequence for normalized models (where the sum/integral can be computed) was to obtain a closed-form estimator for softmax regression.

The recent paper [7] explores other consequences, in particular in terms of rates of estimation for the KL divergence, sometimes with minimax rates and partial adaptivity to linear latent variables. Overall, there is a long way to go, but I see this new framework as a potential replacement for the last layer of neural networks, where cross-entropy loss and log-sum-exp dominate. More on this in the next post.

Acknowledgements and tool usage disclosure. I would like to thank Frederik Kunstner and Nicolas Flammarion for helpful clarifying suggestions. Frontier LLM models were used to produce figures and correct typos.

References

[1] XuanLong Nguyen, Martin J. Wainwright, and Michael I. Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 56(11):5847–5861, 2010.
[2] Yury Polyanskiy and Yihong Wu. Information Theory: From Coding to Learning. Cambridge University Press, 2025.
[3] Monroe D. Donsker and S. R. Srinivasa Varadhan. Asymptotic evaluation of certain Markov process expectations for large time-III. Communications on Pure and Applied Mathematics, 29(4):389–461, 1976.
[4] László Györfi and Igor Vajda. A class of modified Pearson and Neyman statistics. Statistics & Risk Modeling 19(3): 239-252, 2001.
[5] Lucien Le Cam. Asymptotic Methods in Statistical Decision Theory. Springer Science & Business Media, 2012.
[6] Gene H. Golub, Michael Heath, and Grace Wahba. Generalized cross-validation as a method for choosing a good ridge parameter. Technometrics 21(2):215-223, 1979.
[7] Francis Bach. A Spectral Framework for Closed-Form Relative Density Estimation. Technical report, arXiv:2605.10668, 2026, to appear in Advances of Neural Processing Systems (NeurIPS).
[8] Gene H. Golub and Charles F. Van Loan. Matrix Computations. Johns Hopkins University Press, 1996.
[9] Francis Bach. Regularized Variational and Spectral Log-Density-Ratio Estimation in the Gaussian Location Model. Technical report, arXiv:2607.01895, 2026.
[10] Didier Henrion, Milan Korda, and Jean Bernard Lasserre. The Moment-SOS Hierarchy: Lectures in Probability, Statistics, Computational Geometry, Control and Nonlinear PDEs. World Scientific, 2020.
[11] Zhidong Bai and Jack W. Silverstein. Spectral Analysis of Large Dimensional Random Matrices. Springer, 2nd edition, 2010.
[12] Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. The Gaussian min-max theorem in the presence of convexity. Technical report, arXiv:1408.4837, 2014.
[13] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning. Springer, 2009.
[14] Andrzej Cichocki and Shun-ichi Amari. Families of alpha-beta- and gamma-divergences: Flexible and robust measures of similarities. Entropy, 12.6:1532-1568, 2010.
[15] David R. Hunter and Kenneth Lange. A tutorial on MM algorithms. The American Statistician, 58(1):30–37, 2004.
[16] Julien Mairal. Stochastic majorization-minimization algorithms for large-scale optimization. In Advances in Neural Information Processing Systems, 2013.
[17] Arthur P. Dempster, Nan M. Laird, and Donald B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: series B (methodological) 39(1):1-22, 1977.
[18] Olivier Cappé and Eric Moulines. On-line expectation–maximization algorithm for latent data models. Journal of the Royal Statistical Society Series B: Statistical Methodology, 71(3):593–613, 2009.
[19] Brian D. Ziebart, Andrew Maas, J. Andrew Bagnell, and Anind K. Dey. Maximum entropy inverse reinforcement learning. AAAI Conference on Artificial Intelligence, 2008.
[20] Francis Bach. Sum-of-squares relaxations for information theory and variational inference. Foundations of Computational Mathematics, 25.3: 865–903, 2025.
[21] Keiji Matsumoto. A new quantum version of f-divergence. In Nagoya Winter Workshop: Reality and Measurement in Algebraic Quantum Theory, pages 229–273. Springer, 2015.
[22] Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density Ratio Estimation in Machine Learning. Cambridge University Press, 2012.
[23] Zaid Harchaoui, Francis Bach, and Eric Moulines. Testing for homogeneity with kernel Fisher discriminant analysis. Technical Report 0804.1026, arXiv, 2008.
[24] Mónica Ribero, Antonin Schrab, and Arthur Gretton. Regularized \(f\)-divergence kernel tests. Technical Report 2601.19755, arXiv, 2026.
[25] Michel Broniatowski and Amor Keziou, Minimization \(\varphi\)-divergences on sets of signed measures, Studia Scientiarum Mathematicarum Hungarica, 43(4):403–442, 2006.
[26] Michael U. Gutmann and Aapo Hyvärinen. Noise-Contrastive Estimation of Unnormalized Statistical Models, with Applications to Natural Image Statistics. Journal of Machine Learning Research, 13(11):307−361, 2012.

Playing with SDPs

We defined our new divergence in Eq. (7) as $$F(p\|q,\varphi) = \frac{1}{2} \int_0^1 ( \mu_p \, – \mu_q)^\top( \rho \Sigma_p + (1-\rho) \Sigma_q)^{-1} ( \mu_p\, – \mu_q) d\nu(\rho). $$ It is convex in \(\Sigma_p\), \(\Sigma_q\), and \(\mu_p – \mu_q\), and there is a nice duality theory here, showing that \(M,N,2c\) defined above are in fact derivatives with respect to the parameters above. The main result here, shown in [7], is: $$F(p\|q,\varphi) = \ \sup_{M,N,c} {\rm tr}(\Sigma_p M) + {\rm tr}(\Sigma_q N) + 2c^\top (\mu_p – \mu_q) \qquad \qquad \qquad \qquad$$ $$\qquad \qquad \qquad \qquad \mbox{ such that } \ \forall \lambda \geqslant 0, \left( \begin{array}{cc} \lambda M + N & (\lambda-1)c \\ (\lambda-1)c^\top & -f(\lambda) \end{array} \right) \preccurlyeq 0.$$ The semi-definite constraint above exactly implies that the potentials \(v(x)\) and \(w(x)\) are such that \(\forall x \in \mathcal{X}, \ w(x) + f^\ast(v(x)) \leqslant 0\), in exactly the same way as semi-definite programming can be used for optimization through sums-of-squares (see, e.g., [10]). Indeed, for any \(\lambda \geqslant 0\), we have $$\lambda v(x) + w(x) -f(\lambda) = { \varphi(x) \choose 1}^\top \left( \begin{array}{cc} \lambda M + N & (\lambda-1)c \\ (\lambda-1)c^\top & -f(\lambda) \end{array} \right) { \varphi(x) \choose 1} \leqslant 0,$$ which is equivalent to \(w(x) + f^\ast(v(x)) \leqslant 0\).

In earlier work [20], I had developed a similar framework for feature maps that were normalized so that \(\| \varphi(x)\|=1\), leading to the lower bound on \(D(p\|q)\) equal to $$\sup_{M,N} {\rm tr}(\Sigma_p M) + {\rm tr}(\Sigma_q N) \ \mbox{ such that } \ \forall \lambda \geqslant 0, \ \lambda M + N + f(\lambda) I \preccurlyeq 0, $$ which is then equal to an expression common in quantum information theory [21], that is, $$ {\rm tr} \big[ \Sigma_q f( \Sigma_q^{-1/2} \Sigma_p \Sigma_q^{-1/2})\big].$$ The key novelty is that we no longer need normalized features, which makes feature learning significantly easier.

By Francis Bach

Algebraic Matroids are Undecidable

Tobias Boege and Geva Yashfe have posted a remarkable paper, Recognition of algebraic matroids is undecidable. It brings together matroid theory, algebraic geometry, model theory, and undecidability.

An algebraic matroid abstracts algebraic independence in a field extension . If the elements of are represented by elements of , the rank of a subset is the transcendence degree over of the field generated by its representatives. In characteristic zero, Ingleton proved in 1971 that every algebraic matroid is linear over an appropriate extension field. In positive characteristic, however, algebraic matroids include examples that are not linear over any field. In 1975, Ingleton and Main showed that non-algebraic matroids exist: their example was the Vámos matroid , which violates an extension property of algebraic matroids. The class of algebraic matroids is closed under matroid union and truncation; Lindström later constructed infinitely many excluded minors.

Boege and Yashfe prove that:

1. There is no algorithm that takes as input a finite matroid and decides whether it is algebraic in any given positive characteristic .
2. There is no algorithm that decides whether a finite matroid is algebraic over some field, with no restriction on the characteristic.

The contrast with characteristic zero is striking: recognizing algebraic matroids in characteristic zero is decidable, because there algebraic and linear matroids coincide.

Recognizing whether a matroid has a particular sort of realization is a central question in matroid theory. One precursor is Mnëv’s universality theorem: realization spaces of oriented matroids can model arbitrary primary semialgebraic sets, and the associated realizability problem is complete for the existential theory of the reals. Another is work of Lukas Kühne and Geva Yashfe showing that multilinear representability is undecidable: there is no algorithm to determine whether a matroid can be represented by a -arrangement of vector subspaces for some positive integer .

Here is a very rough glimpse of the new proof. Classical von Staudt constructions turn incidences of points and lines in a projective plane into equations for their coordinates. The group configuration theorem of Hrushovski and Zilber, together with work of Evans and Hrushovski, allows Boege and Yashfe to recover suitable projective planes from patterns of algebraic dependence. A central difficulty is to identify the Frobenius map using only information recorded by a matroid. They do this by connecting the additive and multiplicative algebraic groups through the affine group. In the resulting structure, the operations commuting with Frobenius give a copy of the rational function field , with distinguished. The authors then translate solvability of equations over this field into algebraic realizability of finite matroids. The necessary undecidability theorem for equations over is due to Pheidas for odd and Videla for .

What is the Vámos matroid?

The Vámos matroid has rank four on eight elements. Here is a concrete description. Divide its elements into four pairs . Every set of at most three elements is independent. Among the 70 four-element sets, exactly five are dependent:

The conspicuous exception is , which is independent. Every other four-element set is independent as well, and therefore a basis. The five dependent four-element sets are called circuit-hyperplanes.

Why does this example matter here? Ingleton and Main showed that this pattern cannot arise from algebraic dependence among elements of a field extension: under the stated rank conditions, dependence of the five listed unions would force to be dependent too. Thus is not algebraic over any field.

What does the word conspicuous mean?

Conspicuous means easy to notice or standing out clearly. So “a conspicuous exception” is an exception that draws attention.

Here are some beautiful figures from the paper. 

   

By Gil Kalai

Authors: Samruddhi Pednekar, Supartha Podder

A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions $f:\{0,1\}^n\to\{0,1\}$ and $g:\{0,1\}^m\to\{0,1\}$, \[ \widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), \] where $\widetilde{deg}$ denotes constant-error approximate degree.

Authors: Aleksandr Storozhenko

For an arbitrary isotropic log-concave distribution $P$ on $\mathbb{R}^d$, we prove that the polynomial $(Cm)^m\|v\|_2^m - \mathbb{E}_{X\sim P}\langle X,v\rangle^m$ is a sum of squares for every even $m\ge2$, where $C>0$ is a universal constant. This removes the dependence on the Poincaré constant in the theorem of Kothari and Steinhardt (arXiv:1711.07465), recovering the optimal moment bounds for log-concave distributions. As an immediate corollary, we obtain computationally efficient algorithms with dimension-free error guarantees for a wide range of high-dimensional statistical estimation problems. Our proof uses stochastic localization to decompose $P$ as an average of random strongly log-concave measures, whose centered moments admit the subgaussian certificates of Diakonikolas, Hopkins, Pensia, and Tiegel (STOC 2025; arXiv:2410.21194). With a covariance-adapted choice of localization, we show that a fourth-moment certificate derived from Letwin's variance inequality for quadratic forms (arXiv:2607.24164) suffices to control this averaging at every even degree.

Authors: Aaron Potechin, Jeff Xu

It is well known that the \Lovasz-Theta function of a random graph $G(n,\tfrac{1}{2})$ is $Θ(\sqrt{n})$. More precisely, it is tightly concentrated in the interval \( [\sqrt{n},\, 2\sqrt{n}], \) where the upper bound follows from an explicit dual witness for the associated semidefinite program. Numerical evidence and heuristic arguments suggest that the true value is $(1+o(1))\sqrt{n}$. However, closing this gap has remained a longstanding challenge, resisting existing techniques even in light of recent progress on sharp algorithmic thresholds and non-asymptotic free probability. In this work, we resolve this question by proving that the \Lovasz-Theta function of $G(n,\tfrac{1}{2})$ is $(1+o_n(1))\sqrt{n}$ with high probability, determining its asymptotic value up to vanishing relative error.

Authors: Taotao He, Runfa Hu

We study the computational complexity of peak-oriented rationalizability, a survey based revealed-preference test introduced by Seror (2026). We provide a polynomial-time algorithm for testing rationalizability and recovering a utility function, establishing that peak-oriented preference elicitation is computationally tractable. In contrast, we show that computing the peak-oriented Houtman-Maks index is NP-hard. These results delineate the precise computational boundaries of peak-oriented revealed-preference analysis.

Authors: Martin Bichler, Abheek Ghosh

We study equilibrium computation in discrete multiplayer Colonel Blotto games with player-specific battlefield values. In the two-player model with common battlefield values, equilibria can be computed in polynomial time. We show that this tractability breaks down in the multiplayer model with player-specific values under the standard uniform tie-breaking rule. In particular, computing a $(c/n)$-approximate Nash equilibrium is PPAD-hard for some constant $c>0$, even when every player has three resources, where $n$ is the number of players. The main technical step is PPAD-hardness for computing a constant-approximate well-supported Nash equilibrium. In contrast, under uniform tie-breaking, a pure Nash equilibrium can be computed in polynomial time when every player has one resource. We also prove PPAD membership for computing $\varepsilon$-approximate Nash equilibria for inverse-exponentially small $\varepsilon$. Finally, for non-uniform monotone tie-breaking, we show PPAD-hardness even when every player has one resource and all players have identical battlefield values.

Authors: Sebastian Ben Daniel

Valiant and Vazirani isolate a satisfying assignment of a circuit with probability $Ω(1/n)$. Dell, Kabanets, van Melkebeek, and Watanabe showed that success above $2/3$ implies $\mathrm{NP}\subseteq\mathrm{P/poly}$ and asked about the range in between. We show that every positive constant already implies the collapse: if a randomized nonuniform polynomial-size pruning procedure succeeds with probability $ε$ on affine circuit inputs with at most $2^{\lfloor 2/ε\rfloor}$ satisfying assignments, then $\mathrm{NP}\subseteq\mathrm{P/poly}$. Success $10/\log L$ on affine inputs with at most $L^{1/3}$ satisfying assignments suffices, where $L$ is the description length, and on inputs with one or two satisfying assignments the threshold $2/3$ drops to $3/5$. No cryptographic assumption is used, and the procedure may read the entire circuit. The proof compiles a pool of circuits into one circuit whose satisfying assignments are indexed by tags in $\mathbb{F}_2^d$. Each member is assigned an affine region of tag space, and if one member is unsatisfiable, the satisfying set shrinks to that member's region. Because regions may overlap and have different dimensions, the collapse reduces to a combinatorial bound: no set of tags meets more than a $2/d$ fraction of an equally weighted family of affine subspaces of all dimensions below $d$ in exactly one point. This regional counting cannot go below order $1/\log L$. The range between $Θ(1/n)$, achieved by affine hashing, and $O(1/\log n)$ remains open.

Authors: Kainan Zhou, Chuhong Xu, Gangzhen Qian, Zhaoyi Li

A generative search answer can cite a supported passage yet omit a source relationship that changes its interpretation. We specify a claim-gated audit of the query-source-answer tuple. An omission is resolved only when relationship evidence, answer adoption, materiality, and disclosure are all observed; incomplete evidence remains unresolved rather than being treated as independence. The specification separates this endpoint from citation support and review priority, and binds decisions to versioned evidence spans. A reference checker makes the record contract executable. On an exhaustive synthetic suite, it reproduces all 81 three-state predicate combinations and rejects 192 deliberately malformed records. Common-guard baselines and predicate ablations isolate endpoint logic from missing-evidence handling, while controlled transitions check support separation and evidence removal. These are finite contract-conformance results, not detector accuracy or evidence of improved user outcomes. We define the independent annotation, held-out evaluation, and paired utility tests still required to establish semantic validity and deployment benefit.

Authors: Daqing Wan, Jun Zhang

For an $[n,K]$ Reed--Solomon code, the covering radius is $n-K$. Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the decoding radius is $d$ below the covering radius for every $1\le d\le c\log n/\log\log n$, where $c>0$ is an absolute constant. We prove that, for every fixed rational $0<α<1/2$, bounded-distance decoding is NP-complete under deterministic polynomial-time many-one reductions over explicitly represented finite extension fields for the additive gap $d=\lfloor n^α\rfloor$ below the covering radius. The hard codes have odd block length~$n$, dimension $K=(n+1)/2-d$, decoding radius $(n-1)/2$, and rate tending to $1/2$. The alphabet size is subexponential in the evaluation set size: for a fixed $0<η<1$ depending only on $α$, it is $2^{Θ(n^η\log n)}=2^{o(n)}$. The proof passes through moments subset sum on $n-1$ nonzero field elements, with required subset size $(n-1)/2$ and $d$ prescribed moments. The arithmetic ingredient is a uniform positive-completion theorem over prime fields $\mathbb{F}_q$ with $q\ge d^{2+ρ}$, for any fixed $ρ>0$. A sharper form follows from a higher-dimensional point-count estimate based on Deligne's theorem; the weaker form used in our reduction is proved more elementarily using additive-character orthogonality, the one-variable Weil bound, a moment identity of order $2d$, and Newton identities. A universal completion pool, an extension-field quotient construction, and a deterministic linear-size simultaneous power condenser complete the reduction.