Papers

We establish a polynomial sample complexity separation between symmetry-aware and symmetry-agnostic feature learning. We study growing-rank multi-index models with high-dimensional Gaussian covariates in $\mathbb{R}^d$ and $r=\Theta(d^\delta)$ teacher directions forming a cyclic symmetry orbit, where $0<\delta<1/2$. We compare three ways of exploiting this structure: architectural weight sharing, data augmentation over the full symmetry group, and learning without access to the symmetry. In particular, we analyze a symmetry-tied convolutional network, an untied network, and the same untied network trained with full-group data augmentation, using spherical online SGD with correlation loss. For a class of polynomial links with information exponent $p\ge3$, we prove matching sample complexity bounds up to logarithmic factors: the tied and augmented learners achieve weak directional recovery in $\widetilde{\Theta}(d^{p-1})$ samples, whereas the symmetry-agnostic learner requires $\widetilde{\Theta}(rd^{p-1})$. For the pure quadratic Hermite link, the same separation holds for weak recovery of the teacher subspace, with sample complexities $\widetilde{\Theta}(d)$ and $\widetilde{\Theta}(rd)$, respectively. Thus, full-group data augmentation matches the sample efficiency of architectural weight sharing, and both provide a polynomial advantage over training without symmetry. For $p\ge3$, the proof reveals a two-stage mechanism: fluctuations at initialization select one direction in the teacher orbit, after which localized growth amplifies its overlap to the weak recovery scale while competing overlaps remain near their initialization scale.

We study a random walk in $\mathbb{Z}^d$ in a dynamical random environment constituted of independent null recurrent birth-and-death chains, and establish a scaling limit result for the position of the walker in terms of a sublinear time change of Brownian motion, thus establishing subdiffusivity, in contrast to a diffusivity result established previously in an ergodic version of the model.

We give an introduction to the time-fractional stochastic heat equation driven by 1+d-parameter fractional time-space white noise, in the following two cases: (i) With additive fractional time-space white noise (ii) With multiplicative time-space Brownian noise The fractional time derivative is interpreted as the Caputo derivative of order $\alpha \in (0,2]$ and we assume that the Hurst coefficient $H=(H_0,H_1,H_2, ...,H_d)$ of the time-space fractional white noise is in $(\tfrac{1}{2},1)^{1+d}$. We find an explicit expression for the unique solution in the sense of distribution of the equation in the additive noise case (i). In the multiplicative case (ii) we derive the correct space–time convolution equation and its Wiener chaos expansion. For $1<\alpha\leq2$ a second initial condition is required. The endpoint $\alpha=2$ is treated separately and yields a stochastic wave equation with finite propagation speed. A solution $Y(t,x)$ is called mild if $E[Y^2(t,x)] < \infty$ for all $t,x$. In the multiplicative case the random-field condition is expressed by the square integrability of the forcing kernel. For the classical Laplacian and space–time white noise, the endpoint $\alpha=2$ admits a random-field solution only in space dimension $d=1$. This paper is partly a survey paper, explaining the concepts and methods behind the results. It is also partly a research paper, in the sense that some results are new, to the best of our knowledge.

We construct distinct high-dimensional mean-zero finite range lattice random walks having pairwise-equal return probabilities for all step counts. The same examples provide pairwise-distinct shapes of discretizations of the standard Laplacian with pairwise-equal density state functions. The main contribution is a reconstruction theorem: to a colored trivalent graph one associates a quantum Clebsch–Gordan polytope, and this association is a full functor, in particular from the polytope one can uniquely recover the original graph. These polytopes appear as moment polytopes of toric degenerations of character varieties (moduli spaces of rank-2 bundles on curves), yielding a combinatorial non-abelian Torelli theorem. In symplectic geometry, the reconstruction theorem implies that monotone Lagrangian tori on odd character varieties associated with these degenerations are pairwise non-Hamiltonian isotopic. These results, and some of the applications, arose from the study of mirror symmetry for moduli spaces of vector bundles, and of the related Laurent phenomenon for mutations of graph potentials.

We consider site percolation on general graphs and give a sufficient condition on the escape probability of a certain random walk with degree-dependent conductances, such that the number of minimal vertex cutsets of size $n$ separating a given vertex from infinity is bounded above exponentially in $n$. This result extends an analogous theorem of Easo, Severo and Tassion under slightly stronger assumptions. Moreover, we give an alternative sufficient condition in terms of the isoperimetric dimension or, more specifically, an isoperimetric-type inequality. Furthermore, our theorem is sufficient to extend the results of Panagiotis and Severo, and show that there exists a universal positive constant $\varepsilon_1$ such that site percolation on every infinite, connected, locally finite, vertex-transitive graph satisfies $p_c = 1$ or $p_c \leq 1-\varepsilon_1$.

The strong universality conjecture of Bobrowski and Skraba asserts that, under a prescribed data-dependent additive centering, the empirical laws of log-log transformed persistence ratios of random geometric complexes share a universal limit across sampling models, dimensions, filtrations, and homological degrees. They conjectured a left-skewed Gumbel limit and used it as a null law for testing topological significance. We show that, when the uncentered empirical laws and the centerings have deterministic limits, the conjecture forces a second-order quantity of each model's limiting law, determined by ratios close to one and unchanged by additive shifts, to agree across models and dimensions. To compute this quantity for degree-one Čech persistence, we bypass the global persistence pairing with a local proxy based on edges and their first incident triangles in the equivalent alpha filtration. In dimensions two and three, a Palm-Mecke calculation evaluates the proxy intensity exactly for stationary Poisson processes, and two-sided topological bounds show that it agrees with the true normalized persistence intensity through second order. After transfer to finite samples, the quantity equals $\pi^2/32$ and $4/\pi^2-1/4$ for the limiting laws of independent uniform samples from the unit square and the unit cube, respectively. The centered empirical laws converge weakly in probability to distinct deterministic limits, and their mean laws, the expectations of these random laws, also converge weakly to these limits. Hence the conjecture fails even for mean laws. Neither limiting law belongs to the left-skewed Gumbel location-scale family.

A program for fluctuating kinetic theory is proposed in this paper to study nonlinear Lévy-type fluctuation corrections to kinetic PDEs in a unified way. The Vlasov–Fokker–Planck (VFP), Landau, and Boltzmann equations can each be decomposed into a kinetic transport term and a generalized gradient structure generated by a nonlinear dual pair of dissipation potentials. Going beyond the linear Onsager structure and the classical fluctuation–dissipation relation, we propose a new nonlinear Lévy-type fluctuation–dissipation relation that identifies the thermal fluctuations associated with this generalized gradient structure. On a regular tilted class, the canonical action of the generalized gradient structure agrees with the Freidlin–Wentzell-type action predicted by the resulting SPDE. This consistency gives thermodynamic support for the new nonlinear fluctuation–dissipation relation and leads to a master fluctuating kinetic equation. We further establish a sufficient condition on the nonlinear dual dissipation potential under which its centered cumulant admits a Lévy–Khintchine representation, and show that the resulting Lévy current can be realized through Gaussian white noise and a compensated Poisson random measure. As an application of this framework, an \(\alpha\)-stable Lévy-type Dean-Kawasaki equation is derived. Furthermore, by rescaling the fluctuating Boltzmann equation under a distinguished relation between the noise intensity and the hydrodynamic scaling parameter, we prove that its Hamiltonian converges to the Hamiltonian of the Landau–Lifshitz–Navier–Stokes equations. This reveals a scaling relation between kinetic fluctuations and fluctuating hydrodynamics.

The mean exit time of a Brownian motion from a tube around a closed, minimal embedded \(n\)-dimen\-sional submanifold of the \((n+m)\)-dimen\-sional sphere is studied, establishing two-sided bounds via radial transplant. In accordance with known results when \(n = 0\) or \(m = 1,\) the mean exit time goes to infinity as \(n \to \infty\) and to \(0\) as \(m \to \infty.\) Simultaneously, bounds for the volume of such tubes are derived and compared to Weyl's tube formula.

Consider the $\mathbb Z_2$ synchronization problem \[ \boldsymbol{Y} = \frac{\lambda}{\sqrt n} \theta\theta^{\top} + \boldsymbol{Z}, \] where $\theta$ is uniform on $\{-1,1\}^n$ and $\boldsymbol{Z}$ is an independent Gaussian Wigner matrix with off-diagonal variance one. We give a polynomial-time posterior sampling algorithm for every fixed $\lambda>1$, for which the conditional output law converges to the posterior in total variation, in expectation over the observation. The construction combines sequential TAP proposals with an independence Metropolis correction. The key is to control signed overlaps after logarithmic pinning and conditional TAP approximations along a random revealing path, which give an efficiently evaluable proposal with a polynomial density-ratio bound outside a set of vanishing posterior mass. To the best of our knowledge, this is the first polynomial-time posterior sampler for $\mathbb Z_2$ synchronization with a total-variation guarantee throughout the supercritical regime. For comparison, the diffusion-based sampler of \cite{montanari2023posterior} gives normalized Wasserstein guarantees at sufficiently large fixed signal-to-noise ratio.

We propose a new variant of a biased random walk on a Galton-Watson tree, in which some vertices have infinitely many children. These vertices induce a natural regeneration structure, which allows to study differentiability and also monotonicity of the speed of the random walk in the bias parameter. Additionally, we show that the speed in this model is the limit of the speed of random walks on appropriate locally finite trees.

We prove that, on a Galton-Watson tree with almost surely finite offspring and infinite offspring mean, the random interchange process has critical parameter zero for infinite cycles, conditionally on survival. Combined with the finite-mean strict inequality established in arXiv:2503.03319, this gives a dichotomy for locally finite Galton-Watson trees with offspring mean in $(1,\infty]$: the loop and link critical parameters coincide exactly in the infinite-mean case. The proof reduces the tree problem to a finite permutation estimate derived from peeling estimates for random surfaces.

We study a one-dimensional multispecies TASEP model with each particle type having an associated speed parameter and faster particles overtaking slower ones with the rate being the positive part of their speed difference. After expressing the sorting time of a finite system given a reverse-speed initial condition as the maximum of sorting times for all different fast-slow cuts, we prove that forbidding fast-fast and slow-slow overtakes does not alter the law of the sorting time. This allows for an LPP formulation and an analytic expression of the sorting time.

We consider the adjacency matrix of a uniformly random simple $d$-regular graph on $N$ vertices. For every fixed $d\geq3$ and every fixed bulk energy, we prove that the rescaled eigenvalue point process converges to the $\mathrm{Sine}_1$ process with intensity $1/\pi$. We also establish universality of consecutive gaps at deterministic bulk labels and of fixed-energy correlation measures. The eigenvector input consists of polynomial estimates for mixed fourth moments on a uniformly sampled star. These estimates prevent loss of variance in the qualitative joint Gaussian limits of Backhausz–Szegedy, yielding independent variance-one Gaussian waves for fixed tuples at nearby energies. Exact switching identities then give a stationary marked flow and the microscopic loop hierarchy, which identifies the point-process limit. The appendices prove the stronger correlation and gap statements using counting-moment bounds and conditional log-gas laws for tagged limits.

We introduce mean-field Gibbs–Ornstein–Uhlenbeck (MFGOU) processes, a class of discrete-time Markov processes with increments of order $1/n$, whose conditional means approximate a smooth vector field. If the field has a unique attracting zero and satisfies a global Lyapunov condition, we prove \[ \tau_{\mathrm{mix}} = \frac{1}{\lambda_1}n\log n+O(n), \] where $\lambda_1$ is the smallest eigenvalue of the drift Jacobian at the attractor. Mean-field block measures form an important subclass encompassing mean-field spin systems and projected Gibbs samplers for Latent Dirichlet Allocation (LDA) and related mixture models. The leading mixing constant has a spectral expression involving the free-energy Hessian and the covariance of single-step dynamics. A block-refinement argument transfers projected-chain results to the full chain under a mild spectral condition, preserving this constant. The theory recovers known cutoff locations for Curie–Weiss Ising and Potts models and complete multipartite Ising models, gives an external-field formula for Curie–Weiss Ising, and covers regular-graph interactions. It yields explicit $n\log n$ asymptotics for multinomial mixtures and partially collapsed LDA. For full LDA, mixing is determined conditionally on the stationary-point structure of the free energy, distinguishing metastability from topic-label switching. The framework also applies to continuous-state Gibbs sampling, constant-step stochastic gradient descent, and frequently refreshed Hamiltonian Monte Carlo, rigorously for truncated Gaussian increments and heuristically without truncation. The proof combines variance and mean estimates with path coupling allowing slight expansion in expected distance. After rescaling, the coupling distance is a nonnegative supermartingale whose quadratic variation gives a positive probability of coalescence.

In this paper, we study one-dimensional semilinear stochastic wave equations driven by multiplicative space-time $G$-white noise under sublinear expectation. We establish the existence and uniqueness of global mild solutions. By developing the quadratic variation structure of space-time $G$-white noise and establishing a Burkholder-Davis-Gundy inequality for the associated stochastic integrals, we derive higher-order moment estimates and prove the quasi-sure Hölder continuity of the solutions. We further show that the mild solution satisfies the corresponding weak formulation.

We provide a very short proof of the following comparison theorem, which has recently played an important role: every centered subgaussian random vector is dominated in convex order, up to a universal constant, by a standard Gaussian random vector.

We study parabolic stochastic partial differential equations on metric measure spaces $(\mathbb{X}, d,m)$ of the form $$ \partial_t u(t,x) = \mathcal{L}^* u(t,x) + b(t,x,u(t,x)) + \sigma(t,x,u(t,x)) \dot{W}(t,x),\quad t>0,\, x \in \mathbb X, $$ where $\mathcal{L}$ is the generator of a Markov process which possesses transition densities, and $\dot{W}$ is a Gaussian noise that is white in time and possibly with spatial correlation. We assume the coefficients $b$ and $\sigma$ are Lipschitz and satisfy the linear growth condition. We formulate general and checkable assumptions on $(\mathbb{X},\mathcal{L},\dot{W})$ that ensure existence and uniqueness of probabilistically strong, continuous, tempered mild solutions. We then prove comparison principles (including a strong comparison principle) and strict positivity, relative to initial conditions. Our framework allows non-symmetric heat kernels and includes diffusion-type and stable-type examples, such as metric graphs and fractal spaces with sub-Gaussian heat kernel estimates.

For even $n$, let $P_n$ be the probability that independent uniform strict preference lists on $n$ participants admit a stable perfect matching. We prove \[ P_n\sim\frac{e\,2^{1/4}\Gamma(3/4)}{\sqrt\pi}\,n^{-1/4}. \] This establishes Mertens's conjectured exponent of decay, with a leading constant different from his original numerical prediction. The proof starts from Mertens's exact alternating sum over stable permutations. To preserve its cancellation, we construct a common approximation for all cycle structures with the same number of vertices in cycles longer than two. By symmetry, the integrated first-order correction is the same for every such cycle structure, and the remaining errors can be summed in absolute value. The enumeration then reduces the probability to a one-dimensional sum with positive terms.

The Kannan–Lovász–Simonovits (KLS) conjecture asserts that isotropic log-concave probability measures have Poincaré constants bounded by a universal constant, independently of dimension. We give a deterministic variational proof with an explicit bound on the Poincaré constant $C_P(\mu)\le25$, where $\mu$ is any isotropic log-concave probability measure. Starting from elliptic moment estimates and a quadratic variance inequality, we establish geometric bounds on normalized Appell coefficient norms through joint maximization over the measure and test function. Variation of the measure gives a maximum-principle inequality, while stationarity in the test function controls the highest-order cumulant terms. Two concave barriers constructed from quadratic and cubic polynomials close the induction. A weighted Helmholtz–Hodge decomposition then controls the curl correction of weighted divergence, yielding a curvature estimate for compatible symmetric tensor fields that is uniform in rank. Quadratic duality converts this estimate into an operator comparison for centered integration, linking the coefficient bounds to control of the inverse gradient. A spectral-radius estimate and a scalar growth inequality for adjoint iterates then yield the Poincaré bound. The final estimate is independent of the auxiliary positive curvature, allowing approximation to complete the proof for general isotropic log-concave measures.

We study the limit shape of the range of the random walk excited to the center on $\mathbb Z^d$, with $d\geq2$. A cookie is placed at each nonzero vertex. On its first visit to such a vertex, the walker consumes the cookie and takes its next nearest-neighbor step with a bias toward the origin. On a visit to the origin, or on later visits to a nonzero vertex, no cookie is available and the walker moves to a neighbor uniformly at random. We prove that the set of vertices visited up to time $n$, rescaled by $n^{-1/(d+1)}$, converges in probability in Hausdorff distance to an explicit $\ell^1$ ball. This answers a question raised by Kozma (2007).

We study sampling discretization of the uniform norm for trigonometric polynomials with frequencies in a hyperbolic cross of level $N$ on $\T^d$. For every $d,N\ge2$ and $\varepsilon\in(0,1)$, we construct an explicit norming set with at most $\bigl(C_1(1+\varepsilon^{-1})\bigr)^{d-1}N^{1+\varepsilon}$ points and norming constant at most $\bigl(C_2(1+\varepsilon^{-1})\bigr)^{d-1}$, where $C_1,C_2$ are absolute constants. We also prove that independent Haar-distributed points achieve the same exponent $1+\varepsilon$: a sample of size at least $C(d,\varepsilon)N^{1+\varepsilon}\log(2/\eta)$ norms the entire space simultaneously with probability at least $1-\eta$, with a norming constant bounded by $\exp(C_d\varepsilon^{-d})$ and independent of $N$. The deterministic construction combines uniformly stable de la Vallée Poussin sampling operators with a Smolyak-type combination identity. The random result follows from an abstract norming theorem for sums of spaces associated with commuting regular partitions, together with a multiscale approximation of hyperbolic-cross polynomials. Finally, we show that every norming set of constant $B>1$ for the trigonometric polynomials with frequencies in $\{-1,0,1\}^d$ has at least $\bigl(\pi d/(2e\log B)\bigr)^{d/2}$ points. This rules out quadratic bounds in the dimension of the polynomial space with a prefactor growing only polynomially in $d$ when the norming constant is fixed.

When a feasible plan is obtained whose quadratic transport cost is known to be close to the optimal cost, we try to determine how close the feasible plan is to the true optimal map under mild density and moment conditions. The source and target may be unbounded or have non-compact supports. We show that for a source with density in $L^p$ and an $n$-th moment, let $s=1-1/p$ and $\eta=sn/[n+(d-1)s]$. Under the target constraint $\int |y|^m[\log(e+|y|)]^\beta\,d\nu\leqslant1$, the worst-case class-uniform conditioning has a sharp modulus comparable to \[ t^{\eta(m-2)/[m(1+\eta)-\eta]} [\log(e/t)]^{-\beta(2+\eta)/[m(1+\eta)-\eta]}, \] whenever $t>0$ is small. This holds for $m\geqslant2$ and $\beta\geqslant0$. When $m=2$, every $\beta>0$ gives a sharp logarithmic modulus, whereas the $m=2,\,\beta=0$ extreme has no vanishing modulus. The matching lower bound is verified for both the squared map error and barycentric projection error. The sharp map error bounds allow us to directly derive quantitative stabilities of common source Brenier maps without passing through potential estimates, thereby avoiding loss of information. These stabilities strictly improve the corresponding results of Delalande-Merigot \cite{delalande2023quantitative} and Letrouit-Mérigot \cite{letrouit2026gluing} under identical or weaker settings, particularly no convexity of the source support or bounds of the source density are assumed.

Consider a finite planar graph with positive real edge weights and designated boundary vertices, called nodes. Such a graph is called a circular planar electrical network. A grove is a spanning forest in which every component contains at least one node. The connected components of a grove determine a partition of the nodes. We relate weighted grove counts to invariant theory for the symplectic group. To a planar electrical network $G$, we associate an $\mathrm{Sp}(2n)$-invariant tensor $Z_G$. For $\mathrm{Sp}(2)=\mathrm{SL}(2)$, we expand $Z_G$ in the Temperley–Lieb basis indexed by noncrossing matchings and relate its coefficients to the Kenyon–Wilson grove formulas. For $\mathrm{Sp}(4)$, we give reduction rules for superpositions of two groves and prove that the tensors indexed by $3$-noncrossing matchings form a basis of the space of $\mathrm{Sp}(4)$-invariant tensors. The coefficients of $Z_G$ in this basis are weighted counts of reduced double groves, up to normalization.

Let $\varepsilon_1,\ldots,\varepsilon_n$ be independent Rademacher random variables. We settle the best constant $c$ such that \[ \mathbb{E}\Bigl|\sum_{j=1}^n a_j\varepsilon_j\Bigr| \ge \frac{1}{\sqrt{2}} +c\Bigl|a-\frac{e_1+e_2}{\sqrt{2}}\Bigr| \] holds for every $n\ge 2$ and every unit vector $a\in\mathbb{R}^n$ with $a_1\ge\cdots\ge a_n\ge 0$. We prove that the optimal constant is $c=(2-\sqrt{2})^{3/2}/8$, with equality attained at $a=\frac{1}{2}(1,1,1,1,0,\ldots,0)$ for $n\ge 4$. This completes a line of research by De-Diakonikolas-Servedio, Eskenazis-Nayar-Tkocz and Fang-Wang.

We determine how wide a randomly initialized ReLU layer must be to distinguish every pair of inputs. For independent Gaussian weights and zero bias, as the dimensions grow at a fixed output-to-input ratio, the probability of global injectivity tends to zero below a sharp threshold and to one above it. We characterize this threshold exactly through a variational formula for the limiting minimum number of active neurons per input coordinate. The formula accounts for correlations among input directions at arbitrarily many levels. We prove this formula rigorously, establishing a prediction from the statistical physics of the spherical perceptron. The proof compares systems of nearby dimensions and controls a Gaussian interpolation by calibrating responses to auxiliary fields. A uniform volume estimate connects the soft minimum to the worst input direction. An exact-arithmetic calculation places the threshold below seven output neurons per input coordinate. Numerical evaluations suggest a value near 6.698.

In this paper, we show that the height function of the six-vertex model in simply connected domains with piecewise constant boundary conditions converges to the Gaussian Free Field (GFF) with Dirichlet boundary conditions. This implies the conformal invariance of the scaling limit of the model. The argument relies on the full plane GFF convergence combined with Reflexion Positivity and qualitative estimates. The proof works for a wide range of spectral parameters $\Delta$ (among which $\Delta$ close to $0$, and between $-1$ and $-1/2$) making this paper the first instance of a conformal invariance result for a continuum of models. The paper has consequences for other models, including the FK percolation with cluster-weight $q=4$ and the Ashkin-Teller model, which we will pursue in future work.

Let $A$ be a positive continuous additive functional of a strong Markov process and $\alpha$ an independent finite-state Markov chain. For bounded $h$, we study \[ J_\varepsilon(t)=\int_0^t\bigl(h(\alpha_{s/\varepsilon})-\pi(h)\bigr)\,dA_s . \] If $\sup_y \mathrm E_y A_t\le C_T t^\vartheta$, then for every bounded random time determined by the base process, not necessarily a stopping time, \[ \mathrm E|J_\varepsilon(\tau)|^2=O(\varepsilon^\vartheta),\qquad \mathrm E\sup_{t\le T}|J_\varepsilon(t)|^2 =O\!\left(\varepsilon^\vartheta(1+|\log\varepsilon|)^2\right). \] For reflected Brownian boundary local time, the exponent $1/2$ is sharp at fixed time. We apply this principle to reflected Brownian motion with rapidly switching Wentzell boundary dynamics. The homogenized boundary condition is again of Wentzell type, with stickiness and killing coefficients given by invariant averages. For bounded Lipschitz observables, the quenched Feynman–Kac error has every polynomial rate below $1/8$, uniformly over deterministic times and in expected uniform norm. For smooth Neumann-compatible observables with proportional killing and stickiness, the rate improves to $O(\varepsilon^{1/4})$, up to a logarithmic factor in the uniform-in-time estimate. We also construct the switching process, derive quenched and annealed backward evolutions, and transfer the estimates by duality to the forward measure evolution. For the forward evolution, we obtain quantitative convergence in bounded-Lipschitz distance and the sharper $1/4$ rate for smooth observables, including surviving mass. Numerical experiments illustrate the finite-scale convergence.

We show that, in random hypergraphs with several permitted edge sizes, non-uniformity affects existential and algorithmic bounds for 2-colorability (Property B) in fundamentally different ways. Assigning weight $2^{-k}$ to each $k$-edge, we obtain upper and lower bounds in terms of the total edge weight that asymptotically match the uniform bounds as the minimum permitted edge size grows, regardless of how edges are distributed among sizes. We also extend the best-known algorithm for 2-coloring random uniform hypergraphs to the non-uniform setting. With weight $\frac{k}{2^k}$ assigned to each $k$-edge, we construct non-uniform instances whose expected total edge weight per vertex is arbitrarily large, yet the algorithm finds a proper coloring asymptotically almost surely. In the uniform setting, the algorithm fails with high probability once this quantity exceeds a constant. Our construction uses sufficiently separated edge sizes, so that edges of different sizes become relevant at well-separated stages of the execution and their effects are essentially independent.

A single spatial snapshot of a system with multiple interacting populations captures positions but not the underlying dynamics that have led to the observation. This work asks what the stationary second-order spatial statistics of a snapshot can reveal about the structure of the linear reaction-diffusion dynamical model, and in particular about the pairwise directed entries of its interaction operator. The observation is the matrix-valued structure factor $S(k)$ as a one-parameter family in the diffusion-inherited dependence on the wavenumber $\kappa=|k|^2$. The main result is that the directed interaction operator $A$ and the diffusivity matrix $D$ are generically identifiable for any number of interacting populations from $\{S(\kappa)\}$ up to a single global time rescaling. The findings do not contradict known bounds and the recent result that spatial observational data only determine the Markov equivalence class of the underlying graph. In this work, we identify physical assumptions that lift this barrier. The absolute time scale is not identifiable from a single snapshot of any sample size and requires an external clock. For tumor-immune tissue, the results imply that directed cell-cell interactions are in principle recoverable from one section, that the direction cannot be inferred from the mean densities or a covariance matrix, but from the wavenumber dependence of the cross and autospectra, and that a baseline section determines the interaction structure but not the absolute rates.

We study an online trading problem where a trader, given a sequence of i.i.d. prices drawn from a known distribution $F$ on $[0,1]$, must make irrevocable buy, sell, or hold decisions subject to storage constraints. We investigate achievable algorithmic performance measured in terms of regret, the difference between the expected profit of the hindsight optimal policy that knows the entire price sequence and an online algorithm. We analyze finite atomic and continuous distributions characterized by their local behavior around the median which we capture using a parameter $\beta$. The parameter $\beta$ quantifies how the mass of prices accumulates around the distribution median. We identify a new driver of algorithmic performance, demonstrating that median gaps coupled with an initial inventory level of zero can force regret scaling of $\Omega(T^{(\beta + 1)/(2\beta+4)})$ — establishing a novel spectrum of fundamental limits on algorithmic performance. We then study STARS, short for Storage Trading by Averaging Repeatedly across multiple Scenarios, which simulates possible future price scenarios to approximate the value-to-go function and make buy/sell/hold decisions. We show that STARS obtain near-optimal algorithmic performance (upto poly-logarithmic factors) across a broad range of distributions. In particular, it achieves $O(\log T)$ regret for finite atomic prices, $\widetilde{O}(T^{\beta/(2\beta+2)})$ for continuous distributions without a median gap and $\widetilde{O}(T^{(\beta+1)/(2\beta+4)})$ for continuous distributions with a median gap for $\beta \geq 0$.