AI Research Methods
New technical methods, papers, architectures, training techniques, reasoning approaches, and research findings with applied significance.
Infinite Clusters Precede Uniqueness on Expanding Graphs
An OpenAI preprint on percolation in nonamenable quasi-transitive graphs proves that the threshold for infinite clusters is strictly below the threshold for a unique infinite cluster. Its argument shows that the connection operator is bounded at the existence threshold and remains bounded at some parameter strictly above it, while uniqueness would force the operator to be unbounded. As a result, at every fixed parameter between the two thresholds, there are infinitely many infinite clusters.
Critical FK–Ising Maps Converge Jointly in Geometry, Spectrum, and Heat Flow
An OpenAI manuscript on critical FK–Ising planar maps claims that their geometry and random-walk spectrum converge together to those of a unit-area Liouville quantum gravity sphere with \(\gamma=\sqrt{3}\). With the walk sped up by the number of edges, the paper establishes joint convergence of the rescaled metric and area measure, each fixed-index diffusion eigenvalue, and the heat trace uniformly over time intervals bounded away from zero. The result rules out a mismatch in which the surfaces converge but hidden slow modes prevent the walks from having the corresponding continuum limit.
Critical FK–Ising Map Walks Converge to Liouville Brownian Motion
A manuscript on critical FK–Ising maps argues that convergence of the random surfaces is not enough to establish a limit for walks on them: the walk’s time scale and energy must also match the continuum diffusion. With the stated distance scaling and time acceleration by \(n\), it proves joint convergence of the measured maps and any fixed finite number of stationary-start walks to a unit-area quantum sphere and conditionally independent Liouville Brownian motions on that shared surface. The proof adds whole-path control to the geometric and energy results supplied by a companion paper.
Fortuin–Kasteleyn Maps Above Four Converge to the Brownian Continuum Random Tree
An OpenAI manuscript claims that, for each fixed \(q>4\), finite planar maps sampled under a Fortuin–Kasteleyn weight converge to the Brownian continuum random tree when distances are scaled by \(c(q)/\sqrt n\), for a positive, finite constant \(c(q)\). The maps retain their cycles, but their rescaled distances and degree-weighted mass converge to those of the tree.
Planar XY Correlations Acquire a Critical (log r)¹⁄⁸ Correction
An OpenAI preprint on the critical planar XY model claims that its spin correlation decays as \(r^{-1/4}(\log r)^{1/8}\), with a positive, finite amplitude. The result sharpens the familiar power-law prediction: the logarithmic factor captures a correction accumulated across scales, while the proof’s control of the remaining terms establishes that the rescaled correlation converges rather than drifting further.
Height Fluctuations Reach the Roughening Threshold in a Gaussian Free Field Limit
An OpenAI preprint proves Gaussian free field limits for two-dimensional lattice height and planar-spin models, but the results reach different temperature regimes. For heights, the limit extends to the roughening threshold, where the effective parameter \(a\) reaches \(8\pi\); for planar spins, the theorem applies at sufficiently low fixed temperature and does not establish a limit at the spin transition. The paper’s central result is thus a pair of Gaussian free field limits with unequal scope.
A Degree-Five K-Theory Class Vanishes Over the Fraction Field but Not the Ring
An OpenAI preprint gives a degree-5 counterexample to Gersten’s conjecture, constructing a nonzero class in the algebraic K-theory of a two-dimensional regular local ring that vanishes over its fraction field. The authors establish the two sides of the result separately: support on a divisor forces the class to disappear after passing to the fraction field, while an arithmetic and geometric detector shows it remains nonzero in the ring. The example is specific to a ramified mixed-characteristic setting; the paper does not determine the class’s order or whether the failure occurs in lower degrees.
A Quadratic Bound Guarantees Surjectivity of the Foulkes–Howe Map
An OpenAI preprint proves that the canonical Foulkes–Howe map from Symᵇ(Symᵃ V) to Symᵃ(Symᵇ V) is surjective over finite-dimensional complex vector spaces whenever a ≥ 2 and b ≥ a(a − 1). The bound is sufficient, not asserted to be sharp. The proof rules out any nonzero linear functional that vanishes on the map’s image, using a derivative argument whose injectivity depends on a strict degree inequality.
Two-Dimensional O(n) Spin Correlations Decay Exponentially for n ≥ 3
A preprint on two-dimensional classical \(O(n)\) models claims that, for \(n\ge3\), spin correlations decay exponentially at every fixed positive temperature. Its proof bounds correlations by the probability that two sites are joined in an auxiliary random-bond model, then uses rare crossings of large annuli to show that long connections are exponentially unlikely. The stated bound is uniform over finite square-lattice subgraphs and allowed nonnegative edge strengths, but not uniform as temperature approaches zero.
Multiple Ergodic Averages Converge Pointwise Under Mixing
An OpenAI preprint argues that mixing is enough to guarantee almost-everywhere convergence of multiple ergodic averages for any fixed finite number of clocks. For each fixed tuple of bounded functions, it claims the averages along a typical orbit converge to the product of the functions’ means—not just after averaging over the whole probability space. The proof extends a companion result for three clocks by turning a hypothetical failure of pointwise convergence into a correlation that higher-order mixing rules out.
Well-Conditioned Log-Concave Sampling Needs Fewer Than Any Power of Dimension
An OpenAI preprint argues that sampling from a well-conditioned, strongly log-concave distribution to fixed total-variation accuracy requires at most \(C_\epsilon d^\epsilon\) value-and-gradient queries for every \(\epsilon>0\). The bound holds in the worst case, but its constants and algorithm may depend on \(\epsilon\); it is not a runtime guarantee or a polylogarithmic upper bound. The paper also proves a logarithmic query lower bound, so the query count cannot be constant.
A Deterministic Exact DFT Improves the Logarithmic Exponent
An OpenAI preprint claims a deterministic algorithm for the exact discrete Fourier transform at every length, with running time \(O(n(\log n)^{1-10^{-13}})\), a slight asymptotic improvement over the familiar \(O(n\log n)\) bound. The result relies on a model that treats complex arithmetic as exact and unit-cost while charging for scalar preparation and integer indexing. It is not a faster floating-point implementation, and the paper does not estimate when the saving might matter in practice.
Five-Layer Circuits Need n^{√n/400} Gates for Iterated Matrix Multiplication
An OpenAI preprint argues that computing the top-left entry of a product of \(n\) balanced \(n\times n\) matrices with five alternating sum and product layers requires at least \(n^{\sqrt n/400}\) gates, for sufficiently large \(n\). The bound holds for syntactically homogeneous circuits over any field of characteristic zero, even when gates are shared and bottom-layer forms can use all variables. The manuscript also gives a construction of size at most \(n^{\sqrt n+4}\), placing the gate count on a square-root scale in the exponent.
A Quasilinear Reduction Makes END OF LINE Robust to Adversarial Gate Failures
The preprint claims a deterministic quasilinear-size reduction from END OF LINE to a generalized circuit: for fixed numerical and failure tolerances, any acceptable assignment to the circuit can be decoded into an endpoint of the original graph. The guarantee allows an arbitrary fixed fraction of gates to fail, rather than relying on errors being randomly distributed. The paper also proves acceptable assignments exist, but does not provide an efficient method for finding one.
Two-Way Determinism Requires Exponentially Many States for One-Way Liveness
An OpenAI preprint argues that allowing a deterministic finite automaton to reread its input in either direction cannot uniformly replace nondeterministic choice with only a polynomial increase in states. Its example is one-way liveness: a language recognized by a machine with \(h+3\) states, for which any equivalent deterministic two-way machine needs exponentially many states as \(h\) grows. The lower bound applies across alphabets that grow with \(h\); it does not establish an exponential bound for any one fixed alphabet.
Subquadratic Memory Requires More Samples for Higher Gaussian Precision
For the paper’s specified message-alphabet size, an OpenAI preprint bounds the information in \(t\) messages by a constant times \(dt\) in sufficiently large dimension, with the constant depending on the alphabet-size parameter. It uses that bound to show that a one-pass learner with memory \(o(d^2)\) needs at least order \(d\log(1/\varepsilon)\) samples to estimate every unit signal to angular error \(\varepsilon\), with success probability at least \(2/3\), for \(0<\varepsilon\leq 1/10\).
Boolean Functions Break Every Quadratic Bound on Block Sensitivity
An OpenAI preprint proves that no universal quadratic bound can relate block sensitivity to sensitivity for total Boolean functions: for every constant \(C\), some function has block sensitivity greater than \(C\) times its sensitivity squared. The construction uses nested tests to limit the effect of individual bit flips while multiplying the number of disjoint input changes that can alter the output. The authors also derive a fixed exponent greater than two through repeated composition.
Subquadratic Memory Requires More Samples for Exact Gaussian Direction Estimation
An OpenAI manuscript on Gaussian regression argues that exact, noiseless measurements do not eliminate the sample cost of learning when a learner has limited memory. For a learner that processes each sample once and retains fewer than order \(d^2\) bits, the paper proves that estimating a random direction in \(d\) dimensions to angular error \(\varepsilon\) requires at least order \(d\log(1/\varepsilon)\) samples. Its proof uses independent draws from the posterior distribution to track how much information the learner’s finite state retains.
Exact Fourier Cost Has Vanishing Normalized Growth on a Subsequence
An OpenAI manuscript proves that exact Fourier transforms can use asymptotically fewer than \(n\log_2 n\) gates along an unbounded sequence of lengths, in a nonuniform circuit model that allows arbitrary constants and charges for their preparation nothing. The authors’ argument starts from the existence of a finite saving for a tensor computation, amplifies it, then transfers it to Fourier transforms without extra coordinates. The result applies only to selected lengths and does not establish a practical or numerically stable alternative to the FFT.
Bounded Memory Forces Logarithmically More Samples for Precise Gaussian Regression
An OpenAI preprint on noiseless Gaussian regression argues that exact measurements do not eliminate the sample cost of high precision when an algorithm has bounded memory. For a uniformly random unit vector in dimension \(d\), any algorithm using at most \(A d^2\) bits needs at least on the order of \(d\log(1/\varepsilon)\) observations to estimate it within angular error \(\varepsilon\), with success probability at least two-thirds. The lower bound is average-case and applies for fixed \(A\); it contrasts with the fact that \(d\) retained equations determine the vector almost surely.
Exact Gaussian Labels Still Require d log(1/ε) Samples Under Subquadratic Memory
An OpenAI preprint proves that a streaming learner with memory \(M(d)=o(d^2)\) needs at least \(c\,d\log(1/\varepsilon)\) exact Gaussian observations to estimate a \(d\)-dimensional unit vector to angular error \(\varepsilon\), for \(0<\varepsilon\leq 1/10\), with success probability at least \(3/5\). The lower bound applies even when computation on each observation is unrestricted. To handle selection bias in observations that helped shape the learner’s memory, the proof keeps the joint law of the signal and memory fixed and controls how the comparison with fresh observations affects the information bound.
Two-Way Nondeterministic Complementation Requires Exponentially Many States
An OpenAI manuscript proves that complementing a nondeterministic finite-state machine can require exponentially more states, even when the complementing machine remains nondeterministic and can move its input head in both directions. The lower bound arises because finding one accepting path is easier than recognizing that no accepting path exists. It applies to finite alphabets that grow with the machine’s state count, not to a fixed alphabet.
Weisfeiler–Leman Equivalence Remains EXPTIME-Complete on Subcubic Graphs
An OpenAI manuscript claims that deciding whether two graphs are equivalent under joint \(k\)-dimensional Weisfeiler–Leman refinement is EXPTIME-complete when the dimension is part of the input. The result holds even for explicit, connected, uncolored graphs with maximum degree three; the manuscript’s reduction encodes an exponential-time computation in polynomial-size graph pairs. The accompanying explainer presents the proof’s main ideas, while noting that it does not reproduce the full formal proofs.
Subquadratic Memory Requires Dimension-Scaled Samples for Precise Gaussian Regression
An OpenAI preprint on noiseless Gaussian regression argues that exact measurements do not remove the sample cost imposed by limited memory. It proves that when a learner’s memory grows more slowly than the square of the dimension, achieving angular error at most ε with probability at least two-thirds requires at least \(d\log_2(1/\varepsilon)/65{,}536\) samples, for sufficiently large dimension and ε between zero and 0.1 radians. The bound is a necessary condition, not an algorithm, and the paper does not claim its constant is optimal.