Theoretical computer science

FlashProve: an open-source library for provable inference

Roy Rinberg, Alex Allain, Alessandro Chiesa, Miranda Christ, Rahul Dalal, Giacomo Fenzi, Ben Mayer, Guy Weissenberg

FlashProve combines a hiding weight commitment with a succinct cryptographic proof of integer-model inference for Llama 4 Maverick. For a batch of 24 requests with 1,024-token contexts, the authors report about 223 seconds on one H100 GPU and 24 CPU cores, with one selected token checked per request and an 18.78 MB proof for each request. The approximately 110 tokens/second figure counts processed context tokens; checking every token instead gives about 39.1 checked tokens/second in their experiment.

Researcher-$\in -the$-Loop Evolutionary Discovery of Entanglement-Assisted Quantum Code Families

Jae-Hyun Baek, Byung-Sun Won, Jon-Lark Kim

Under researcher-defined targets and an exact evaluator, AlphaEvolve evolved programs that produced finite entanglement-assisted stabilizer quantum codes. One binary code has parameters [[12,1,11;8]], raising the listed distance from 9 to 11 at the same length, encoded-qubit count and entanglement cost. Researchers then identified a pattern, generalized it and proved a separate prime-power family; the family and entanglement lifting together close 54 gaps in the archived tables.

Sharp reset thresholds for bounded-response synchronization games with a sink

Ben Keene

For $n\ge 2$ and $k\ge 1$ with $k=1$ or $n\le k+3$, the largest shortest-reset-word length among n-state $A_{k}$ automata with a fixed sink is $M(n,k)=\sum_{i=1}^{n-1}\lceil i/k\rceil$. Alice chooses one letter per round and Bob replies with fewer than k letters, including the empty word; $A_{k}$ means Alice can force a reset. In particular $M(k+2,k)=k+2$ and $M(k+3,k)=k+4$ for $k\ge 2$, and $M(5,2)=6$.

Group constructions cannot refute the Set Cover Conjecture, including tensor powers

For $k\ge 2$ and $m\ge 1$, a Strassen combinatorial degeneration of a finite group tensor onto the mth tensor power of the balanced tripartitioning tensor $T_{k}$ requires $|G|\ge\binom{3k}{\lfloor 3k/2\rfloor}^{m}>\tau_k^m$, where $\tau_k=\frac{8^k\binom{3k}{k}\binom{2k}{k}}{27^k}$. For single-copy group restrictions, $|G|\ge 2^{3k-1}$; the partition products factor through commuting elements even when G is nonabelian.

Subexponential Deterministic Factoring

Isaac Rudich, Louis-Martin Rousseau

A single deterministic Turing machine outputs the smallest prime factor Nat.minFac N of every natural number N in binary. For each integer $k\ge 1$ there is a constant $C_{k}$ such that its running time on every $n-bit$ input is at most $C_{k}\cdot 2^{\lfloor n/k\rfloor }$; all stack alphabets are finite. Thus the stated deterministic running time is $N^{o(1)}$.

Approximate Counting for Mixed p-Spin Glasses in Weak External Fields via Cluster Expansion

Qiang Wu

For SK and finite mixed Ising p-spin models with all interaction orders at least three, at a fixed margin below the second-moment threshold and homogeneous fields $|h|\le \rho _{0}N^{-1/4}$, algorithms approximate $\log Z_{N}$ to additive error $\varepsilon$ using a number of exact operations polynomial jointly in N, $\varepsilon ^{-1}$ and $\delta ^{-1}$. Symmetric unit-variance disorder is allowed; failure is at most $\delta$ plus an explicit disorder-tail term, which vanishes with a finite fourth moment.

A $2^{o(n)}$ Time Algorithm for 3-SAT

Claude

One deterministic finite-alphabet Mathlib TM2 machine exactly counts the satisfying assignments of $k-CNF$ formulas with $k\ge 1$, $m\ge 2$ distinct clauses and $n\ge 4$ occurring variables in time $2^{O\left(\min\left\{\frac{k^2n\log\log n}{\sqrt{\log n}},\frac{km}{\sqrt{\log m}}\right\}\right)}$, with base-two logarithms and an absolute hidden constant. A separately formalized decision statement refutes ETH.

The Euclidean algorithm is not optimal among uniform processes

Jason Davies

For every positive integer pair $a\ge b$, $\gcd (a,b)$ has a remainder-only derivation using at most $(6+o(1)) \log _{2}(a)/\log _{2}\log _{2}(a)$ remainder calls, uniformly in b. Previously computed values may be reused and the choice of operands is free. This refutes Moschovakis’s stated uniform-process lower-bound conjectures, not the Main Conjecture for algorithms.

$Sum-of$-squares minimizers for a left-shift binary GCD algorithm

For each $n\ge 2$, among ordered positive integer inputs $u\ge v>0$ taking exactly n iterations of the Shallit–Sorenson left-shift binary GCD algorithm, $u^{2}+v^{2}$ has a unique minimum at $(p[n-1],p[n-2])$. Here $p[0]=1$, $p[1]=3$, and $p[j+2]=p[j+1]+p[j]$ for even j, or $2p[j+1]+p[j]$ for odd j.

On the Accuracy of Approximate Leave-$One-Out$ with Blockwise Nonsmooth Regularization in High-dimensions

Honghao Lin, Songbin Liu, Arian Maleki, Vahab Mirrokni, Chen Shang, David P. Woodruff, Hanbo Yang, Wenjin Zhang

Under Assumptions 2.1–2.5, the expected average absolute loss discrepancy between exact leave-$one-out$ fits and each of the two restricted-fit approximations is $O\left(\frac{\log^{3/2}(en)}{\sqrt n}\right)$. The setting has bounded block sizes, a fixed block partition, Gaussian design with covariance eigenvalues comparable to $1/p$, $n/p$ bounded above and below, positive deterministic ridge and penalty parameters, smooth convex loss, finite third score moments and the stated one-sided likelihood-curvature condition.

Exact Storage-Repair-Bandwidth Tradeoffs for (6,5,5) and (7,6,6) Exact-Repair Regenerating Codes

Chao Tian

The manuscript gives converse bounds that completely characterize the storage/repair-bandwidth tradeoffs of exact-repair regenerating codes for $(n,k,d)=(6,5,5)$ and (7,6,6), without assuming linear codes. Previously known layered codes with space sharing attain the bounds.

Erdős Problem 111: bipartizing finite subgraphs of uncountably chromatic graphs

If a graph is not countably colorable, $h_{G}(n)/n$ tends to infinity, where $h_{G}(n)$ is the largest minimum number of edge deletions needed to make an n-vertex subgraph bipartite. Equivalently, a uniform linear deletion bound on all finite subgraphs forces countable colorability. The limit holds for the whole sequence, for graphs of any uncountable chromatic cardinality.

Ten Advances in Mathematics and Theoretical Computer Science

OpenAI

For every finite two-player entangled game G with entangled value below one, the value of winning all n independent repetitions decays exponentially in n; the Chapter 6 bound depends on the gap and answer alphabet sizes.

Persistent failure of Euclidean quartic SOS exactness

An explicit fixed rational cubic in 14 variables gives a quartically regularized polynomial whose exact minimum shift is nonnegative but not a $\sum of$ polynomial squares for every positive regularization parameter. A second explicit cubic has a unique global minimizer with positive-definite Hessian there and retains a strict SOS gap for every positive parameter.

A Limiting Satisfiability Threshold for Every Fixed Clause Size

OpenAI

For every fixed $k\ge 3$, random $k-SAT$ with independent uniformly signed proper clauses sampled with replacement has a positive finite limiting density $\alpha _{k}$: satisfiability probability tends to one below $\alpha _{k}$ and zero above it. The claim makes no assertion at $\alpha _{k}$.

Hyperbolicity Cones Without Semidefinite Lifts

OpenAI

An OpenAI manuscript claims a real homogeneous hyperbolic polynomial whose closed cone has no exact finite affine semidefinite lift, even with arbitrary real coefficients and any finite number of auxiliary variables.

Polynomial Hitting Lists for Noncommutative Rational Formulas

OpenAI

Given unary n and a size bound s, a deterministic machine constructs in polynomial bit time a polynomial-size list of rational matrix tuples of polynomial total output length and common polynomial dimension. Every admissible nonzero noncommutative rational formula over Q of size at most s has a defined, invertible evaluation on a listed tuple.

AI-built Lean program triangulates simple polygons in linear time

For every closed simple polygon with n vertices, including collinear vertices and equal heights, an explicit exact-real-RAM program returns a conforming triangulation with $n-2$ triangles in at most $C(n+1)$ steps and natural words bounded by $K(n+1)$. It is a variant of Chazelle’s algorithm that completes the visibility map directly below $n=2^{30}+2$.

AI-assisted proof gives sharp graph-matrix norm orders

For each fixed finite simple graph shape in the globally injective dense independent-sign model and fixed $p>0$, the pth norm moment has matching upper and lower orders $n^{(h+i_0-s)/2}\log(2n)^{b^*/2}$, with h the role count, $i_{0}$ isolated interior roles, s the minimum boundary-separator size and $b\cdot the$ largest attached floating-component count over minimum separators.

AI-assisted Walsh embedding reaches linear row scaling

For $n=2^{k}$, a fixed real orthonormal $n\times d$ frame, $0<\varepsilon <1$ and $0<\delta <1/2$, two independent sign rerandomizations of the normalized Walsh transform followed by uniform row sampling preserve all squared norms within $\varepsilon$ with probability at least $1-\delta$. The stated row count is $\min\left(n,\left\lceil\frac{8192(d+27\lceil\log_4(4d/\delta)\rceil^3)}{\varepsilon^2}\right\rceil\right)$, which is $O(d/\varepsilon ^{2})$ for fixed $\delta$.

AI-derived bounds for Mazur’s greedy drawing construction

For a well-formed Mazur edge, cycle, series and join scheme with $n\ge 2$ vertices and j nontrivial joins, the span satisfies $T+1\le 2^{j}(n-2j)$, with equality at $(n,j)=(2,0)$ or $2j+3\le n$. Its worst case is $T=2^{(n/2)}-1$ for even n and $T=3\cdot2^{(n-3)/2}-1$ for odd n. Companion theorems give interior dart mass $\le a_{s}b_{s}T$, Dirichlet row norm $\le 2(n-1)^{2}T$ $and |\det M|\le (2(n-1)^{2}T)^{n}$, bound the candidate products $T^{2}|\det M|$ and $T^{3}|\det M|$, and prove $z=\operatorname{adj}(M)u$ with $Mz=\Delta u$ and boundary $z_{s}=\Delta h_{s}(T-h_{s})$ when $h_{s}\le T$, where $\Delta =\det M$.

AI-developed proof improves the permanent-approximation base

For every nonnegative rational $n\times n$ matrix, Anari’s formal development constructs one rational-output algorithm and an absolute constant $c<\sqrt{2}$ with a two-sided $c^{n}$ approximation guarantee for the permanent. It also proves deterministic polynomial time in the ordinary binary input size.

AI-generated certificate candidate for Dittert’s dimension-five inequality

A released AI-generated sum-of-squares and Lean candidate encodes $\Phi (A)\le 1226/625-||A-U_{5}||^{2}_{F}/625$ for nonnegative $5\times 5$ matrices whose entries $\sum to$ five. If its encoding matches the original problem, it implies unique equality at $U_{5}$.

A Four-Terminal Planar Lower Bound and a Sharp Equal-Cost Gadget for Cost-Preserving Unsplittable-Flow Rounding

Matthew Protti

Protti’s planar acyclic four-terminal instance needs upper overload at least 335 when the largest demand is 294 if cost cannot increase. A rational family gives a lower bound $(299-41\sqrt{41})/32\approx 1.139747$ for the unrestricted planar constant.

Non-Acceleration of the Heavy-Ball Method in 1D

Konstantinos Fotopoulos, Michael Helcig, Karl Deck, Jannis Alsbach

Two AI-generated heavy-ball counterexamples separate cycling regions for smooth strongly convex functions. Example 3.2 uses $\kappa =4/5$, $\beta =17/20$ and $L\gamma =18/5$ to admit a primitive $(K,m)=(5,2)$ cycle while excluding all ordered $m=1$ modes. Section 5 uses $L=1$, $(\kappa ,\beta ,\gamma )=(531/10000,4879/10000,32829/12500)$ and a ten-step mixture of modes 2 and 3 with weights 137/500 and 363/500: it supports a four-dimensional cycle but excludes every pure root-of-unity mode.

Formally Verified Autoresearch for Analyzing the Expressivity of Multi-Head Attention

Karthik Viswanathan, Plamen Dimitrov, Stefano Rocca, Sarayu Sirikonda

For the paper’s one-layer, attention-only transformer on Boolean inputs with a dedicated query token and linear threshold readout, the autonomous core results characterize head complexity by sums of admissible linear-fractional functions, bound it below by threshold degree, and determine it exactly for symmetric Boolean functions by the number of sign changes. In particular, $n-bit$ parity requires exactly n heads.

The Exponential Time Hypothesis is False

OpenAI

For each fixed $k\ge 2$, one deterministic finite-tape machine exactly counts satisfying assignments of every canonically encoded $k-CNF$ formula on n variables. With encoding length L, its time is $(L+1)^{O_k(1)}2^{O_k\left(n(\log\log n)^2/\sqrt{\log n}\right)}$ and its visited tape space is polynomial in L at every execution prefix. In particular, fixed-width 3-SAT has a subexponential-time decision algorithm.

Tight weighted paging with delay via mirror descent

Julian Born, Yann Disser, Linda Thelen

Born, Disser and Thelen give a randomized online algorithm for weighted paging with delay whose competitive ratio is $O(\log k)$, matching the classical lower bound. A cache holds k of n pages with positive fetch costs; each request reveals its nondecreasing, continuous, unbounded delay-cost function when it arrives. The expected fetch-plus-delay cost is bounded relative to an optimal offline schedule, with an additive term depending on k and the page weights, not the requests.

Anthropic reports: Claude reconstructs NIST elliptic-curve seed generation

Anthropic reports recovering a reproducible lrand48-and-timestamp recipe for all five NIST prime-curve seeds, five additional ANSI prime-curve seeds and four NIST binary-curve seeds. The reported timestamps and candidate indices regenerate each $160-bit$ public seed. The NIST $B-163$ seed remains unexplained.

Revisiting Separators in String Graphs, Region Intersection Graphs, and Induced-Minor-Free Graphs

James Davies, Paweł Rzążewski, Jack Spalding-Jamieson, Bartosz Walczak

The AI-origin improvement in Appendix B gives non-expansive line embeddings with $O(\log h)$ average distortion for the stated vertex-weighted metrics of connected graphs excluding the one-subdivision of $K_{h}$ as an induced minor. The paper derives balanced separators of size $O(h \log h \sqrt{m})$ for the corresponding m-edge graphs.

AI-led proof gives a sharp global squared-law transport bound

For any real law with $X^{2}$ in [A,B], $A=3-\sqrt{6}$ and $B=3+\sqrt{6}$, let $\delta =3(E[X^{2}])^{2}-E[X^{4}]$ and let $X_{0}$ be the four-node Gaussian quadrature law identified by zero deficit. For every feasible $0\le \delta \le 30+12\sqrt{6}$, $W1(L(X^2),L(X_0^2))\le\sqrt{\delta/3}$, using ordinary infimum-over-couplings Wasserstein distance. The bound is attained at every feasible deficit and does not require symmetry of X.

AI-led proof gives an optimal eighth-order MGF gap

For every symmetric law with $X^{2}$ in [A,B], $A=3-\sqrt{6}$ and $B=3+\sqrt{6}$, set $v=E[X^{2}]$ and $h=E[(X^{2}-A)(B-X^{2})]$. For every real t, $\exp(vt^2/2)-\mathbb E\exp(tX)\ge ht^4/24+t^8/25200$. Both coefficients are optimal for this two-term bound. A positive coefficient on the intrinsic fourth deficit $3v^{2}-E[X^{4}]$ cannot be paired with the optimal eighth-order coefficient.

Discovering state-$of-the-art$ quantum circuits with large language models

Andi Gu, Alek H. Kemeny, Susanne F. Yelin, Mikhail D. Lukin

Gu, Kemeny, Yelin and Lukin report lower Toffoli and peak-qubit counts in seven specified circuit benchmarks, plus a new prime-field modular-inversion architecture. For fixed-point Gaussian evaluation, their stated benchmark falls from about 24,000 Toffolis and 362 qubits to 1,583 Toffolis and 139 qubits; the reported worst-case error is $9.99\times 10^{-8}$.

At the Limits of Computability: Steps Towards Autonomous AI Discovery on the Busy Beaver Frontier

Marco Dos Santos, Vivek Veeriah, Alex Havrilla, Andrew Bolt, Goran Zuzic, Satinder Singh, Tom Zahavy

A Gemini agent pipeline discovered and formally proved closed systems of Collatz-like acceleration rules for eleven specified six-state, two-symbol Turing machines. Each system summarizes exact execution from its fixed blank-tape starting configuration; the machines’ eventual halting behavior remains unresolved.

Claude agents construct quasi-uniform digital nets in every dimension

For every $s\ge 3$, allowed base q and $k\ge 1$, the explicit $N=q^{(sk)}$ digital net has covering radius $\le \sqrt{s}$ $N^{(-1/s)}$; when $q\ge 5a\cdot _{s}+4$ its point separation $is \ge (1-a\cdot _{s}/q)N^{(-1/s)}$, with the stated bound on $a\cdot _{s}$.

Claude-assisted proof gives quantitative stability for optimal qubit cloning

For any finite-Kraus 1→2 qubit channel whose mean fidelity over the six Pauli eigenstates is at least $5/6-\varepsilon$, the Kraus operators have total squared Frobenius distance at most $6\varepsilon$ from the span of the two Bužek–Hillery Kraus operators. For every input matrix $\rho$, the channel output is within $200\sqrt{\varepsilon }\Vert \rho \Vert F$ of the Bužek–Hillery channel in Frobenius norm.

GPT-assisted proof establishes the full last-gradient curve for smooth convex descent

For every $N\ge 0$ and $h\ge 0$, constant-step gradient descent $x_{i+1}=x_{i}-(h/L)\nabla f(x_{i})$ on a differentiable convex function with L-Lipschitz gradient in a real Hilbert space satisfies $\lVert\nabla f(xN)\rVert\le L\lVert x0-x^*\rVert\max\{1/(1+Nh),|1-h|^N\}$. One-dimensional Huber and quadratic examples attain the two branches. The compared Lean contract also classifies sampled equality trajectories and proves the same sharp factor for the terminal residual of relaxed proximal minimization with actual minimizers.

GPT-assisted proof finds exact robust gaps for finite chiral chains

For a finite open chain with positive strong-bond lower bounds $\beta _{i}$, boundary parameter $s\ge 0$ and weak-to-strong ratios $q_{i}\in [\ell _{i},\rho _{i}]$, the minimum scalar squared gap minq $\lambda \min (D\beta Q(q)^{T}Q(q)D\beta )$ is positive and equals the minimum over the ordered one-switch endpoint vectors $q^{(^{k})}$, with lower endpoints before k and upper endpoints after k. The same value sharply bounds the squared nonzero gap for arbitrary finite-dimensional complex matrix channels satisfying the stated singular-value constraints.

Explicit circuits for the Walsh–Hadamard transform below the textbook operation count

Jacob Sussman

For every commutative ring R and every $k\ge 0$, the exact, unscaled Walsh–Hadamard transform on $N=2^{k}$ inputs has a straight-line circuit with at most (3/4) N $\log _{2}$ $N + N/4$ lines. Each line creates $u+c\cdot v$ or $c\cdot v-u$ from available values, with a fixed ring constant c, and costs one. Reuse, output selection and permutations are free.

GPT-assisted proof finds the sharp robustness radius for a four-row permanent inequality

For a balanced probability law $\nu$ on the 24 permutations of four labels at total-variation distance at most $r\le 1/24$ from uniform, and nonnegative rows $f_{i}$ normalized by the uniform mean of $f_{i}^{2}$ equal to one, $1-\mathbb E_{\nu}\prod_i f_i(\sigma(i))\ge\frac{1-24r}{9}\sum_i\operatorname{Var}(f_i)$. The coefficient is sharp at each radius and 1/24 is the exact admissible radius.

Claude agents tighten the formalized 3SUM and APSP exponents

Deterministic integer 3SUM in $O(n^{1.99896})$ and APSP in $O(n^{2.99791})$ in the pinned upstream word RAM model, for polynomially bounded input numbers.

Proudfoot–Perrault reports: a laser-method exponent below 2.3710449

Proudfoot and Perrault report that the exact tensor-rank matrix-multiplication exponent is strictly below 2.3710449 over every commutative ring. Their formal theorem uses the exact rational bound 23710449/10000000; the accompanying paper rounds this to 2.371045.

Navot: AI-assisted extensions of the 9/4 matrix multiplication bound to fields and rings

Navot’s AI-assisted Lean developments extend OpenAI’s matrix multiplication exponent bound $\omega \le 9/4$ from complex numbers to every field, including finite fields and positive characteristic, and subsequently to every associative unital ring, including noncommutative rings. The ring development establishes exact integer coefficient tensor-rank identities and, for every $\varepsilon > 0$, correct division-free arithmetic programs with cost at most C $n^{(9/4 + \varepsilon )}$ at every positive matrix size, for one C independent of n. Palomar registered the field development on 8 October and the ring development on 11 October 2026.

OpenAI reports a superquadratic sensitivity separation

There are total Boolean functions with unbounded block sensitivity divided by sensitivity squared; in particular, a fixed exponent $\alpha >2$ holds along a sequence with unbounded block sensitivity.

The maximum number of mutually unbiased bases in dimension six

OpenAI

OpenAI reports that the maximum number of mutually unbiased orthonormal bases in complex dimension six is three, using an exhaustive computer-assisted exclusion of four bases under specified arithmetic and compiler conditions.

OpenAI reports a uniform generalized star-height bound

Every regular language over a finite alphabet has a generalized regular expression over that same alphabet whose Kleene-star nesting height is at most thirteen, with complement taken relative to the same free monoid.

OpenAI reports a parity-lift reduction for Weisfeiler–Leman equivalence

For each $k\ge 4$, an explicit construction maps a finite compatible-choice system to two equal-size simple uncolored graphs that are k-dimensional Weisfeiler–Leman equivalent exactly when the system has no successful choice; a successful choice is detected after two joint-refinement rounds or one separate-refinement round.

OpenAI reports exponential semidefinite lift complexity for perfect matching

Every exact affine semidefinite lift of the perfect-matching polytope of the complete graph on n vertices has matrix size at least $2^{c n}$ for some absolute $c>0$ and all sufficiently large even n.

OpenAI reports a uniform quasipolynomial-time trace-reconstruction decoder

For every binary string of known length n and known rational deletion retention probability p, one randomized algorithm reconstructs the string with probability at least 2/3 using an explicit sample budget and bit time polynomial in that budget and the binary input length; for each fixed p, both are quasipolynomial in n.

OpenAI reports one matrix hitting point in every positive characteristic

Given a prime p in binary and positive n,s in unary, one deterministic polynomial-bit-time machine outputs a tuple of matrices over $F_{p}$ of dimension $O(n^{3}s^{6})$ that detects every nonzero division-free noncommutative formula of size at most s in n variables over every field of characteristic p.

OpenAI reports a uniform influence bound for hypergraph properties

For every fixed $r\ge 3$, every vertex-relabeling-invariant Boolean property of simple r-uniform hypergraphs on n vertices satisfies $\operatorname{Var}_p(f)\le\frac{C_r I_p(f)}{(\log n)^{r/(r-1)}}$ for all $0<p<1$, without requiring monotonicity.

OpenAI reports arbitrary-constant NP-hardness for Uniform Sparsest Cut

For every fixed $C>1$, approximating Uniform Sparsest Cut within factor C is NP-hard on graphs with nonnegative rational capacities and unit demand between every pair of distinct vertices.

OpenAI reports an FPRAS for common integer polymatroid bases

With exact rank-value oracles, the number of common integer bases of two equal-rank polymatroids can be approximated by an FPRAS whose oracle calls and non-oracle bit work are polynomial on every run in ground-set size, binary input length, inverse relative error, and log inverse failure probability.

OpenAI reports polynomial unitary synthesis with a Boolean oracle

For every n, one quantum oracle circuit generated in polynomial time from n using H, T, T† and CNOT approximates the channel of every n-qubit unitary to full diamond-norm error at most 1/2 after a suitable Boolean oracle is chosen; circuit size, qubits, queries and query length are polynomial in n.

OpenAI reports real-sentence decision in the counting hierarchy

The truth of existential–universal sentences over the reals is decidable in one fixed level of the counting hierarchy, even when their integer polynomials are specified by arithmetic circuits; in particular, the existential theory of the reals lies in the counting hierarchy.

OpenAI reports a nearly quartic quantum query separation

There are total Boolean functions whose bounded-error randomized query complexity cannot obey any universal bound of the form $O((1+Q(f))^{\alpha })$ with $\alpha <4$, where Q is bounded-error quantum query complexity.

OpenAI reports deterministic Ramanujan graphs at prescribed large sizes

For every fixed $d\ge 3$ and every sufficiently large even n, a deterministic algorithm outputs in polynomial bit time a simple connected nonbipartite d-regular n-vertex graph whose nonconstant adjacency eigenvalues lie strictly between ±$2\sqrt{(d-1)}$.

OpenAI reports a quasilinear PCP theorem for PPAD

There are fixed positive rational $\varepsilon$ and $\delta$ and a deterministic reduction mapping an $\operatorname{End}-of$-Line instance of binary length N to a generalized circuit of length $N(\log N)^{O(1)}$. A solution to the original instance can be recovered in polynomial time from any polynomial-length rational assignment $\varepsilon$-satisfying all but a $\delta$ fraction of gates.

OpenAI reports a memory–sample lower bound for noiseless Gaussian regression

For every fixed $A>0$ and sufficiently large dimension d, a one-pass learner retaining at most $\operatorname{Ad}^{2}$ bits between independent exact Gaussian linear measurements needs at least $c_{A}$ d $\log (1/\varepsilon )$ measurements to estimate a uniformly random unit vector to angular error $\varepsilon \le 1/10$ with success probability at least 2/3.

OpenAI reports exact-budget recovery for metric k-median

On positive integral metrics of polynomially bounded diameter, a supplied anchor with distinct accurate proxies for all but logarithmically many comparison clusters and sufficiently small total proxy error supports a polynomial-time k-median recovery algorithm opening at most k facilities and attaining a $(1+2/e+\varepsilon )$ factor against those comparison centers with any requested confidence.

OpenAI reports exact quantum factoring with fixed finite gates

A polynomial-time uniform family of quantum circuits over one fixed finite bounded-arity gate set outputs the complete prime factorization of every integer $N\ge 2$ with probability exactly one, using polynomially many gates and qubits in the input bit length.

OpenAI reports threshold repetition for entangled games

For every finite two-player game with finite-dimensional entangled value $v<1$ and arbitrary correlated questions, the maximum probability of winning at least a fraction $v+\delta$ of k repetitions decays at least as exp($-\kappa \delta ^{13}k$/($1+\log$(|A|$|B|$))) for one universal $\kappa >0$ and $0<\delta <1-v$.

OpenAI reports QMA-hardness of continuum Coulomb energy

Approximating the electronic Coulomb spectral infimum in three-dimensional continuum space is QMA-hard when positive integer nuclear charges use binary encoding, nuclei have distinct rational positions and electron count is unary; a deterministic polynomial-time reduction produces a promise gap of at least one.

OpenAI reports weak-to-strong normalization for pure type systems

For any pure type system, if every legal expression in every valid context has a terminating $\beta$-reduction sequence, then every $\beta$-reduction sequence from every such expression terminates, including reductions inside type annotations.

OpenAI reports a P-time query outside choiceless counting

An explicit isomorphism-invariant query on all finite structures in one fixed vocabulary of eight relations is decidable in deterministic polynomial time but is not definable in choiceless polynomial time with counting.

OpenAI reports unbounded violations of the square-root degree bound

For every $C>0$, some nonconstant Boolean function on a finite sign cube has the $\sum of$ its linear Fourier coefficients greater than $C\sqrt{deg}(f)$, where degree is that of its real multilinear representation.

OpenAI reports a two-fifths-power space simulation for one-tape machines

A fixed deterministic machine with one writable tape can be simulated through a supplied time cap $T\ge 2$ in O($T^{(2/5)}$ polylog($T+2$)) work-space bits while preserving its finite-control and halting outcome.

OpenAI reports a depth-five lower bound for iterated matrix multiplication

Over every characteristic-zero field, for all sufficiently large n every syntactically homogeneous depth-five $\Sigma \Pi \Sigma \Pi \Sigma$ circuit computing the (1,1) entry of n independent $n\times n$ matrix products has at least $n^{\sqrt n/400}$ gates.

OpenAI reports exponential state cost for $two-way$ NFA complementation

For every $n\ge 4$, an explicit n-state $two-way$ nondeterministic finite automaton has a complement requiring at least $\frac12\cdot2^{\lfloor(n-4)/127\rfloor}-1$ states in any $two-way$ nondeterministic finite automaton.

OpenAI reports the asymptotic average-sensitivity bound for polynomial thresholds

Every degree-at-most-d real polynomial threshold function on the uniform n-dimensional Boolean cube has average sensitivity at most $8d\sqrt{n}$ for $1\le d\le n$.

OpenAI reports exact uniform sampling of contingency tables with arbitrary margins

For any nonnegative row and column margins with equal totals, an exact uniform sampler for integer contingency tables terminates almost surely and has expected bit complexity polynomial in both dimensions and the binary input length.

OpenAI reports a $QAC^{0}$ parity lower bound

For every fixed depth, polynomial qubit bound and $\varepsilon >0$, sufficiently large measured-output quantum circuits using arbitrary one-qubit and unbounded-arity Toffoli gates have some input on which parity succeeds with probability below $1/2+\varepsilon$.

OpenAI reports a proof of the Boone–Higman conjecture

A finitely generated group has decidable word problem if and only if it embeds in a finitely presented simple group.

OpenAI reports single-fold Diophantine representations

Every recursively enumerable subset of natural-number n-tuples, for $n\ge 1$, has an integer-polynomial Diophantine representation with exactly one complete natural-number auxiliary tuple for each member and none for nonmembers.

OpenAI reports sharp binary-information contraction on the discrete cube

For a binary channel on a uniform discrete cube under independent symmetric noise, a noisy coordinate maximizes retained information at fixed initial information; for Boolean functions this gives I($f(X)$;Y) $\le 1 - h_{2}(\varepsilon )$ at crossover probability $0\le \varepsilon \le 1/2$.

OpenAI reports a depth-three circuit lower bound beyond every square-root constant

One fixed polynomial-time Boolean language has exact depth-three OR–AND–OR circuit size greater than $2^{(A\sqrt{n})}$ for every fixed $A>0$ at all sufficiently large input lengths n.

OpenAI reports a one-sample matroid prophet inequality against full-seed ordering

For every finite matroid, one independent sample per element supports an online rule with expected reward at least $2^{-310}$ times the expected offline optimum, even when the arrival-order adversary sees all samples, online values, and the rule’s seed.

OpenAI reports polynomial mixing of graph switches for every degree sequence

For every graphical degree sequence on $n\ge 4$ vertices, the lazy simple-undirected switch chain that proposes switches uniformly on four vertices has total-variation mixing time at distance 1/4 at most $2n^{8}$.

OpenAI reports polynomial-time optimal three-machine unit-job scheduling

A deterministic polynomial-time algorithm finds a minimum-makespan schedule for unit-length jobs with arbitrary acyclic precedence constraints on three identical parallel machines.

OpenAI reports an FPRAS for counting perfect matchings in general graphs

A randomized algorithm approximates the number of perfect matchings in every finite simple undirected graph to relative error $\varepsilon$ with failure probability at most $\delta$ in worst-case bit time polynomial in the input length, $\varepsilon ^{-1}$, and $\log \delta ^{-1}$; it returns zero with certainty when there is no perfect matching.

OpenAI reports a cubic permanent–determinant lower bound

The complex border determinantal complexity of the $m\times m$ permanent is $\Omega (m^{3})$, allowing affine-linear determinant representations and coefficientwise limits.

OpenAI reports hardness of large independent sets in three-colorable graphs

For every fixed $0<\delta <1/3$, it is NP-hard to distinguish three-colorable finite simple graphs from graphs whose largest independent set has fewer than $\delta$ times the vertices.

OpenAI reports perfect completeness for $2-to-1$ games

For every fixed rational $0<\delta <1$, it is NP-hard to distinguish satisfiable $2-to-1$ games from unweighted games of value at most $\delta$, with an alphabet depending only on $\delta$.

An explicit power saving for the exact discrete Fourier transform

OpenAI

The manuscript reports one deterministic algorithm computing the exact complex discrete Fourier transform at every length n in $O\left(n(\log n)^{1-10^{-13}}\right)$ operations, including scalar preparation, scheduling and indexing, in its specified arithmetic model.

Hilbert’s tenth problem over the rational numbers

OpenAI

OpenAI reports that no algorithm can decide whether an integer-coefficient polynomial has a rational solution when the number of variables is part of the input.

The Unique Games Theorem

OpenAI

OpenAI reports a deterministic polynomial-time reduction from 3SAT to fixed-alphabet Unique Games with completeness at least $1-\varepsilon$ and soundness at most $\delta$ for each fixed $\varepsilon$,$\delta$ in (0,1/2).

Exact derandomization of logarithmic space: $L = RL = BPL$

OpenAI

OpenAI reports a uniform deterministic logarithmic-space simulation of polynomial-time randomized logarithmic-space decision procedures with bounded error, yielding $L=RL=BPL$.

Squared-logarithmic randomized k-server on arbitrary metrics

OpenAI

OpenAI reports randomized k-server competitive ratio $O(\log ^{2}(k+1))$ on every metric against oblivious requests, matching the stated worst-case lower-bound order; distinct initial server positions need no additive term.

Deterministic Polynomial Factorization over Prime Fields

OpenAI

OpenAI reports uniform deterministic complete factorization of a densely represented polynomial over a binary-specified prime field in bit complexity polynomial in (degree+1) $\log p$, including irreducible factors and multiplicities.

Rigidity of the Turing degrees

OpenAI

OpenAI reports that every order automorphism of the full Turing-degree partial order is the identity in ZFC, without a definability or regularity restriction on the automorphism.

The Partition Principle does not imply Choice

OpenAI

OpenAI reports that consistency of ZF implies consistency of ZF plus the Partition Principle and Choice for ordinal-indexed families but without the full Axiom of Choice.

Codex reports equal-capacity greedy-matching dominance

In Arnosti’s random bipartite matching model with independent uniform job neighbourhoods of prescribed sizes and a common positive integer bin capacity, RANDOM-VERTEX stochastically dominates RANKING in the number of accepted jobs.

Turn-Based Stochastic Mean-Payoff Games in Deterministic Quasipolynomial Time

OpenAI

The manuscript reports a deterministic quasipolynomial algorithm for the nonnegative-value vertices of finite turn-based stochastic mean-payoff games.

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

Josh Alman, Virginia Vassilevska Williams

Claude’s original sparse-output thin-matrix multiplication algorithm, as presented in Section 2 and related to the certified $3SUM/APSP$ theorems. Human-optimized numerical parameters, new reductions, data structures and Hinted OMv extensions retain human credit.

Subset Sum in Time $O(2^{0.49n})$

OpenAI

The manuscript reports a randomized classical Subset Sum algorithm in $O(2^{(0.49n)})$ time for polynomial-bit inputs.

An Upper Bound of 9/4 for the Matrix Multiplication Exponent

OpenAI

For every $\varepsilon >0$, the OpenAI construction multiplies $n\times n$ complex matrices with $O\varepsilon (n^{9/4+\varepsilon })$ division-free arithmetic operations; consequently $\omega (C)\le 9/4$.

An Upper Bound of 9/4 for the Matrix Multiplication Exponent

OpenAI

The manuscript reports that the complex matrix-multiplication exponent is at most 9/4.

Codex reports a sharp two-size Gasoline rounding bound

For positive-integer two-size Gasoline instances with deliveries in {1,K}, the position-first iterative-rounding algorithm under the doubly stochastic assignment-LP interpretation has capacity at most $OPT+K-2$. For $K\ge 3$, the original-index tie rule has matching instances with $OPT=K$ and returned capacity $2K-2$, giving worst-case ratio $2-2/K$.

AI-assisted six-task pinwheel scheduling counterexample

The artifact reports (3,4,5,20,22,36) schedulable but (3,4,5,20,22,32) unschedulable, refuting the proposed six-task kernel cap.

Variable-dimension Weisfeiler–Leman equivalence on general and subcubic graphs

OpenAI

For joint-update k-dimensional Weisfeiler–Leman equivalence, with $k\ge 2$ binary encoded as part of the input and graphs given by explicit adjacency matrices, the test is EXPTIME-complete. The hardness also holds for connected equal-order simple uncolored graphs of maximum degree three.

Generalized Star Height at Most Three

OpenAI

Every regular language over a finite alphabet has a generalized regular expression over that same alphabet with at most three nested Kleene stars, allowing union, concatenation and complement.

An exponential $two-way$ deterministic state lower bound for $one-way$ liveness