Perplexity
Perplexity develops AI tools for search, browsing, research, content creation, organization, and workflow automation, including perplexity.ai, Comet, and Computer.
Critical XY Center Magnetization Decays as n⁻¹⁄⁸(log n)¹⁄¹⁶
A paper on the critical planar XY model gives a conditional asymptotic for how strongly spins at the center of a square remain aligned with spins fixed along its boundary: the expected alignment decays as \(C n^{-1/8}(\log n)^{1/16}\). The authors argue that the logarithmic correction, which fixed-ratio scaling alone cannot determine, follows from comparing scales in a dual height representation. The result relies on inputs from three companion manuscripts; it does not establish nonzero magnetization in infinite volume.
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.
Every Graphical Degree Sequence Has a Polynomial-Time Switch-Chain Mixing Bound
An OpenAI preprint proves that a switch chain for simple undirected graphs mixes in polynomial time for every graphical degree sequence, with a worst-case bound of \(2n^8\) steps to reach total variation distance \(1/4\) when \(n\geq4\). The result applies from any starting realization and uses a specified transition rule that does not choose uniformly among valid switches. The authors say it settles the simple-graph formulation of the Kannan–Tetali–Vempala conjecture.
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 Continuous Collar of Caustics Forces a Smooth Billiard Table to Be Elliptical
An OpenAI manuscript proves a rigidity theorem for smooth, strictly convex billiard tables: if a continuous family of caustics fills a collar just inside the boundary, the table must be an ellipse, including the circular case. The authors stress that the hypothesis requires every intermediate caustic in the collar; a handful of caustics or closed trajectories is not enough. Their proof turns periodic billiard orbits into constraints on the boundary, then uses analytic continuation and growth estimates to establish the result.
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.
Triple Orbit Averages Converge Almost Everywhere to the Product of Their Means
An OpenAI preprint claims that for an invertible, measure-preserving mixing transformation, the products of three bounded functions sampled along one orbit at times \(n\), \(2n\) and \(3n\) converge almost everywhere when averaged over all lengths \(N\). The limit, the manuscript says, is the product of the functions’ integrals. Its proof separates the task of establishing almost-everywhere convergence from identifying the limit, using a scale-based oscillation estimate for the first and mixing for the second.
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\).
Every WL Equivalence Decider Faces a Dimension-Scaled Time Lower Bound
An OpenAI preprint claims an unconditional worst-case time lower bound for deciding Weisfeiler–Leman equivalence: for every sufficiently large fixed dimension \(k\), every correct deterministic decider in the stated sequential models must take at least \(n^{ck}\) time on some inputs of every sufficiently large graph order \(n\), for an absolute constant \(c>0\). The authors derive the bound through a reduction from a language whose time gap is established by diagonalization, rather than by assuming another problem is hard. The claim excludes randomized algorithms, nonuniform advice and unit-cost unbounded integers.
Bernoulli Convolution Singularity Has an Infinite Arithmetic Classification
An OpenAI preprint gives an arithmetic classification of when Bernoulli convolutions are singular above one half: the parameter must be approached at every scale by algebraic targets whose polynomial coefficients satisfy a demanding crowding condition. The criterion is exact but infinite, not a finite procedure for deciding the type of an arbitrary parameter. The manuscript also proves singularity at reciprocals of quartic Salem numbers despite Fourier decay, and presents a degree-31 non-Pisot example.
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.
A C¹ Map Has Zero Entropy Despite Doubling Second Homology
An OpenAI preprint constructs a noninvertible C¹ map of a compact manifold with zero topological entropy but an eigenvalue of 2 in its action on second homology, contradicting the conjectured lower bound linking entropy to homological growth. The authors’ counterexample is specific: it applies in dimension at least five and does not settle the question for diffeomorphisms. Its construction uses delayed signals stored in finitely many registers to control orbit behavior while preserving the homological doubling.
One Irrational Triangle Angle Makes the Full Billiard Flow Ergodic
An OpenAI preprint claims that the full position-and-direction flow of a billiard is ergodic in every nondegenerate triangle with at least one angle that is an irrational multiple of π. The authors unfold the reflected paths onto a flat surface with cone points, then use an analytic argument to control the angular Fourier modes of any invariant set. Irrationality forces every nonzero mode to vanish, leaving only invariant sets of probability zero or one.
A Worst-Case Subset Sum Algorithm Uses 2^(n/5) Space
An OpenAI preprint presents a randomized algorithm for worst-case subset sum that uses less memory without improving the familiar half-exponential running time. For inputs with integer bit lengths bounded by any fixed polynomial in the number of positions, it runs in polynomial time times 2^(n/2) and uses O_c(2^(n/5)) writable words, with those resource caps holding on every run. The paper’s central idea is to generate search information without retaining it all.