Papers

In this paper, we establish large deviations of invariant measures for fractional stochastic reaction-diffusion equations with polynomial reaction term driven by unbounded multiplicative noise on R^n. Under a dissipativity condition, we first prove the Freidlin-Wentzell large deviation principle of solution trajectories uniformly over all initial data in L^2(R^n). The key ingredient is a positive-time L^\infty-estimate for differences of controlled solutions which is independent of all initial data and hence yields uniform convergence of controlled stochastic solutions over the entire tphase space. Then using the uniform trajectory estimates, contraction and a second-moment estimate, we further prove the large deviations of invariant measures of the equation with a good quasipotential without introducing weighted spaces or establishing exponential tightness. The non-compactness of Sobolev embeddings in R^n is circumvented by uniform spatial tail-ends estimates. This is the first result on large deviations of invariant measures of the equation with multiplicative noise on unbounded domains.

We study the optimal score $T_{n,m}$ in a complete feedback card guessing game. The deck has $n$ types and $m$ cards of each type. Its predictable compensator $S_{n,m}$ is the sum of the conditional success probabilities. We prove that Var$(S_{n,m})\leq C((\log\log n)^2+m/\log n)$, uniformly in $m$ for large $n$. This bound yields a central limit theorem for every sequence $m=m_n\geq1$ as $n\to\infty$. The score variance is asymptotic to its mean. We also give uniform Kolmogorov bounds using the conditional Bernoulli moments. For $m,n\to\infty$, the excess mean is asymptotic to $(\log n)\log\min\{m,\log n\}+(\pi/\sqrt2)\sqrt{m\log n}$. The two contributions balance at $m\asymp(\log n)(\log\log n)^2$. The variance proof uses reversed occupancy hitting times. Discrete hypergeometric tail estimates control their fluctuations in the large-deviation, Gaussian, and saturation regimes. For fixed $n$, we also show that the compensator has a Brownian-bridge functional limit as $m\to\infty$.

We investigate a newsvendor problem where a decision-maker observes a $z$-dimensional vector of covariates, and wants to learn how much stock to order given a sample of size $n$ of censored demand data to minimize costs. Demand is censored when insufficient stock is available to meet it, and past stocking quantities are known. We propose a new model-agnostic loss function approach to estimate optimal order quantities using observational data, and characterize the optimal newsvendor policy as the policy that minimizes our proposed loss function. Our method requires only a single estimation step, can be scaled to datasets with hundreds of thousands of data points, and does not suffer from the same instabilities as inverse censoring probability weighting methods. We describe how this loss function can be implemented in linear empirical risk minimization, kernel weights optimization and deep neural network algorithms, and provide excess risk generalization bounds for their out-of-sample performance. Moreover, we show through numerical experiments that our method quickly converges to the optimal policy on synthetic data, and leads to improved performance on real world retail data.

Motivated by the opinion and social dynamics literature, we rigorously study dynamically co-evolving latent space network models, where agent opinions evolve based on a latent state space model influenced by and influencing an underlying dynamically evolving graph determining their interactions. In contrast to earlier work, see [18], agents are allowed to be heterogeneous, i.e., of different types, and their dynamic evolution can capture behaviors like attraction and repulsion between and within groups. In addition, the model encodes bidirectional feedback between the latent process and the underlying interaction network, persistence effects are included, and the interactions are localized, i.e., individual agents do not have global information. We produce weak and empirical limit theorems that encode the asymptotic joint distribution of agent opinion trajectories and their interaction network. In doing so, we describe and exploit the complex dependence structure of the model.

We study the asymptotic response time tail in the M/G/n queue with heavy-tailed (regularly varying) job sizes. For this setting, strongly tail optimal policies are known only at lower load, where n-1 servers suffice for stability. At higher load, the tail optimal scheduling has been open. This paper presents DynaSPLIT, the first strongly tail optimal policy at high load. Together with prior work, this result shows that strong tail optimality is achievable across the entire stability region of the M/G/n with heavy-tailed job sizes.

We develop a Sobolev theory for the kinetic Fokker-Planck equation subject to a singular Morrey-form $L^\infty+M^q_K$ force field which can produce local blow-ups due to strong attraction to a submanifold. Our approach is based on the fractional representation for the Duhamel series of the equation and on establishing kinetic Adams-type estimates. Accordingly, we construct weak solutions of Brownian-driven kinetic SDEs in a critical Morrey set-up, obtain kinetic Krylov-type estimates and a strongly continuous Feller propagator, and establish uniqueness criteria for a large class of weak solutions.

This work studies certified reach-avoid control of stochastic hybrid systems in which a stochastic differential equation governs continuous flow and a controlled stochastic kernel governs guard-triggered resets. The input appears only in the reset kernel, where it determines the post-jump distribution. Certificates for such systems have so far assumed spontaneous or controller-chosen jump times, a finite horizon, or discrete-time dynamics; we certify, over the infinite horizon, that the target is reached before the unsafe set with at least a prescribed probability. First, we introduce reach-avoid contact certificates, whose flow and jump conditions are imposed only on a sublevel corridor, and prove that any such certificate with a compatible reset policy meets the specification; a pointwise safety filter extends this guarantee from verification to control by constraining arbitrary nominal controllers. Next, we prove that executions are non-Zeno and bound the expected settling time and reset count. We frame certificate search as a linear program over any twice-differentiable dictionary followed by independent verification. We illustrate our approach via comparisons where the certified region is a subset covering 93.6% of the ground truth and where our certificate-based safety filter reaches the goal while reducing collisions from 68 to zero across 200 episodes of a dribbling ball problem.

We study the rough differential equation $$ \frac{du_t}{dt}= F(u_t) \zeta_t, \ \ u(0) = u_0 \in \mathbb{R}^d, $$ where $F : \mathbb{R}^d \to L(\mathbb{R}^d, \mathbb{R}^d)$ is a sufficiently regular vector field, and the noise $\zeta$ is a distribution in $\mathscr{C}^{\alpha-1}(\mathbb{R})$ for $\alpha \in (\frac{1}{4}, \frac{1}{3})$. We construct solutions to this equation at lower regularity than previous work of Gubinelli-Imkeller-Perkowski and Prömel-Trabs using ideas from the high-order paracontrolled viewpoint of Bailleul-Bernicot. The key tool in our work is the development of a harmonic-analytic framework for proving a set of iterated commutator estimates which are necessary for the solution theory. We also show the procedure of enhancement when the noise $\zeta = dZ$, where $Z$ is a realization of fractional Brownian motion with Hurst parameter $H \in (\frac{1}{4}, \frac{1}{3})$.

We study the behavior of saddle connection directions on translation surfaces from the point process viewpoint. We define a direction point process for saddle connections of length at most $R>0$ on every translation surface. Given a general ergodic $\mathrm{SL}(2,\mathbb R)$-invariant measure $\mu$ on a stratum of translation surfaces, we also define a slope point process associated with $\mu$. By utilizing the dynamics and geometry of strata, we show that for almost every translation surface, the direction point processes, rescaled by $R^2$, converge in distribution to the slope point process as $R\to\infty$. Using Palm distribution theory, we prove the existence of limiting joint gap distributions and obtain new regularity results for gap distributions associated with the general $\mu$. Finally, we study how these point processes and joint gap distributions behave as the genus $g$ tends to infinity. In the principal stratum, we show that the slope point processes, rescaled by $g^2$, converge in distribution to a Poisson point process. By passing to the corresponding Palm distributions, we show that the rescaled slope gaps converge jointly to independent exponential random variables, which is in stark contrast to the known non-exponential gap distributions in a fixed genus.

We show that finite-order exponential mixing does not imply the central limit theorem for smooth diffeomorphisms. For every integer $R\geq2$, we construct a $\mathcal{C}^{\infty}$ diffeomorphism $T:M\to M$ of a compact smooth manifold $M$ and a $T$-invariant probability measure $\mu$ such that $(T,\mu)$ is exponentially mixing of order $R$ for $\mathcal{C}^1(M)$ observables, but not of order $2R+2$. For some centred observable $f_0\in\mathcal{C}^{\infty}(M)$, no subsequence of the normalised sums $\frac{1}{\sqrt n}\sum_{i=0}^{n-1}f_0\circ T^i$ converges in distribution to a Gaussian law. In particular, exponential decay of two-point correlations implies neither exponential mixing of all orders nor the central limit theorem. We realise $(T,\mu)$ in two ways. In the first, $T$ is a fixed linear Anosov diffeomorphism of $\mathbb T^2$ and $\mu$ is singular with respect to Lebesgue measure. In the second, $M$ can be any compact smooth surface without boundary and $\mu$ is a physical measure whose statistical basin contains a nonempty open set. The main theorems have been formalised in Lean 4.

We investigate the regularity of Lyapunov exponents for products of random invertible matrices of arbitrary dimension $d\ge 2$. We prove that the top Lyapunov exponent is pointwise Hölder continuous with respect to the Wasserstein-Hausdorff distance in the space of probability measures with compact support, in the case where this exponent is simple and the equator has dimension equal to or less than one.

We consider the existence and uniqueness of positive, bounded stationary solutions of the Fisher-KPP equation with Dirichlet boundary conditions. We establish that stationary solutions are unique, and exist if and only if the generalised principal eigenvalue is strictly positive (supercriticality), in dimension at most $6$. This is sharp: we exhibit examples both of non-uniqueness and of existence at criticality in dimension $7$ or higher, including for the classical reaction $f(u)=u-u^2$. This proves a conjecture of Berestycki and Graham in the affirmative for dimension at most $6$, and in the negative for dimension at least $7$. We thereby show that branching Brownian motion cannot survive globally without surviving locally in dimension $6$ or lower, but can do so in dimension $7$ or higher, mirroring the classical transition of Brownian motion from recurrence to transience from dimension $2$ to $3$. We further show that relaxing the strong-KPP condition results in a more general sharp dimension threshold for the uniqueness/non-existence result. These results are valid without any regularity assumptions on the domain boundary. As a corollary, we show that solutions of the evolution reaction-diffusion equation are always convergent in the long run in dimension at most $6$, whilst we exhibit non-convergent solutions in dimension larger than $6$.

A class of models which brings to the fore the inner logic of the calculus of probability instead of assigning probabilities to sentences is introduced and investigated.

For the counts $(X_1,\dots,X_n)\sim\mathrm{Mult}(N;1/n,\dots,1/n)$ of $N$ observations in $n$ ordered bins we study the variance of the discrete total variation $d=\sum_{i=1}^{n-1}|X_{i+1}-X_i|$. An exact decomposition splits $\mathrm{Var}(d)$ into per-edge, adjacent-pair and disjoint-pair terms and yields, for fixed $n$ as $N\to\infty$, $\mathrm{Var}(d)/N=\alpha(n)-\beta(n)/N+\gamma(n)/N^2+o(N^{-2})$. For every $n\ge 2$, $N\alpha(n)$ is the classical normal-theory variance (Hoel, Kamat) of the sum of absolute successive differences of $n$ independent $N(0,N/n)$ variables; the correction $\beta(n)$ is obtained in closed form for $n\ge 3$ (the case $n=2$ is treated separately). Two disjoint edge differences $D_1=X_2-X_1$ and $D_3=X_4-X_3$ are exactly uncorrelated and asymptotically independent, yet $\mathrm{Cov}(|D_1|,|D_3|)=-1/(\pi n)+O(1/N)$: a correlation of relative order $1/N$, invisible in the Gaussian limit and absent under Poissonized sampling, whose constant is proportional to the exact joint fourth cumulant $\kappa_{2,2}(D_1,D_3)=-4N/n^2$ and is proved here on the lattice. The adjacent pair contributes the lattice-Edgeworth constant $a_*=-2\sqrt{3}/(9\pi)$, of which one quarter is a smooth Edgeworth term and three quarters a lattice-corner term; the disjoint skeleton $h(m)$ is closed through a Bessel generating function; and $\gamma(n)$ ($n\ge 5$) is expressed through a single triangular-lattice constant whose closed form we conjecture. Together with the mean of Part 1, the variance supplies the two moments used by moment-matched approximations to the null law of $d$. This is Part 2 of a series; the cyclic statistic $d^{c}$ will be treated in Part 5.

Ideal Poisson–Voronoi tessellations are random tessellations that arise as limits of Voronoi diagrams for Poisson point processes as their intensity tends to zero. For the Riemannian metric on a symmetric space of higher rank, Frączyk, Mellick, and Wilkens (arXiv:2307.01194) proved that the corresponding ideal Poisson–Voronoi tessellation is almost surely completely connected, with an unbounded side between any two cells. This contrasts sharply with the geometry of ideal Poisson–Voronoi tessellations in hyperbolic spaces studied by D'Achille, Curien, Enriquez, Lyons, and Ünel (arXiv:2303.16831). In this paper we introduce and study ideal Poisson–Voronoi tessellations for Finsler metrics on higher rank symmetric spaces. We show that ideal Poisson–Voronoi tessellations with respect to polyhedral Finsler metrics can exhibit either behavior seen in these previous works: generically they resemble the hyperbolic case, where almost surely all cells have bounded sides. We further introduce the ideal Selberg–Poisson–Voronoi tessellation of the space of positive definite symmetric matrices, which has particularly nice properties.

We study the asymptotic behavior of extreme events in multivariate stationary sequences, with particular emphasis on stochastic processes generated by dynamical systems. We develop a general framework for describing the dependence structure of extremes through two complementary objects: the tail process and the spectral measure. We first extend the enriched point-process convergence of the univariate theory to the multivariate setting, proving that the decorated point process of exceedances converges to a marked Poisson cluster process whose marks retain the componentwise and temporal structure of extreme clusters. We then construct a spectral measure for stationary sequences, which assigns weight to distinct extremal profiles and characterizes the asymptotic dependence between components, and establish a de Haan-Resnick type representation. We also relate the spectral measure to the tail process, showing that its normalized profile distribution is recovered from the angular component of the tail process. Finally, we recover the classical univariate and multivariate exceedance processes as special cases. We illustrate the theory through applications to dynamical systems, using examples in which different dynamical mechanisms give rise to distinct extremal clustering patterns and cross-dependence structures. These applications demonstrate the ability of the proposed framework to capture genuinely multivariate features of extreme events and to extract information about the underlying dynamics that is not accessible through classical exceedance processes.

We derive a Fredholm-Pfaffian formula for the one-time multi-point transition probabilities of half-space polynuclear growth with any nonnegative boundary nucleation rate and general deterministic upper semi-continuous initial profiles. We prove the formula by showing that it satisfies an integral Kolmogorov equation with a unique bounded solution. We also discuss the formal 1:2:3 scaling limit of the kernel and its relation to the half-space KPZ fixed point.

Let $X_N(t)$, $t\in[0,\pi]$, be a stationary Gaussian trigonometric polynomial, and let $\mathcal Z_N$ denote the number of zeros of the rescaled process $X_N(t/N)$ on $[0,N\pi]$. We establish the quantitative central limit theorem \[ d_{\mathrm W}\left( \frac{\mathcal Z_N-\mathbb E[\mathcal Z_N]} {\sqrt{\operatorname{Var}(\mathcal Z_N)}},Z\right) \le C\frac{(\log N)^2}{\sqrt N}, \] where $Z$ is standard Gaussian and $d_{\mathrm W}$ denotes the Wasserstein-1 distance. The proof combines Ornstein–Uhlenbeck regularization of the singular Kac representation with direct estimates of the covariance between the Malliavin–Stein factor and Stein test functions. A lattice lower bound of order $N^{-1/2}$ shows that the convergence rate is optimal up to logarithmic factors.

We introduce a determinantal linear process on the space of $1$-forms over a weighted graph endowed with a unitary local system, which we call the determinantal linear spanning forest (DLSF). This process is the analog of the uniform spanning tree in the presence of an arbitrary rank $n$ quenched gauge field in ${\rm U}(n)$ (or ${\rm O}(n)$, ${\rm SO}(n)$, ${\rm SU}(n)$, ${\rm Sp}(n)$), and generalizes the determinantal random cycle-rooted spanning forest which corresponds to the case of ${\rm U}(1)$ and ${\rm SU}(2)$. We describe the support of this process by means of a polymatroid which is described in terms of the circular and bicircular matroids. We also explain how the DLSF relates to the computation of currents in an electrical network in the presence of a gauge field. The partition function of the DLSF is shown to be the determinant of the twisted Laplacian, for which we also give a matrix-tree type theorem that computes its characteristic polynomial. We initiate the study of the twisted Laplacian determinant as a functional on the space of connections, and give a first order expansion of it in a neighborhood of the trivial connection, for which we provide a probabilistic interpretation. We extend the construction to infinite graphs, exhibiting the analogs of the classical wired and free distributions on spanning forests. We give a sufficient geometric condition on the local spectral gap for the existence of a Poincaré inequality as well as the uniqueness of the infinite volume measure, and the exponential decay of correlations. We show that on any recurrent graph, the wired and free DLSF coincide. We construct examples where they do not, for example, unlike in the classical case, on $\mathbb Z^d$ for $d\geq 3$.

We consider a random subgraph G_p(n,r,<s) of the complete distance graph G(n,r,<s) whose vertices are the r-element subsets of the set {1,...,n} and whose edges join pairs of subsets that intersect in fewer than s elements; each edge survives independently of the others with probability p. The stability of the Erdos-Ko-Rado theorem is the event that the independence number of the random subgraph equals that of the original graph, N = C_{n-s}^{r-s}. For fixed r and s, two-sided bounds for the critical probability, whose ratio depends on r and s, were obtained by P. A. Ogarok and A. M. Raigorodskii. In this paper we establish the order of the critical probability for growing r=r(n) and s=s(n): if min{C_r^s r^2, s r^3} = o(n), then the upper and lower bounds differ only by an absolute constant factor. The proof is elementary; only one of the two branches of the growth condition uses the complete nontrivial-intersection theorem of Ahlswede-Khachatrian.

An Orlicz ball is the set of points where the sum of a fixed even convex function of the coordinates does not exceed a given radius, here proportional to the dimension. For a broad class of such functions, including non-homogeneous ones, we find the exponential rate of the intrinsic volumes whose order is proportional to the dimension and express it by a two-parameter variational formula involving only one-dimensional integrals. As a function of the order-to-dimension ratio, this rate is concave and continuous on the closed unit interval, and the convergence is uniform in the order. This proves the exponential-profile conjecture of Kabluchko, Marynych, and Prochno for these bodies and recovers their result for $\ell_p$ balls with $p>1$. The proof relies on the theory of large deviations. An exact formula for the Laplace transform of the intrinsic volumes in the radius, extending theirs for $\ell_p$ balls, plays the role of a moment generating function, and a Laplace method gives its exponential rate. An exponential change of measure, analogous to that used in Cramér's theorem, then recovers the intrinsic volumes. The key step is a lower bound on the tilted density at its mean, obtained from log-concavity rather than a law of large numbers.

Can the Alexander-Orbach conjecture hold on hierarchical lattices? We construct Gromov-Hausdorff-Prokhorov scaling limits of critical percolation clusters on hierarchical lattices in the chemical metric and determine the typical spectral dimensions of the associated diffusions. These dimensions are dense in $(1,2)$; however, outside a narrow region in dimension space, we prove that the Alexander-Orbach conjecture fails on every hierarchical lattice under consideration.

The total variation profile $\mathrm{TV}_n$ of a random walk measures how far its distribution at time $n$ is from being invariant under the generators. Three lower bounds are given: an elementary bound $\mathrm{TV}_n \geq 1/\big(44\,L(n)\big)$ in terms of the speed $L(n)$; a bound by the entropy increment $H(P^{n+1}) - H(P^n)$, which is a reverse Pinsker inequality; and a bound in terms of the entropy and the isoperimetric profile. Deciding whether the entropy-increment bound always improves on the isoperimetric one is related to conjectures on the growth of the entropy and of groups. The motivation comes from the question of whether the distributions of a random walk can be transported back onto their translates at bounded cost.

The purpose of this note is twofold. First, we revisit the classical regularity theory of harmonic maps in the setting of maps defined on a lattice $\mathbb{Z}^d$ instead of $\mathbb{R}^d$ or some other manifold. The target space of our harmonic maps will be spheres $\mathbb{S}^{N-1}, N\geq 2$. A harmonic map $\sigma : \mathbb{Z}^d \to \mathbb{S}^{N-1}$ is a map which in any finite subgraph $\Lambda$ minimizes the internal Dirichlet energy $\frac 1 2 \sum_{i \sim j \in \Lambda} \|\sigma_i -\sigma_j\|^2$ given the boundary condition $\sigma_{|\partial \Lambda}$. One key difference between our setting and the continuum is that our main Hölder regularity statement in a large domain $\Lambda\subset \mathbb{Z}^{d=2}$ does not require any regularity assumption on the map $\sigma$ restricted to the boundary of the domain. For example, when $d=2$ and $N=3$, the Hölder regularity induced in the bulk of the domain holds uniformly in all boundary configurations $\sigma \in (\mathbb{S}^{2})^{\partial \Lambda}$ (this is in contrast with the continuum which requires extensions in suitable Sobolev spaces). The fact we obtain results uniformly in the boundary conditions allows us to extend our results for positive temperatures. Namely, as $T \searrow 0$, we obtain a local regularity theory for all infinite volume Spin $O(N)$ Gibbs measures, at least when $d=2$ and $N\geq 3$. We also discuss implications of our analysis in dimensions $d\geq 3$.

Polyakov predicted in 1975 ([Pol75) that the spin $O(3)$-model (or classical Heisenberg model) should have exponential decay of correlations at all positive temperatures on $\mathbb{Z}^2$. Our main result is as follows: if we replace the Euclidean scalar product \begin{align*} \langle \sigma_i , \sigma_j\rangle = \sigma_i^x \sigma_j^x + \sigma_i^y \sigma_j^y + \sigma_i^z \sigma_j^z \end{align*} by the $\lambda$-modified scalar product \begin{align*} \langle \sigma_i , \sigma_j\rangle_\lambda := \sigma_i^x \sigma_j^x + \sigma_i^y \sigma_j^y + \lambda \sigma_i^z \sigma_j^z \end{align*} we show that for all $\lambda\in(-1,1)$, the $\mathbb{S}^2$ valued spin system with Gibbs measure $\exp(\beta \sum_{i\sim j} \langle \sigma_i,\sigma_j\rangle_\lambda)$ has power-law decay of correlations if $\beta$ is chosen large enough. This is the first evidence that arbitrary small smooth modifications of the classical Heisenberg model produce a BKT phase in $2d$. It was proved in the 1970s and 80s that there exist arbitrary small smooth modifications of the classical Heisenberg model which produce instead an Ising phase. In these work, they considered the regime $\lambda>1$ while in this paper, we consider the regime $\lambda<1$ which cannot be analyzed via reflection positivity and chessboard estimate. The two main ingredients used in our proof are the stability of the BKT phase under percolation type disorder ([DG25]) and weak regularity type properties of the groundstates or $\mathbb{S}^2$-valued harmonic maps associated to our $\lambda$-energy functional. This analytic step is interesting on its own. Finally, the exponential and power-law decay regime should be separated by a curve $\lambda \mapsto \beta_c(\lambda)$. We prove a rigorous lower bound in the case of the $\lambda$-anisotropic hemisphere model $\mathbb{S}^2_+$ which matches with RG flow predictions.

We obtain very high genus asymptotics for double Hurwitz numbers when both the size $n$ and the genus $g$ go to infinity, under the constraint that $g$ grows much faster than $n$, more precisely that $\frac{2g}{n}-\ln n\to\infty$. Our proof relies on adapting arguments about the mixing time of the transposition random walk introduced by Diaconis and Shahshahani.

We study one-dimensional marginals of an isotropic, log-concave probability measure in $\mathbb{R}^n$. We show that the Kolmogorov distance between a typical marginal and the standard Gaussian distribution is at most $C/n$, for a universal constant $C > 0$. This bound is optimal in general, up to the value of the universal constant. It improves the Gaussian approximation bound of Bobkov, Chistyakov and Götze by a logarithmic factor in the log-concave setting.

We present a statically and dynamically arbitrage-free European option market model with smooth interpolation between option prices, based on the SANOS framework, and prove that its dynamics admit a unique strong solution. In spirit, it is a stochastic model for local volatility when the latter is used as a representation of a European option price surface, not as a pricing model. We illustrate the strength of our approach on S&P Index Option data from January 2022 to August 2025. We show that the model's initial state fits within bid/ask for more than 95% of relevant market option prices. We then train the model dynamics under $\mathbb{P}$ and $\mathbb{Q}$ and show that the model is indeed free of arbitrage while fitting the dynamics of the market well. We also propose a range of BHW-tests to test for absence of arbitrage.

In the tensor principal components analysis (tensor PCA) problem, we are asked to recover an unknown vector in $\{\pm1\}^N$ from a noisy observation of its $k$-th tensor power, for a fixed $k\ge3$. Tensor PCA exhibits a well-studied information-computation gap: global algorithms such as spectral methods and sum-of-squares work above an algorithmic threshold, below which we know matching lower bounds (against these and some other restricted models of computation). In contrast, local algorithms such as Markov chains were only known to succeed from a random initialization at a polynomially larger signal-to-noise ratio, and were believed to be inferior to global algorithms for tensor PCA. We show that Glauber dynamics, when supplemented with annealing and ergodic averaging, achieves polynomial-time strong recovery above the algorithmic threshold from a uniformly random initialization, demonstrating that local Markov chains can succeed all the way down to the algorithmic threshold from an uninformative cold start.

We study the recovery of the hidden vertex correspondence between two correlated dense random geometric graphs. Each graph is generated from $n$ latent unit vectors in $\mathbb R^d$; the vectors $u_i^A$ and $u_i^B$ of corresponding vertices satisfy $\langle u_i^A,u_i^B\rangle=\rho$, and the vertex labels of the second graph are permuted by an unknown permutation $\pi$. For every fixed correlation $\rho\in(0,1]$ and every edge density bounded away from zero and one, we give a randomized polynomial time algorithm that recovers $\pi$ exactly with probability tending to one whenever $d\ge(\log n)^L$, where $L$ depends only on the correlation and the density bounds. The algorithm assigns to each vertex a signature formed by counting decorated paths with a constant number of seeds. The number of such seeded templates grows exponentially with the path length, with an arbitrarily large constant base, so the resulting statistics amplify an arbitrarily small constant correlation. We control the dependencies created by the latent geometry in two ways: when $d$ is larger than $n/(\log n)^{L_0}$ for a suitable constant $L_0$, by comparing local moments with those of correlated Erdős–Rényi graphs; for smaller $d$, by spectral estimation of the latent geometry combined with a harmonic correction. We also provide low-degree evidence for a tradeoff between the correlation and the computational cost.