AI Research Methods
New technical methods, papers, architectures, training techniques, reasoning approaches, and research findings with applied significance.
A Deterministic Polynomial-Time Algorithm Factors Polynomials Over Prime Fields
An OpenAI preprint claims a deterministic algorithm for factoring polynomials over prime fields in time polynomial in the degree and the bit length of the prime, without randomness or an integer-factorization oracle. Its central step is to construct labels that distinguish roots the algorithm cannot see, then use a greatest common divisor to turn that distinction into a factor. The paper handles even-sized root sets by counting and odd-sized sets through divisor classes on curves; its unconditional complexity claim also relies on a zero-free theorem proved in a separate companion manuscript.
One-Tape Computations Can Be Simulated in Two-Fifths-Power Space
An OpenAI preprint argues that a fixed deterministic machine with one writable tape, running for at most \(T\) steps, can be simulated in roughly \(T^{2/5}\) space, up to polylogarithmic factors. The bound improves on the square-root exponent for this setting, but the simulator may use vastly more time and need only determine the machine’s state and whether it has halted—not reproduce its final tape. The proof gets the space reduction by checking and recomputing local portions of the run rather than storing its full history.
Weakly Reversible Networks Share Eventual Bounds Within Each Stoichiometric Class
The OpenAI preprint *Uniform Permanence in Weakly Reversible Mass-Action Systems* claims that, for a finite weakly reversible network with fixed positive rate constants, every positive trajectory in a given stoichiometric class eventually enters the same compact region and remains there. The shared bounds depend on the network, rates and class—not on the initial state—but the time to reach them can vary without a uniform limit. The result establishes eventual bounds on concentrations, not convergence to a common equilibrium.
Two Limit Cycles Are the Exact Maximum for a Quintic Liénard Class
An OpenAI manuscript proves that a planar Liénard system with restoring force \(x\) and a polynomial damping term of degree at most four can have no more than two isolated periodic orbits, even when degenerate cycles are counted. The result applies to systems whose defining polynomial \(F\) has degree at most five, not to all planar systems with quintic terms. The authors establish the upper bound by comparing orbit halves and counting zeros of a matching function, then construct a small perturbation with two isolated cycles to show the bound is sharp.
Exact Measurements Still Require Many Samples Under Tight Memory
An OpenAI preprint proves a sample lower bound for recovering a direction from exact Gaussian linear measurements when a streaming learner’s memory is limited. In the specified finite-state model, any learner achieving average angular error at most \(\varepsilon\) with probability at least two-thirds needs at least \(c d\log(1/\varepsilon)/(1+M/d^2)\) observations, for an absolute constant \(c\) and sufficiently large dimension. The paper develops three proof routes, using projection moments, positive-cap domination and Riesz estimates to control how signal mass can concentrate across memory states.
Every Regular Language Has Generalized Star Height At Most Four
An OpenAI preprint claims that every regular language over a finite alphabet can be expressed using union, concatenation, complement and repetition with generalized star height at most four. The bound is uniform: it does not depend on the size of an automaton recognizing the language, and it limits nesting of repetition rather than the length of the expression. The proof converts an automaton into a finite monoid and builds shallow expressions by controlling how monoid products are recognized across cuts in a word.
Existential–Universal Real Sentences Fall Within a Fixed Counting Level
An OpenAI preprint argues that sentences asking whether one real tuple makes a polynomial condition true for every other real tuple can be decided within a fixed level of the counting hierarchy. The result applies to polynomial conditions represented by arithmetic circuits and allows arbitrarily many variables in both quantified blocks; it does not specify a numerical level for this two-block problem or claim a practical algorithm. The proof turns the universal challenge into a question about whether polynomial fibers contain real zeros, then encodes the existence of a uniformly good choice through finite algebraic tests.
A Uniform Decoder Reconstructs Strings From Randomly Deleted Traces
An OpenAI preprint on trace reconstruction claims a uniform algorithm that recovers any binary string of known length from independent deletion traces, with quasipolynomial sample and computation bounds for each fixed retention probability. When the empirical moments are sufficiently accurate, the algorithm’s tests exclude a wrong prefix and allow the correct extension to pass with strict slack; the paper claims this yields recovery with probability at least two-thirds. The guarantee is asymptotic, not a claim of practical speed.
A Full Band of Grazing Billiard Trajectories Forces Elliptic Tables
The preprint *Continuous Phase Foliations Create Analytic Caustic Collars* argues that a complete band of invariant billiard states near grazing motion forces a smooth, strictly convex planar table to be an ellipse. Its proof turns the foliation into exact action identities, uses them to establish analytic caustics near the boundary, and then applies a companion theorem to obtain rigidity. The hypothesis requires leaves throughout the band; isolated invariant curves or families with gaps do not meet it.
Identifying a Graph by Weisfeiler–Leman Refinement Is EXPTIME-Complete
An OpenAI preprint argues that deciding whether Weisfeiler–Leman refinement uniquely identifies a graph is EXPTIME-complete. That is a stronger question than whether refinement can distinguish a graph from one particular rival: identification requires ruling out every non-isomorphic graph with the same fingerprint. The result remains EXPTIME-complete when the refinement dimension is written in unary, according to the paper, which Perplexity Computer adapted into an animated explainer.
Parity Lifts Make Weisfeiler–Leman Refinement Detect Compatible Choices
An OpenAI manuscript argues that parity lifts turn a finite compatibility problem into a test of Weisfeiler–Leman refinement: a compatible choice makes two constructed graphs distinguishable, while its absence leaves them equivalent for every dimension \(k \ge 4\). The construction also links refinement distinguishability to bounded-treewidth witnesses, and uses the reduction to derive a conditional lower bound on the cost of computing WL histograms under positive-rate ETH.
Triple Ergodic Averages Converge to a Product of Means
An OpenAI preprint claims that for any three distinct, nonzero integer slopes, averages of three bounded measurable functions along the same orbit of an invertible, probability-preserving mixing system converge almost everywhere to the product of their means. The result holds along every positive integer length, not only along a selected subsequence. Coefficient identities let the authors extend the argument beyond equally spaced slopes, while analytic estimates control oscillation and establish convergence.
Weak Reversibility Prevents Extinction and Runaway Growth in Mass-Action Networks
An OpenAI preprint proves that, for finite weakly reversible reaction networks with mass-action kinetics, every trajectory starting at positive concentrations remains bounded above and bounded away from zero for all future time. The authors use a concave function to construct a region that traps each trajectory. The bounds may depend on the initial concentrations; the result does not establish convergence to equilibrium or a common bound for an entire compatibility class.
Edit Distance Requires Exponential Distortion in L₁ Embeddings
An OpenAI preprint argues that edit distance on words of length at most \(D\) cannot be embedded into \(L₁\) with low distortion: the best possible distortion grows as \(\exp(\Theta(\sqrt{\log D\,\log\log D}))\). The authors establish the lower bound using circle-based constructions, including a result that already holds for binary words of one fixed length, and give a matching-scale upper bound using overlapping substring histograms. The bounds match asymptotically, not in their constants.
Binary Edit Distance Requires L1 Distortion of exp(Θ(√(log d · log log d)))
An OpenAI preprint proves that, for every sufficiently large length cap d, there is a finite family of binary words of length at most d whose pairwise edit distances require distortion of at least exp(c√(log d · log log d)) in any embedding into L1, for a positive absolute constant c. The lower bound applies to a constructed family, not to each pair of words or to the computational cost of measuring their edit distance.
Low-Dispersion Samples Can Make Randomness Unnecessary in Motion Planning
In Stanford’s 2019 lecture on sampling-based motion planning, Professor Marco Pavone argues that planners can search complex robot configuration spaces without explicitly constructing their full obstacle geometry. Instead, they test sampled configurations and connections for collisions, trading a difficult global representation for local checks. Pavone compares PRM’s reusable roadmap with RRT’s incremental search, explains how dynamics change feasible connections, and presents results showing that well-spread deterministic samples can provide asymptotic guarantees without randomness.
LLM Design Trades Model Capacity Against Compute Per Token
Large language model design is a question of how to spend computation, not simply how many parameters a model has. In Stanford’s CME295 lecture, adjunct professor Afshine Amidi uses training budgets, sparse expert routing and attention mechanisms to show how designers allocate work across a model and its tokens; decoding choices, in turn, shape how the model generates answers. The distinction is between a model’s total capacity and the computation it uses for each token.
The Triangular Lattice Minimizes Planar Coulomb Energy Beyond Periodic Patterns
An OpenAI preprint on planar Coulomb renormalized energy claims that the triangular lattice attains the minimum not only among periodic arrangements but across the full admissible class, including non-periodic fields. The manuscript establishes the lower bound by first treating a finite system on a torus, then transferring it to the plane; its proof combines a global comparison potential, Voronoi-sector geometry and computer-assisted inequalities. The claim is a bound on the energy, not a classification of every minimizing arrangement.
Every Sufficiently Large Degree Admits an Ultraflat Real Littlewood Polynomial
An OpenAI manuscript dated October 5, 2026, claims that for every sufficiently large length \(N\), one can choose \(+1\) and \(-1\) coefficients so that the resulting real Littlewood polynomial has modulus uniformly as close to \(\sqrt N\) as desired at every point on the unit circle. The paper’s argument first builds a nearly flat continuous wave, then uses its energy to show the wave’s Fourier coefficients are close on average to signs and a discrepancy lemma to round them with uniformly controlled error.
A Scale-Independent L³ Bound for the Dyadic Triangular Hilbert Form
An OpenAI preprint proves a scale-independent \(L^3\) bound for a dyadic triangular Hilbert form built from three functions sharing variables around a cycle. The authors show that the sum of the absolute local contributions is at most 40 times the product of the functions’ \(L^3\) norms, regardless of which finite set of scales is used. Their proof charges each contribution to a nonnegative increase in matrix energy, then telescopes those increases across scales.
A New Falconer Theorem Claims Positive-Measure Distances Above d/2
An OpenAI manuscript dated September 23, 2026, claims that any compact set in ℝᵈ with Hausdorff dimension greater than d/2 determines a set of distances with positive Lebesgue measure. The result addresses the unpinned Falconer distance conjecture in every integer dimension d ≥ 2, but does not cover the equality case or distances measured from a fixed point. The proof combines frequency estimates with a multiscale argument to obtain a distance measure with an integrable density.
Ellipsoids Minimize Projection-Body Volume Ratios in Dimensions Four and Higher
An OpenAI preprint claims a sharp solution to Petty’s projection-volume problem in every dimension \(n\ge4\): among convex bodies with fixed volume, ellipsoids—and only ellipsoids—minimize the volume of the body defined by their shadows. The manuscript reduces the global inequality to a bound on pairings of measures, with the hardest step controlling directional variation through higher spherical-harmonic components. Its geometric examples illustrate the result but do not establish the proof.
Fourier Extension Is Bounded for Every Exponent Above Three
An OpenAI manuscript proves a diagonal Fourier extension estimate for every finite \(p>3\) on compact, smooth surfaces in three dimensions with positive curvature: the wave’s \(L^p\) norm across space is bounded by the input’s \(L^p\) norm on the surface. The authors build the global bound by combining packet-propagation and Kakeya estimates, using a local density inequality to connect them. The endpoint \(p=3\) is not covered.
A Sharp Three-Dimensional Kakeya Bound Tracks Sparse Tube Density
An OpenAI manuscript claims a sharp three-dimensional Kakeya maximal estimate, allowing a δ⁻ε loss as tubes become thinner. Its central claim is density-sensitive: the bound must hold even when only a sparse subset of each tube is retained, with the resulting union estimate weakening cubically in the retained fraction. The manuscript’s proof argues that near-extremal tube families must recur in a constrained geometric pattern across scales, then uses projection and information estimates to rule out the configurations that would violate the bound.