Papers

In the theory of error correcting codes, list-decoding refers to the following problem. Given a code $C \subseteq \Sigma^N$ and a received word $y \in \Sigma^N$, find all codewords $c \in C$ so that $\delta(c,y) \leq \rho$, where $\delta$ is relative Hamming distance and $\rho \in (0,1)$. Codes that approach the optimal trade-off between the rate $R := \log_{|\Sigma|}(|C|) / N$ and the list-decoding radius $\rho$ are said to achieve capacity.By now, there are constructions of capacity-achieving list-decodable codes with fast near-linear-time list-decoding algorithms, but most existing work has not considered space complexity. In a recent line of work, Cook and Moshkovitz (2024, 2025, 2026) initiated the study of low-space deterministic algorithms for error correcting codes. In particular, in their 2026 paper, they gave a construction of list-decodable codes with deterministic near-linear-time and sublinear space list-decoding algorithms. However, these codes were far from achieving capacity. In this paper, we present list-decodable codes approaching capacity with deterministic time- and space-efficient list-decoding algorithms. More precisely, for any $R \in (0,1)$ and any arbitrarily small constant $\tau > 0$, we present a family of codes $C\subseteq \Sigma^N$ with rate $R$ that are deterministically list-decodable up to radius $\rho = 1 - R - \tau$, in time $N^{1 + \tau}$ and space $N^{\tau}$ with constant output list size and constant alphabet size. Our results can be extended to capacity-achieving list-recoverable codes.

We study $\ell_p$-norm maximization over zonotopes given by rational generators, with input length $L$. For fixed $p=a/b>1$, the exact Turing baseline runs in $n^{O(d)}b^{O(d)}\mathrm{poly}(L)$ time, but fixed-parameter tractability in the ambient dimension $d$ was open [FGHS25]. We prove W[1]-hardness and, under the Exponential Time Hypothesis (ETH), exclude $\rho_p(d)L^{o(d)}$ time, even for $5$-sparse generators, by encoding binary CSP constraints with normalized positive cap generators. We also give a deterministic $(1-\varepsilon)$-approximation with $\varepsilon^{-(d-1)/2}$ dependence and, among algorithms with fixed-degree polynomial dependence on $L$, rule out $(1/\varepsilon)^{o(d)}$ dependence under ETH. Support-function duality transfers the results to positive-output two-layer ReLU networks.

This paper is a failure analysis of the representation layer underlying GNN-based smart contract vulnerability detectors. These systems convert source code into graphs before any learning takes place; if the graph fails to capture the code's semantics, no model improvement can compensate. We investigate GNNSCVulDetector and identify four failures. First, structurally different contracts produce byte-for-byte identical graphs, constituting a concrete evasion attack. Second, graph construction is governed by a hardcoded 47-entry variable whitelist (including one duplicate entry), which constrains what the extractor can recognise. As a consequence, identical vulnerabilities with different variable names produce inconsistent graphs, graph quality degrades as naming diverges from the whitelist, and when no entry matches the pipeline produces structural output not grounded in source variables. Third, the C node (the graph element representing the external caller that triggers a reentrancy attack) is absent from even the most canonical vulnerable contract in the literature. Fourth, a controlled experiment confirms this as a direct misclassification: a fully exploitable contract is labelled safe because the C -> W edge is never constructed. All four failures are demonstrated experimentally. Current accuracy figures in the literature are measured under conditions that do not expose these failures. We demonstrate one confirmed case of misclassification caused directly by a representation-layer failure; the prevalence of such failures in real-world contract populations remains an open empirical question.

Locally dense lattices are central gadgets used to prove the hardness of the Shortest Vector Problem and related lattice problems. Informally, a locally dense lattice is a lattice $\mathcal{L}$ that contains exponentially many lattice vectors inside some $\ell_p$ ball centered at $\vec{s}$ with radius at most an $\alpha < 1$ fraction of the length of its shortest nonzero lattice vector. In this paper, taking a “meta” viewpoint on locally dense lattices, we introduce the Locally Dense Lattice Problem (LDLP), the decision problem of determining whether a given input specifies a locally dense lattice. Our main result is that LDLP in $\ell_p$ norms for all finite $p \geq \log_2 3$ and for the infinity norm is complete for the second level of the polynomial hierarchy. We also compare two standard definitions of local density that appear in prior work. Micciancio's original definition (FOCS 1998 and SICOMP 2001) uses integer coefficient vectors, while later work by Micciancio (ToC 2012) and by Bennett and Peikert (RANDOM 2023) uses short vectors in a shifted coset. We show that the corresponding promise problems are mutually reducible in deterministic polynomial time, which shows that the two formulations are robust.

In a landmark JACM paper recognized with the 2021 Gödel Prize, Cai and Chen established a complete complexity dichotomy for counting CSPs over arbitrary finite domains with algebraic complex weights. Its polynomial-time side is characterized by three conditions—Block Orthogonality, Type Partition, and preservation by a common Mal'tsev operation—quantified over the countably infinite family $W_{\mathcal{F}}$ generated from arbitrary $\#\mathrm{CSP}(\mathcal{F})$ instances by partial summation. They asked whether these infinitary conditions are decidable from the finite language $\mathcal{F}$ alone—equivalently, whether the polynomial-time side of this complete fixed-language classification is uniformly recognizable. We settle this problem by giving, for every nonempty finite domain $D$ and every finite exactly encoded algebraic-complex language $\mathcal{F}$, a total exact algorithm that decides all three conditions on the full unbounded family $W_{\mathcal{F}}$. Beyond decidability, we prove that Block Orthogonality alone forces both Type Partition and the existence of a single Mal'tsev operation preserving all generated support and row-equivalence relations. Thus the three-condition characterization collapses to Block Orthogonality, and the finite input $(D,\mathcal{F})$ determines which side of the dichotomy applies. The same framework decides the corresponding conditions in the dichotomy theorem for degree-multiple counting CSP proved by Lin.

For each $N\geq1$, consider the normalized König bilinear form $B_{\mathrm K}:L_\infty(\mathbb R^N)\times L_\infty(\mathbb R^N)\to\mathbb R$ given by \[ B_{\mathrm K}(f,g):=\frac{1}{(\sqrt{2}\pi)^N} \iint_{\mathbb R^N\times\mathbb R^N} f(x)g(y)e^{-(\lVert x\rVert^2+\lVert y\rVert^2)/2} \sin\langle x,y\rangle\,\mathrm d x\,\mathrm d y, \] We define the König constant by \[ \mathfrak K_{\mathrm K}:=\sup_{N\geq1}\sup_{\substack{f,g:\mathbb R^N\to\{\pm1\}\\ f,g\ \mathrm{measurable}}}B_{\mathrm K}(f,g). \] The study of this bilinear form arose from efforts to determine the exact value of the Grothendieck constant. König~\cite{KONIG} conjectured that the sharp value should instead be given by the one-dimensional half-spaces $B_{\mathrm K}(\operatorname{sgn}(x_1),\operatorname{sgn}(x_1))=\frac{2}{\pi}\log(1+\sqrt{2})$. A positive answer to this conjecture, together with a classical upper bound of Krivine \cite{KRIVINE}, would determine the exact value of the Grothendieck constant. In a breakthrough~\cite{BMMN}, Braverman, Makarychev, Makarychev, and Naor disproved König's conjecture already in dimension two and used their counterexamples to obtain the first strict improvement over Krivine's bound. One question in \cite{BMMN} attempts to determine the Grothendieck constant through alternating Krivine rounding schemes arising from König's bilinear form in high dimension. More recently, Li et al.~\cite{LISK} constructed high-dimensional examples showing that $\mathfrak K_{\mathrm K}\ge 0.59357$. An elementary Fourier argument gives $\mathfrak K_{\mathrm K}\le 1$ and excludes equality for every finite-dimension. In this paper, we prove that $\mathfrak K_{\mathrm K}=1$ by constructing a family of Boolean pairs in high dimensions. In particular, this gives a negative answer to the high-dimensional aspect of the question in \cite{BMMN}.

For every constant $2<p<\infty$ and every constant \[ 0<\varepsilon< \min\left\{\frac{p-2}{4p},\frac18\right\}, \] we show that the $\ell_p$-shortest vector problem for lattices of rank $M$ is NP hard to approximate within a factor of $M^\varepsilon$, via a deterministic reduction. For $p=\infty$, the same holds for every constant $0<\varepsilon<1/8$. The reduction builds on the polynomial-gap CVP construction of OpenAI [OpenAI 2026] and the direct reduction to SVP for $p>2$ of Hair and Sahai [STOC'26].

It is notoriously difficult to obtain deterministic reductions for the Minimum Distance Problem (MDP) and the Shortest Vector Problem (SVP). Under two-sided-error randomized reductions, Bennett, Cheraghchi, Guruswami, and Ribeiro (STOC 2023) proved parameterized hardness of approximation for these problems. We partially derandomize their reductions and present one-sided-error randomized reductions: MDP is W[1]-hard to approximate within an arbitrary constant factor under FPT many-one one-sided-error randomized reductions; For every $p \ge 1$, SVP in the $\ell_p$ norm is W[1]-hard to approximate within an arbitrary constant factor below $2^{1/p}$. We demonstrate the usefulness of one-sided-error randomized reductions by showing that they can be conditionally derandomized when the target problem has an OR function. Under a standard hardness-vs-randomness assumption, namely a plausible lower-bound assumption against nondeterministic circuits, we prove a general theorem formalizing this derandomization. Here, an OR function combines several instances into one instance that preserves their disjunction. We construct such OR functions for the relevant MDP and SVP gap problems, and thereby obtain deterministic W[1]-hardness for approximating MDP over every fixed finite field within every constant factor, and for approximating SVP in $\ell_p$ norms for every fixed integer $p$ within every factor below $2^{1/p}$. Applying the same framework to Micciancio's one-sided-error randomized reduction (ToC 2012) yields, under the same circuit lower-bound assumption, deterministic polynomial-time NP-hardness of approximating Euclidean SVP within every constant factor.

We study online probabilistic forecasting of binary outcomes chosen by an adaptive adversary. Given an online learning algorithm for a weak hypothesis class $H$, we would like to efficiently obtain two incomparable guarantees that existing online boosting techniques provide separately. Online gradient boosting competes in Brier score with the best predictor induced by the span of $H$ on every sequence, but promises nothing when the span does not contain an accurate predictor. Online weak-to-strong boosting drives classification error to zero under a weak-learning condition, but promises little when that condition fails. We give a simple defensive forecasting algorithm, the Defensive Booster, that obtains both guarantees. On every adaptive sequence, its Brier score is competitive with the best prediction induced by the span of $H$ at the same rate as online gradient boosting; simultaneously, whenever the realized transcript satisfies the smooth weak-learning condition, its Brier score and randomized classification error satisfy the same rate guarantee as online classification boosting. This is achieved by operationalizing the "dual view" of boosting: When the algorithm's randomized classification error is persistently high, its mistake weights form a smooth reweighting on which every weak hypothesis has low edge, yielding an ex-post hard-core certificate that the weak-learning condition fails. We also develop a strongly adaptive variant, which satisfies both guarantees on every time interval. The Defensive Booster is very efficient: it accesses just one weak-class learner, whereas the prior online boosting methods we compare against maintain large weak-learner ensembles. Experiments on synthetic and real data streams demonstrate its strong predictive performance (sometimes substantially improving over all prior baselines) coupled with orders-of-magnitude faster runtime.

Two graphs $G$ and $H$ are homomorphism indistinguishable over a graph class $\mathcal{F}$ if they admit the same number of homomorphisms from every graph in $\mathcal{F}$. A wide range of relaxations of graph isomorphism arise this way: isomorphism itself over the class of all graphs [Lovász, Acta Math. Hung. 1967], equivalence under the $k$-dimensional Weisfeiler-Leman algorithm over the graphs of treewidth $\leq k$ [Dvořák, J. Graph Theory 2010], and quantum isomorphism over planar graphs [Mančinska-Roberson, FOCS 2020]. Since the class $\mathcal{F}$ is typically infinite, it is not clear a priori whether homomorphism indistinguishability over $\mathcal{F}$ is decidable; for planar graphs it is undecidable. Every class for which decidability was previously known is sparse. We give the first decidability results for dense graph classes: We introduce the dense Weisfeiler-Leman algorithm that decides homomorphism indistinguishability over the class of graphs of cliquewidth $\leq k$, the dense counterpart of treewidth. This relation was not previously known to be decidable. The algorithm colors $k$-tuples of vertex subsets rather than $k$-tuples of vertices. Beyond the class of all graphs of cliquewidth $\leq k$, we prove a general meta-theorem: homomorphism indistinguishability over every $\mathsf{CMSO}_1$-definable graph class of bounded cliquewidth is decidable, in randomized exponential time. For classes of bounded linear cliquewidth the bound improves to $\mathsf{PSPACE}$, and we show this is tight by exhibiting such a class for which the problem is $\mathsf{PSPACE}$-complete. These are the first general algorithms for homomorphism indistinguishability over dense graph classes.

The $(\min,+)$ convolution is a central problem in fine-grained complexity, and it remains open whether it can be computed in truly subquadratic time. We study it through tropical polynomials, where $(\min,+)$ convolution is exactly tropical polynomial multiplication. We introduce the tropical decomposition width, $\operatorname{tdw}(A)$, which measures how finely a tropical polynomial can be decomposed into factors of small degree. We prove two modular convexity theorems showing that bounded tropical decomposition width forces convexity on arithmetic progression subpolynomials. This yields deterministic algorithms for computing $a\otimes b$ in $$O\left(n\max(\operatorname{tdw}(a),\operatorname{tdw}(b))^2\right)$$ when $\max(\operatorname{tdw}(a),\operatorname{tdw}(b))$ is given, and in $$O\left(ne^{\min(\operatorname{tdw}(a),\operatorname{tdw}(b))(1+o(1))}\right)$$ without prior knowledge of the width. Neither algorithm requires a decomposition of the input sequences. The same structural ideas give a randomized algorithm for Multiple-Sequence $(\min,+)$ Convolution: given $k$ sequences of length at most $n$, their convolution can be computed in $$O\left(kn^2\sqrt{\min(k,n)}\log^{1.5}(kn)\right)$$ time, improving the natural $O(k^2n^2)$ bound. Finally, we introduce interpolation algebras for tropical polynomials and show that classes with bounded tropical decomposition width admit interpolation algebras of finite generating rank, whereas distinguishing all tropical polynomials of degree at most $n$ requires generating rank $\lfloor n/2\rfloor+1$. We also prove that tropical decomposition width cannot decrease under any flat $\mathbb T$-algebra extension. Together, these results connect the tractability of $(\min,+)$ convolution with structural rigidity in tropical polynomial multiplication.

This article provides an assignment designed to let undergraduate students who have completed an undergraduate CS1/CS2 sequence try to themselves, in groups, prove Fortune's Theorem. (Fortune's Theorem states that if the complement of the Boolean satisfiability problem polynomial-time reduces to a sparse set, then the Boolean satisfiability problem is polynomial-time computable. The assignment does not assume that students have previously seen the Boolean satisfiability problem, polynomial-time reductions, or sparse sets. Rather, it teaches those within the assignment. Note: Reworded into the technical vocabulary of complexity theory, Fortune's Theorem states that no sparse set is coNP-hard unless P=NP. Fortune's Theorem was a major advance in the understanding of the relationship between hardness and density.) We provide both the assignment handout (as the main body of this report plus Appendix A) and a solution to the assignment (as Appendix B, which would of course not be made available to the students until after they had handed in the assignment). The assignment handout, though the instructor can change this, is framed as having the students starting the assignment in teams in class for a whole class session, and then finishing it in those same teams as a take-home assignment, and handing it in before the next class session. We have found that student groups often succeed, partially or completely, in this challenge. This can mean a lot to the students: they see that they were able to make an advance that, when it was first obtained, appeared in what was arguably at the time the top journal venue for complexity theory research. This can give them confidence that they have substantial problem-solving skills (which basically means research skills) when they truly apply themselves to a given challenge.

Multi-Agent Path Finding for Large Agents (LA-MAPF) is a geometric variant of MAPF in which agents are modeled as disks and conflicts are determined by physical overlap in the underlying Euclidean workspace. The goal of LA-MAPF is to decide whether there exists a sequence of conflict-free transitions from a start configuration to a goal configuration. Agafonov and Yakovlev proved that LA-MAPF is NP-hard. In this paper, we strengthen their result by proving that LA-MAPF is PSPACE-complete via a polynomial-time reduction from Restricted Sliding Tokens.

Multi-layer transformers form the critical component of essentially all large language models (LLMs) in use today. Because of their ubiquity and computational capability, there is a rapidly growing body of work that aims to precisely calibrate the expressive power of transformers as language recognizers by comparing them against standard models of computation studied for decades by the theoretical computer science community. In this endeavor, circuit complexity has by and large emerged as the "correct" branch of computational complexity to analyze the expressive power of transformers; the reason is that parameterizing transformers by the various resources they use, such as attention and precision, leads to direct comparisons with different classes of circuits parameterized by resources such as type of gates, size, and depth. Here, we present an overview of selected results that delineate the expressive power of transformers using concepts and methods from circuit complexity.

We prove that, for every constant $\rho>1$, the Euclidean shortest vector problem is NP-hard to approximate within any constant factor $\rho$ under a deterministic polynomial-time many-one reduction. This extends our previous deterministic NP-hardness result from $\rho<\sqrt 2$ to arbitrary constants and gives a deterministic version of Khot's randomized arbitrary-constant theorem.

Dadush et al.\ (2024) recently developed a scaling-invariant layered least squares algorithm for linear programming whose complexity depends on the optimal condition measure $\bar{\chi}_A^*$. Their work builds on Vavasis and Ye's (1996) algorithm whose running time depends only on the constraint matrix $A$ through the condition number $\bar{\chi}_A$. Monteiro-Tsuchiya (2003) defined the optimal condition number $\bar{\chi}_A^*$ as the maximum $\bar{\chi}_{AD}$ achievable over all positive diagonal column rescalings $D$. Dadush et al.\ (2024) introduced the optimal circuit imbalance measure $\kappa_W^*$, which serves as a lower bound for $\bar{\chi}^*_A$. Instances with artificially large optimal circuit imbalance measures $\kappa_W^*$ can be easily constructed; however, finding naturally occurring examples where this optimal scaling-invariant measure grows exponentially is of independent interest. In this paper, we show that the Ben-Tal Nemirovski (BN) linear programming approximation of the unit disk provides such an example. By explicitly constructing circuits in the kernel of the BN formulation, we prove that the optimal circuit imbalance measure $\kappa_W^*$ grows exponentially in the number of approximation steps. Since $\kappa_W^*$ lower bounds $\bar{\chi}_A^*$, our result demonstrates that the BN approximation yields an exponentially ill-conditioned family of constraint matrices.

We study nonnegative submodular maximization on $n$ elements subject to a general matroid of rank $k$, when the offline algorithm is given an arbitrary controlled value oracle. Our main result is an adversarial resilience theorem for the Spiteful Greedy Swap Poisson Process (SGS-Poisson): without modifying its Poisson intensity, single-element exchange rule, or spiteful drop step, the algorithm retains limiting approximation factors $1/e$ for non-monotone objectives and $1-1/e$ for monotone objectives. More precisely, given an error bound $\xi\ge0$, under every controlled oracle $\widehat f$ satisfying $|\widehat f(S)-f(S)|\le \xi$ for every set $S$, our implementation returns a feasible set with expected value at least $(1/e-\varepsilon)OPT-O(k\xi)$ and $(1-1/e-\varepsilon)OPT-O(k\xi)$, respectively, where $OPT$ is the feasible optimum. The implementation uses a deterministically bounded budget of $O(nk^{2}\varepsilon^{-2}\log n\log^{2}(1/\varepsilon))$ oracle calls. As a consequence, an offline-to-online reduction yields full-bandit combinatorial multi-armed bandit (CMAB) algorithms for general matroid-constrained submodular rewards with exact limiting approximation-regret factors $1/e$ and $1-1/e$ and $\widetilde O(n^{1/5}k^{4/5}T^{4/5})$ regret over $T$ rounds. These online guarantees allow exploration to play sets that become independent after deleting at most one element; exploitation and the benchmark remain matroid-feasible. For unit-capacity partition matroids we obtain $\widetilde O(n^{1/5}k^{3/5}T^{4/5})$ under the same exploration relaxation. We establish a deterministic query budget by truncating the Poisson process and identify the enlarged action set needed to answer its offline queries.

We prove a general upper bound for scaling windows of sparse monotone covering problems. From that, we deduce that for every fixed value $k\geq 3$, the window of random $k$-SAT is $O(n/\log n)$, improving the Friedgut-Bourgain bound of $O(n/\log\log n)$. We also show that random signed Not-All-Equal-$k$-SAT and hypergraph non-two-colourability (Property B) have windows of the same order. Our upper bound for scaling windows of sparse monotone covering problems follows from a general strategy combining the strengthening of Bourgain's sharp threshold theorem by Keevash, Lifshitz, Long, and Minzer with a local-to-random replacement principle. This provides a systematic method for proving scaling-window bounds, addressing a question of Perkins.

Evaluating expectation values is a critical task for variational quantum eigensolvers, parameterized quantum circuits, and many other quantum algorithms. We consider the well-studied case of the Quantum Approximate Optimization Algorithm (QAOA) for the MaxCut problem. Recent work of Wang et al. [arXiv:2511.20212] showed this task to be NP-hard in general for any QAOA depth $p\geq 2$, complementing past results showing efficiently computable formulas for $p=1$ with arbitrary problem graphs. We sharpen this dichotomy showing that for $p\geq 2$ exact or exponentially precise cost expectation value evaluation is #P-hard under deterministic polynomial-time Turing reductions. Hardness at $p\geq 2$ is shown to remain even for evaluating single pairwise correlators $\langle Z\otimes Z\rangle $, as well as for highly restricted sets of algorithm parameters. Our proof refines the NP-hardness construction of Wang et al. that recovers the maximum cut value from the largest exponent of a QAOA Laurent polynomial, utilizing a distinct and simpler construction that extracts a value proportional to the total number of maximum cuts, in addition to the optimal cut value. Thus we show that the QAOA expectation value hardness transition from $p=1$ to $p=2$ is not only from tractability to optimization hardness, but to that of counting optimal solutions. As an application we show our results imply analogous hardness results for computing gradients and Hessians of QAOA circuits.

The computability of real numbers and functions using Turing Machines has been a central area of theoretical computer science since the mid-20th century. In the late 20th century, it was shown that chemical reactions can serve as a basis for computation using the Chemical Reaction Network (CRN) model. Recent advances in computing real numbers using Deterministic Chemical Reaction Networks (DCRNs) have identified numerous classes of DCRN-computable real numbers. In parallel, the works of R. Landauer and C. H. Bennett, spanning the 1960s to the early 2000s, showed that reversible computing offers significant advantages over irreversible methods, particularly in energy efficiency, motivating extensive research on reversible computation. In this work, we investigate the computability of real numbers using Reversible Chemical Reaction Networks (RevCRNs). The paper has two primary contributions: (1) establishing relationships among CRN-computable real number classes including Lyapunov CRN ($\mathbb{R}_{LCRN}$), Real-Time CRN ($\mathbb{R}_{RTCRN}$), rational numbers ($\mathbb{Q}$), and RevCRNs ($\mathbb{R}_{RevCRN}$), with key results: (i) $\mathbb{Q}$ is a strict subset of $\mathbb{R}_{RevCRN}$; (ii) the set of positive algebraic numbers ($ALG$), $\mathbb{R}_{LCRN}$, and real numbers computable by 1-species RevCRN ($\mathbb{R}_{RevCRN}^{1s}$) are equal; (iii) $\mathbb{R}_{RTCRN}$ and $\mathbb{R}_{RevCRN}$ exhibit non-empty overlap; and (iv) the set of real numbers computable by detailed-balanced RevCRNs ($\mathbb{R}^{DetBal}_{RevCRN}$) is a subset of $ALG$; and (2) exploring the existence of a hierarchy within $\mathbb{R}_{RevCRN}$. Finally, we leave open the exact relationship between $\mathbb{R}_{RevCRN}$ and $\mathbb{R}_{RTCRN}$ while conjecturing a general hierarchy of RevCRN-computable reals.

A classical theorem due to Friedgut, Kalai and Naor asserts that if a function $f\colon \{0,1\}^n\to\{-1,1\}$ close to a degree $1$ function, then either $f$ or $-f$ is close to either the all $1$ function, or to $(-1)^{x_i}$ for some $i\in [n]$. We prove a version of their theorem for the Grassmann scheme over $\mathbb{F}_2$. More precisely, we prove if a function $f\colon \genfrac{[}{]}{0pt}{}{\mathbb{F}_2^n}{\ell}\to\{0,1\}$ is close to a degree $1$ function, then either $f$ or $1-f$ must be close to a function of the form $g(L) = \sum_{x\in\mathcal{X}}1_{x\in L}+\sum_{W\in\mathcal{W}}1_{L\subseteq W}$, where $\mathcal{X}\subseteq\mathbb{F}_2^n$ is a set of points and $\mathcal{W}$ is a set of hyperplanes in $\mathbb{F}_2^n$.

AI agents are increasingly used in mathematics research, but it is often unclear how to use them effectively. Towards this, we present an extensive case study of how AI was used to improve bounds on the Grothendieck constant $K_G$, which captures the hardness between combinatorial problems and their continuous relaxations. Specifically, while the precise value of $K_G$ is not known, we recently tightened the best known bounds to \[ \frac{6\pi}{11} \;\le\; K_G \;\le\; \frac{\pi}{2\log(1+\sqrt2)} - 10^{-4}. \] Crucially, these improvements were achieved using an AI research system that could arrive at insights deemed novel by domain experts. We give a detailed discussion of our experience using AI for mathematics research, particularly touching upon its strengths and weaknesses, as well as our experience with creating ideal conditions for AI to arrive at breakthrough insights.

When a probabilistic predictor answers many conditional-probability queries, are its answers self-consistent, and can this be verified in polynomial time? This problem is of interest for AI safety, where safety is derived from honesty about probabilistic predictions of unwanted outcomes potentially caused by an AI action. We construct an interactive PCP as follows. Let a predictive model be specified by a probability circuit P and a circuit Q which outputs confidence in predictions. Together, P and Q implicitly specify exponentially many probabilistic claims. We show a protocol in which a polynomial-time verifier can verify the approximate consistency of (P,Q). The verifier is given the pair of circuits (P,Q), which it evaluates at only a few points; alongside them it is given a proof oracle, an encoding of a witnessing probability distribution allegedly consistent with the predictions of (P,Q), which it reads at a few locations while interacting with a single untrusted prover. En route, we must ensure the existence of a sparse witnessing distribution consistent with the model's predictions. To do so, we first consider witness distributions for the consistency of explicit probabilistic claims, rather than claims specified by a predictor: say m claims, each of the form Pr[Y = 1 | X = x] = p, over n Boolean variables. Building on work initiated by Nilsson (Artif. Intell., 1986), we place l_2-approximate probabilistic consistency of explicit claims in NP, with certificates of length O(mn + log B) in the input bit-precision B; we further show how a small additive completeness-soundness gap removes the dependence on B. Together these results provide a complexity-theoretic foundation for certifying the self-consistency of probabilistic predictors. We view our interactive PCP as a first step toward training predictive models to prove their own consistency.

We establish new bounds on the Grothendieck constant $K_G$: \[ \frac{6\pi}{11} \le K_G \le \frac{\pi}{2\log(1+\sqrt2)} - 10^{-4}. \] Methodologically, our lower bound approach differs from previous works by establishing limitations on the asymptotically optimal Krivine schemes, rather than giving explicit constructions of gap instances. Our upper bound is obtained by proposing and analyzing the first asymptotic construction of rounding schemes, whereas previous works only consider low-dimensional schemes. Together, these bounds determine the previously unknown tenths digit of $K_G$ to be $7$. The bounds were discovered by a long-running collaborative effort of humans and a long-horizon AI research system that we engineered.

We prove inference-time quantum coordination advantages for specified AI state-tracking tasks. A solver compresses semantic history into a future-accessible boundary state and later answers a query. We count communication $B$, persistent instance-dependent memory $M$, and local work $D$; classical recurrence, caches, tools, and recomputation are allowed and charged. The central result is a boundary-preserving semantic-compilation theorem. It maps a finite one-way, streaming, or adaptive causal task into a semantic AI interface while preserving event order and access to past input. Classical boundary-state lower bounds and quantum-memory upper bounds transfer up to explicit compiler overhead, independently of the finite-precision recurrent architecture. Two applications have classical semantics. Matched-entity synopsis QA inherits the hidden-matching separation between $O(\log N)$ qubits and $\Omega(\sqrt{N})$ classical boundary bits. Continual requirements auditing inherits a Max-$k$SAT streaming separation: a recurrent solver uses $O(\log^5 n\log(1/\delta))$ qubits and polylogarithmic classical workspace to obtain a $0.7172$-approximation, whereas every classical one-pass finite-information solver attaining that ratio requires $\Omega(\sqrt{n})$ coordination width. As a quantum-native compiler test, a stabilizer latent-state dialogue uses $n$ qubits, while every exact finite-state classical causal online realization satisfies $B+M \ge \frac{1}{2}n^2+(\frac{3}{2}-\log_2 3)n+O(1)$. The source protocols, streaming algorithms, and stabilizer witness are imported; the new result is their architecture-independent semantic transfer. These are memory and coordination separations, not runtime or empirical advantages for present-day language models. The stabilizer result assumes exact simulation and ideal noiseless quantum memory.

Shellsort repeatedly runs insertion sort with decreasing gaps, so its worst-case cost depends on the gap sequence. Pratt's $2^u3^v$ sequence, one of the few systematic constructions with a proven $O(n\log^2 n)$ bound, includes every product below $n$ of two base numbers, or generators. We ask whether adding more base numbers, and thus more intermediate gaps, can improve this full product grid. We show that it cannot when every product is retained and each base is at most a fixed power of the smallest. With $r$ independent bases (different exponent choices give different products) and $\Theta(\log n)$ gaps, the best possible worst-case cost is $n\exp(\Theta((\log n)^{1-1/r}))$. Thus two bases give the exponent $\sqrt{\log n}$, whereas three give $(\log n)^{2/3}$: more bases are worse. With a budget of $p$ gaps, matching bounds give the factor $\exp(\Theta(\log n/p^{1/r}))$ beyond linear cost. The reason is simple. Few products force the smallest base $m$ to be large, and fullness makes $m$ the next-to-last gap. An input built from reversed blocks is already sorted for every earlier gap, forcing $\Omega(nm)$ work in the final pass. Powers of distinct primes give a matching construction. For arbitrary gaps, we count current-gap multiples that earlier gaps cannot form. This gives upper and lower bounds for individual passes. A Fourier argument gives necessary conditions for small total cost, while short nonnegative sums give sufficient conditions. In both settings, useful distances must be available before they are needed.

A tensor has border rank at most $r$ if it can be written as $T=\lim_{\varepsilon \rightarrow 0} T(\varepsilon)$ where $T(\varepsilon)$ has rank at most $r$ for all sufficiently small $\varepsilon$. It is known that the map $\varepsilon \mapsto T(\varepsilon)$ can be assumed to be a (tensor valued) polynomial in $\varepsilon$. The smallest possible degree of such a map is called the error degree of $T$. The error degree and the related notion of order of degeneration are the two key quantities that we study in this paper. One motivation comes from debordering: by polynomial interpolation on the map $\varepsilon \mapsto T(\varepsilon)$ we can upper bound the tensor rank of $T$. For order 3 tensors, exponential upper bounds on the error degree and degeneration order were given almost 40 years ago in (Lehmkuhl Lickteig, 1989) and were not improved ever since. In this paper we give bounds that apply to a wide class of tensors, exponentially improving on (Lehmkuhl Lickteig, 1989). Our results are most general for tensors with 3 slices (format $m \times n \times 3$). In this case, our main assumption is on the rank of the matrix slices. We also give bounds that apply to arbitrary rectangular formats ($m \times n \times p$). In this case, we need an additional 1-regularity assumption on one of the slices of the tensor (recall that a matrix is said to be 1-regular if its eigenspaces are 1-dimensional). Under these assumptions we show that the error degree is at most 1, which yields a nontrivial debordering result (tensor rank at most $2r$ for border rank $r$). The results in (Lehmkuhl Lickteig, 1989) rely on an upper bound on the degree of the variety of tensors of border rank at most $r$. We rely instead on more specific properties of this algebraic variety, and in particular on commutativity properties of certain matrices derived from the tensor slices.

Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning $n$-qubit quantum unitaries $U$ and Hamiltonians $H$, given query access to $U$ or the unitary evolution of $H$, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form $U = \sum_i \alpha_i C_i$ over Cliffords $C_i$ with bounded Clifford extent $\sum_i |\alpha_i|$. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary $U$ with optimal Clifford fidelity $\textsf{opt}$, outputs a Clifford unitary witnessing fidelity $\geq \textsf{opt} - \varepsilon$ for some error $\varepsilon > 0$, in time $\textsf{poly}(n,(1/\varepsilon)^{\log(1/\varepsilon)})$. We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity $\Omega(2^n)$) in the Pauli basis but are Clifford structured.

Vehicle platooning offers significant benefits, including reduced energy consumption, lower emissions, improved road utilization, enhanced safety, and reduced driver fatigue. As intelligent driving technologies continue to advance, platoon sizes are expected to increase substantially, making the efficient sequencing and resequencing of vehicles increasingly important. We study the vehicle platoon sequencing and resequencing problem on road networks with varying segment lengths under two fundamental objectives: minimizing total energy consumption and minimizing the maximum energy consumption of any vehicle. For the typically encountered combinations of vehicle and road characteristics, we provide a complete computational complexity classification, either developing polynomial-time algorithms or proving computational intractability. For several intractable cases, we design fully polynomial-time approximation schemes and polynomial-time heuristics with provable performance guarantees. A computational study demonstrates that the proposed heuristics achieve average solutions within 1% of optimal. We also consider settings in which only limited information about position-dependent energy savings is available and develop a heuristic with bounded worst-case performance. In addition, we present an efficient algorithm for on-road vehicle resequencing when only limited position changes are permitted. Together, these results provide a comprehensive algorithmic framework for energy-efficient vehicle platoon sequencing and resequencing.

For a constant $\eta \geq 0$, Pathwidth-$\eta$ Deletion is the problem of deciding whether, for a given graph $G$ and integer $k$, there is a set $S \subseteq V(G)$ of size at most $k$ such that the pathwidth of $G - S$ is at most $\eta$. The problems Treewidth-$\eta$ Deletion and Treedepth-$\eta$ Deletion are defined similarly for the parameters treewidth and treedepth, respectively. A landmark result of Fomin et al. [FOCS, 2012] shows that, for any constant $\eta$, all three problems admit a kernel on $O(k^{c(\eta)})$ vertices, where $c(\eta)$ is a constant depending on $\eta$. Giannopoulou et al. [ACM TALG, 2017] show that, in some sense, this result is optimal for Treewidth-$\eta$ Deletion: for $\eta \geq 2$ and even when parameterizing by the size of a vertex cover $M$ of the input graph, there is no kernel of size $O(|M|^{\frac{\eta+1}{2}-\varepsilon})$, for any $\varepsilon > 0$. Contrasting this result, they prove that Treedepth-$\eta$ Deletion admits a uniform polynomial kernel, that is, a kernel of size $O(k^c)$ for a constant $c$ that is independent of $\eta$. In comparison, the question whether Pathwidth-$\eta$ Deletion admits a uniform polynomial kernel has been neglected in the literature. As treewidth and pathwidth tend to behave similarly, it is natural to expect that no uniform kernel exists when parameterizing by the size of a vertex cover. Surprisingly, we show this not to be the case. More concretely, we prove the existence of a uniform polynomial kernel for Pathwidth-$\eta$ Deletion when parameterizing by (1) the solution size $k$ plus the size of a set $M$ such that $G - M$ has bounded treedepth; (2) the (vertex-deletion) distance to pathwidth-$1$ graphs; (3) the distance to the class of graphs with treedepth at most $\eta + 1$. This leads us to conjecture that Pathwidth-$\eta$ Deletion admits a uniform kernel when parameterizing by the solution size $k$.