Papers

Real-world networks like the internet share patterns like a power law degree distribution and a high clustering coefficient. Many of these properties are captured by the generative model of hyperbolic random graphs (HRGs), which provides a theoretical framework for studying such networks. Motivated by the observation that several algorithms perform better on real-world networks than their worst-case guarantees suggest, we design and analyse distributed algorithms under the assumption that the input graph is an HRG. Indeed, prior work has shown that the classical symmetry-breaking problem of $\Delta+1$ colouring, where $\Delta$ is the maximum degree of the graph, can be solved in 2 rounds on HRGs [Maus and Ruff; SODA'26]. In stark contrast to this 2-round algorithm for $\Delta+1$ colouring, we prove that the related symmetry-breaking problems of maximal independent set (MIS) and maximal matching (MM) are substantially harder: we establish a lower bound of $\Omega\left(\frac{\log\log n}{\log\log\log n}\right)$ for MIS and MM on HRGs. Our lower bound techniques rely on new structural insights that may be of independent interest: we show that HRGs contain $d$-ary trees with large height and degree which enables us to adapt and lift prior impossibility results for distributed algorithms to the setting of HRGs. We also show that these lower bounds are polynomial tight: we design algorithms tailored to HRGs that solve MIS and MM in $\tilde{\mathcal{O}}(\log^{5/3}\log n)$ rounds with high probability in the LOCAL model, improving over the general worst-case lower bound of $\Omega\left(\min\left\{\log \Delta, \sqrt{\log n}\right\}\right)$ rounds [Khoury and Schild; FOCS'25].

We extend Gårding's theorem to homogeneous posynomials: if a finite positive sum of monomials with arbitrary nonnegative real exponents is zero-free on a product of right half-planes, then its degree-normalized root is concave. Consequently, zero-freeness in a sector of aperture $\alpha\pi$ implies $\alpha$-fractional log-concavity. This sharpens generic mixing and domain-sparsification guarantees for fixed-size matchings and nonsymmetric determinantal point processes. The result was developed in an AI-assisted interaction initiated and checked by the author; Codex also assisted with assembling and typesetting the manuscript.

We prove asymptotic formulae for positive real $(p,q)$-Rogers-Szegő polynomials when the quadratic term in the expansion about the middle coefficient vanishes. For coefficient indices whose distance from $n/2$ is of order $n^{3/4}$, the coefficient ratios have a quadratic-quartic exponential limit. A uniform bound valid for all indices allows the ratios to be summed and gives locally uniform convergence of the centred generating polynomials to a Fourier–Laplace integral. We also obtain an asymptotic formula for the sum of the coefficients, convergence of all rescaled moments, weak convergence of the normalised coefficient measures, and convergence with multiplicity of the zeros tending to $w=1$.

In this note, we study distortion risk measures of step-weighted distribution.

We study pathwise well-posedness of the stochastic heat equation (SHE) with a multiplicative noise on the circle. By combining the convolution Young and rough integration theory, introduced by Gubinelli and Tindel (2010), with the random tensor estimate approach to pathwise well-posedness of stochastic dispersive PDEs with multiplicative noises, introduced by Chapouto and the second and third authors (2026), we establish pathwise well-posedness of SHE in both the Young and rough cases, improving the results in Gubinelli and Tindel (2010). In particular, in the rough case (= the white-in-time case), our result covers the case of almost space-time white noise, thus establishing an optimal result within the framework of one-parameter rough paths.

We study the problem of recovering the correspondence between a collection of $n$ points in $\mathbb{R}^d$ and a noisy, permuted version of those points. In the high-dimensional regime $d=\omega(\log n)$, under a Gaussian model with noise variance $\sigma^2=d/(b\log n)$, prior work identifies $b=2$ as the threshold for almost exact recovery. We prove that this threshold is all-or-nothing: for every fixed $b<2$, no estimator recovers a positive fraction of the matching, and even estimating the matched point cloud in Euclidean distance is asymptotically no better than ignoring the correspondence. On the other hand, we consider a multi-view generalization of the problem where $K$ noisy, independently permuted copies of the same latent point cloud are observed. Here we show that a simple polynomial-time procedure recovers all relative matchings up to $o(n)$ errors whenever $b>K/(K-1)$. Thus multiple views can break the impossibility barrier $b=2$ for the original matching problem: in particular, for $3/2 < b < 2$, the two-view model has no nontrivial recovery, but a third view makes all latent correspondences efficiently recoverable.

We revisit the pathwise global well-posedness issue of the modulated Korteweg-de Vries equation (KdV) on the circle. In the previous work (2024), by combining the $I$-method and the sewing lemma, the second and fourth authors with C. Chouk, G. Li, and J. Li proved its global well-posedness in negative Sobolev spaces. This result was, however, restricted to the scaling subcritical regime $s > - \frac 32$ due to the use of the classical KdV scaling. In this paper, by noting that the modulated KdV enjoys additional one degree of freedom in its scaling symmetry thanks to the modulation term, we apply a non-KdV scaling to the unknown and prove that, given any $s \in \mathbb R$, the modulated KdV on the circle with a sufficiently irregular modulation is globally well-posed in $H^s(\mathbb T)$, thus going beyond the barrier of the scaling critical regularity $s = - \frac 32$.

In large-scale computing systems, jobs often demand heterogeneous server allocations: large jobs that occupy a substantial fraction of the servers are of high importance and are thus latency-sensitive, while small jobs fill in the remaining capacity to maintain throughput. To model this dynamic, we introduce the half-batch multiserver-job (MSJ) framework, a queueing model in which large jobs arrive according to a Poisson process and require all servers simultaneously, while small jobs, each needing only one server, are always available. We prove that, in the half-batch MSJ model, the Pareto frontier for large-job mean response time and small-job throughput admits a simple and exact characterization. It is generated by a family of convoy policies, under which the system serves small jobs until $k$ large jobs have arrived and then switches to serving large jobs, together with convex combinations of neighboring convoy policies. Our result is fully general and non-asymptotic, holding for every stable arrival rate $\lambda$, every number of servers $n$, and every large-job size distribution $S$.

We study the variance of the free energy in the Gaussian Sherrington-Kirkpatrick model at zero external field. For every system size and inverse temperature $\beta>0$, we prove $2N^2\operatorname{Var} F_N^{\mathrm{off}}(\beta) \le \log\chi+(\beta^2-1)(\chi-1), \chi=N\mathbb{E}\langle R_{1,2}^2\rangle_\beta$, where $R_{1,2}$ is the replica overlap and $F_N^{\mathrm{off}}=N^{-1}\log Z_N^{\mathrm{off}}$ omits diagonal disorder. The proof uses an exact identity for the edges incident to one spin, Schur complements, and Gaussian disorder interpolation. At criticality the bound reduces to $2N^2\operatorname{Var} F_N^{\mathrm{off}}(1)\le\log\chi$. An explicit nonnegative integral measures its gap. A second decomposition relates this gap to a mixed cubic overlap functional. Existing moment and cavity estimates imply that its required integral is bounded. Critical susceptibility asymptotics give the sharp logarithmic upper coefficient and show that the gap converges exactly when the variance has a constant term. We extend an entropy bound throughout bounded critical temperature windows and establish overlap moment stability on a smaller interval.

For a broad class of discrete-time, finite-range interacting particle systems on $\mathbb{Z}$, we establish a linear spreading speed and a one-dimensional shape theorem on the event of survival, without assuming monotonicity or attractiveness of the dynamics. The method requires that the system admits a coupling with supercritical oriented percolation on a coarse-grained lattice. The central technical step is an approximate subadditivity property for the hitting times, obtained through a `shifted coupling' that compensates for the absence of monotonicity. As a concrete application, we show that a discrete-time branching annihilating random walk fits into this framework, and consequently exhibits a linear spreading speed.

Let $K$ be a convex body in $\mathbb{R}^d$, and let $I$ and $B$ be random points uniformly distributed inside $K$ and on its boundary, respectively. We prove that if $d=2$ and $\mathbb E I = \mathbb E B$, or if $K$ is a circumscribed polytope with the center of the inscribed sphere coinciding with $\mathbb E I = \mathbb E B$, then $I$ is dominated by $B$ in the convex order. As a consequence, for any function $\varphi$ convex in each argument, the expectation $\mathbb E \varphi(I_1,\dots,I_k)$ does not exceed $\mathbb E \varphi(B_1,\dots,B_k)$. This yields, in particular, an inequality between the moments of random chords $\mathbb E |I_1 - I_2|^p \leqslant \mathbb E |B_1 - B_2|^p$ for all $p \geqslant 1$, confirming the Zaporozhets–Tarasov conjecture for the indicated class of bodies, and extends to inequalities for mean volumes of random simplices.

In this article we investigate the theoretical convergence properties of the fictitious-play approximation procedure applied to coupled FBSDE systems for finite-player non-zero-sum stochastic differential games. Under one set of assumptions, the convergence is shown to be geometric. Under an additional structural assumption, the geometric convergence rate further improves to a super-exponential rate in a special class of games. To the best of our knowledge, this provides the first convergence analysis of fictitious play for fully coupled FBSDEs. A numerical experiment with a linear-quadratic interbank borrowing and lending problem confirms the geometric convergence.

Score matching controls average error under the forward marginals, but a discretized reverse-time sampler evaluates the learned score along its own trajectory. We show that small forward-marginal error does not guarantee numerical stability. We construct a single smooth score field with arbitrarily small forward-marginal $L^2$ error. The learned reverse-time process is nonexplosive, has moments of every order, and can be arbitrarily close to the exact reverse-time process in path-space total variation. Yet its Euler–Maruyama discretizations converge in probability while every positive moment diverges. Thus weak convergence can hold even though every Wasserstein distance $W_p$, $p\ge1$, diverges. The same failure can occur within one fixed finite neural architecture. We construct a family of bounded, globally Lipschitz denoisers for which both the forward-marginal error and the path-space total variation distance tend to zero, while their Euler–Maruyama endpoints diverge in every $W_p$. For compactly supported data, we also give a simple positive result. Projecting the learned denoiser onto a known bounded closed convex set containing the support preserves pointwise accuracy, gives grid-uniform moment bounds, and yields Wasserstein convergence under mild local regularity. Experiments with a small fixed DiT-style network show large growth along rare numerical trajectories and its suppression by denoiser projection, while overall trajectory errors remain small.

We study the spectrum of the adjacency matrix $A_n$ of directed inhomogeneous random graphs on $n$ vertices. We assume that $A_n$ has independent entries and diverging average degree scale $s_n$. This framework includes, as special cases, the directed Chung–Lu random graph and directed stochastic block models. Assuming boundedness of the variance profile and that $s_n$ diverges faster than $\log(n)^2$, we show that the rank-one Chung–Lu model satisfies a non-homogeneous version of the circular law, which in some situations allows for an explicit expression. Moreover, under mild conditions, we identify the asymptotic singular value distribution using tools from free probability. Finally, for finite-rank directed models, we establish that eigenvalues outside the bulk have joint Gaussian fluctuations at the scale $\sqrt{s_n/n}$, with an explicit covariance matrix. These results extend the theory of spectral outliers and their fluctuations to directed inhomogeneous random graphs.

We construct a measure that exhibits two aspects of a new type of universality and dramatically simplifies the integration of tensors $T_{a_1,a_2,\ldots,a_D} \in \mathbb{C}$ ($a_1,\ldots,a_D=1,\ldots,N$) at large $N$. In contrast to matrix integration, in which matrix traces canonically yield the integrand, tensors need additional information (equivalent to a $D$-coloured graph $B$) to contract their indices and form a tensor trace $B(T)$. We show that, whenever each $B_1,\ldots, B_n$ can be obtained by a recursive construction known as melonicity, then the leading order in $N$ of the integral of $ {B_1}(T) {B_2}(T) \cdots {B_n}(T) $ is independent of the – often intricate – combinatorics of the traces $B_i$, but also, to our surprise, independent of $D$ as far as $D\geq 3$. Instead, at large $N$, these integrals are some functions (indexed by $n$) of the number of vertices $2p_i$ of $B_i$ which we call melonic polynomials. Melonic traces cumulants with respect to any ('interacting') measure \[ \exp\Big\{-N^{D-1} \sum_{i=1}^m g_i {B_i}(T)\Big\} \mathrm{d}\mu_0(T) \quad (g_1,\ldots,g_m \in \mathbb{R}, \mathrm{d}\mu_0(T) =\text{the tensor Gaussian}) \] with each $B_i$ melonic, can be computed with our universal measure that replaces each $B_i$ by a canonical trace depending only on $p_i$. We prove that any two melonic tensor models are indistinguishable at large-$N$, independently of the number of tensor indices (first universality aspect), and of the fine-grainedness of their interactions (second universality), being a sufficient condition that the couplings (the parameters $g_i$ above) agree and their respective traces are monomials with the same degree in $T$.

We study stochastic barycentric estimators for proximal points and metric projections obtained by exponentially reweighting Gaussian perturbations. Our main result is an abstract comparison theorem for probability measures with densities proportional to an exponential weight, under a radial dominance condition relative to a prescribed profile. This yields an explicit upper bound for the norm of the associated barycenter in terms of a one-dimensional comparison measure. We also provide tractable sufficient conditions for radial dominance, including strong convexity, addition of nonnegative convex terms, and star-shaped constraints. As a consequence, we obtain a refined convergence rate for stochastic proximal estimators of weakly convex functions, together with asymptotic sharpness of the constant. The same framework yields a corresponding rate for stochastic projection estimators onto closed convex sets. We further establish basic structural properties of the barycentric approximation operator, such as smoothness and cocoercivity. Numerical experiments illustrate the predicted rate, the dimensional scaling of the constant, and its asymptotic sharpness.

We construct an uncountable family of extremal Gibbs states of the low temperature Ising model on hyperbolic lattices embedded in the hyperbolic plane $\mathbb{H}_2$ whose interfaces are complete geodesics of $\mathbb{H}_2$. These states are extracted from the states constructed by D'Achille, Coquille and Le Ny in arXiv:2504.19553v2 by considering path in the dual lattice at close enough distance from geodesics of $\mathbb{H}_2$ thanks to the Morse–Mostow lemma.

Recently, there has been significant interest in applying the method of moments developed by Wood and others to study distributions of finite abelian groups that arise in number theory and combinatorics. When the moments do not grow too fast, they determine a unique distribution. We construct large families of distributions that have the same moments. These families include several distributions that arise naturally in the study of sandpile groups of families of random graphs. Wood determined the distribution of Sylow $p$-subgroups of sandpile groups of Erdős–Rényi random graphs. This was extended by Mészáros to sandpile groups of random $d$-regular graphs, who observed an interesting special case when $d$ is even and $p = 2$. We study Sylow $p$-subgroups of sandpile groups of random bipartite graphs and similarly find a special case for $p =2$. Although this distribution differs from that of Mészáros, we show that they have the same moments and fit into our broader construction. To compute the moments of the distributions we study, we apply combinatorial tools from the theory of Hall–Littlewood functions.

We study a class of random inner functions $\varphi$ whose Clark measure at $1$ is the weighted sum of point masses supported on independent uniformly distributed points of $\mathbb T$. Our first result shows that $\varphi$ is almost surely a Blaschke product. We then investigate when $\varphi$ admits angular derivative almost surely and we provide a $0 - 1$ law. These conditions have a direct interpretation in terms of the other Clark measures associated with $\varphi$. Finally, we obtain quantitative estimates for the zeros of $\varphi$, proving that, in suitable regimes, their distribution satisfies summability conditions stronger than the classical Blaschke condition.

We study a weighted-threshold version of the coupon collector problem in continuous time. Each type $i$ is discovered at rate $\lambda p_i$ and, once discovered, contributes weight $w_i$, where $p$ and $w$ are probability vectors. The stopping time when the total weight of the discovered types first exceeds a fixed threshold $\theta\in (0,1)$ is called the quorum time. We first prove concentration estimates and compare the quorum time with the corresponding deterministic threshold time obtained from the mean discovered weight. When all discovery rates are equal and the largest individual weight tends to zero, the first-order asymptotics are universal and do not depend on the weight vector. We then analyze the aligned Zipf family $p_i = w_i \propto i^{-s}$. This model has three regimes: a deterministic linear scale for $0\le s < 1$, a critical scale $H_NN^\theta$ at $s=1$, with an explicit leading constant, and a non-degenerate random hitting-time limit for $s>1$. Finally, we show that the expected quorum time need not be monotone in the Zipf exponent.

We show that the lower edge of the appropriately scaled size $n$ Laguerre beta-ensemble with parameter $a=a_n$ converges to the $\operatorname{Airy}_{\beta}$ process as $n\to \infty$ when $a_n\to \infty$ and $\tfrac{a_n}{n}\to 0$. This completes the picture of the possible edge scaling limits of the Laguerre beta-ensemble with a fixed $\beta>0$. When $a_n\gg (\log \log n)^3$ our proof establishes operator level convergence of the inverse of the scaled Dumitriu-Edelman tridiagonal matrix to the inverse of the stochastic Airy operator. Our methods allow us to prove similar operator level limits for the known soft edge scaling limits of the Laguerre and Gaussian beta-ensembles. For $a_n\le (\log n)^{1/2}$ we give a different argument that relies on coupling and a result of Dumaz-Li-Valko for the transition between the hard and soft edge limits of the Laguerre beta-ensemble.

Assuming that the asset price $X$ follows a constant elasticity of variance process, this paper studies the optimal prediction problem $\inf_{0\leq \tau\leq T}\mathbb{E}|X_\tau-\ell|$, where the infimum is taken over stopping times $\tau$ of $X$ and $\ell$ is a hidden aspiration level independent of $X$. Adopting the aspiration level hypothesis, we show that a class of admissible laws of $\ell$ leads to optimal trading boundaries which are located relative to the median interval of $\ell$ and serve as predictors of the resistance and support levels. The existence of these boundaries is proved and nonlinear integral equations are derived to characterise them uniquely. In the positive drift case the stopping set is bounded by two curves, while in the negative drift case the stopping set is described by a single boundary.

Hansen and Pitts (2006) introduced the problem of nonparametric estimation of the service-time distribution of an M/G/1 queue observed through its workload process at discrete times $t=0,1,\ldots,n$. Despite its seemingly simple formulation, obtaining an estimator with sharp risk guarantees for this observation model has remained an open challenge for nearly two decades. In this paper, we construct such an estimator and prove that its $L^1$-risk is $\mathcal{O}\left(\frac{\log n}{\sqrt{n}}\right)$ as $n\to\infty$. Remarkably, this nearly parametric convergence rate is achieved without assuming stationarity, stability, or knowledge of the arrival rate. Our approach is based on a two-stage screening procedure that uncovers a hidden conditionally independent compound Poisson structure within the dependent workload observations. This probabilistic reduction transforms the original estimation problem into a classical decompounding problem, making it possible to leverage existing nonparametric estimation techniques despite the complex dependence induced by the reflected workload process. More broadly, we hope that the proposed screening methodology will provide a useful framework for statistical inference from dependent stochastic systems beyond the classical assumption of stability.

This article concerns interacting particle systems with singular kernels, driven either by degenerate deterministic controls or by degenerate decomposable noise. In the deterministic setting, we establish global exact controllability and a topologically robust property called solid controllability. Moreover, we prove a result that guarantees global approximate controllability with prescribed trajectories. For stochastic dynamics, we obtain ergodicity and exponential mixing by utilizing coupling and recurrence mechanisms based on controllability. Our approach exploits the singularity and applies to a broad class of models, including Biot-Savart, Coulomb, Riesz, and Yukawa interactions, as well as heterogeneous multi-species systems.

Let $X=(X_1,\ldots,X_n)$ be independent nonnegative random variables, not necessarily identically distributed. Let $D=(D_0,D_1,\ldots,D_n)\sim\operatorname{Dir}(1,\ldots,1)$ be independent of $X$, and define $K(x)=\mathbb{P}\{\sum_{i=1}^n x_iD_i\le1\}$. We prove that, for every $n\ge1$, whenever $\mathbb{E} X_i\le1$ for every $i$, $\mathbb{P}\{K(X)\le\alpha\}\le\alpha$ for all $0\le\alpha\le1$. Thus $K(X)$ is a finite-sample, distribution-free $p$-value for testing the null hypothesis $\mathbb{E}X_i \le 1$ for all $i$. This proves a conjecture of Gaffke (2005).

We investigate pathwise well-posedness of the stochastic modulated Korteweg-de Vries equation (KdV) on the circle with a multiplicative noise, where a time non-homogeneous modulation acts on the linear dispersion term. (i) In the Young case (= fractional-in-time case with Hurst parameter greater than $\frac 12$), we establish a new regularization-by-noise phenomenon on the stochastic convolution in a pathwise manner, where a gain of spatial regularity becomes (arbitrarily) larger for more irregular modulations. We then prove that, given any $s \in \mathbb R$ and any multiplicative Young noise, however rough it is in space, the stochastic modulated KdV is pathwise locally well-posed in $H^s(\mathbb T)$, provided that the modulation is sufficiently irregular. (ii) In the rough case (= white-in-time case), irregularity of the modulation does not induce any smoothing on the stochastic convolution, and in fact, there is a slight loss in the spatial regularity. In this case, by slightly regularizing the multiplicative noise term, we prove pathwise local well-posedness in $H^s(\mathbb T)$ for any given $s \in \mathbb R$, provided that the noise is sufficiently smooth in space. We achieve these goals by combining (i) the sewing lemma approach to the nonlinear Young integration theory, introduced by Chouk and the second author (2014), and (ii) the pathwise construction of stochastic convolutions as Young or rough integrals via the random tensor estimate and the sewing lemma, introduced by the first, fourth, and fifth authors (2026). In the appendix, we also present an example of regularization by noise for a stochastic modulated Schrödinger equation with a multiplicative Young noise.

We consider the zero-temperature stochastic Ising process describing $\pm 1$ spin-flip dynamics on an infinite one-dimensional quasi-transitive graph $G=(V,E)$ with finite interaction range $K$. We prove that the zero-temperature limit of the Glauber dynamics for this Ising model exhibits a Type $\mathcal{I}$ behavior (infinite fluctuations of all vertices) if and only if the graph possesses the so-called shrink property. For graphs lacking this property, we introduce an algorithmic framework based on an auxiliary spatial automaton to distinguish, in finite time, between Type $\mathcal{F}$ behavior (almost sure local fixation) and Type $\mathcal{M}$ behavior (a mixed regime characterized by the presence of blinkers). We prove that the classification among these three regimes is algorithmically decidable. Furthermore, we provide a constructive example of a graph supporting blinkers of arbitrarily large size.

We construct a new family of random fields on the Heisenberg group $\mathbb{H}$, the sub-Riemannian analog of $\mathbb{R}^{n}$. These fields are generalized random eigenfunctions of the sub-Laplacian on $\mathbb{H}$, and can be viewed as the sub-Riemannian counterpart to the Berry random wave model in $\mathbb{R}^{n}$. The construction of such waves relies on the representation theory of $\mathbb{H}$, and differs from the Euclidean case because of the presence of infinite-dimensional unitary irreducible representations. This work represents a first step towards studying random waves and their geometry in sub-Riemannian spaces.

Random sums of independent random variables have been extensively studied in classical probability theory. We consider random sums of self-adjoint variables from a non-commutative probability space, and establish several $*$-convergence results. In particular, we show that the joint $*$-convergence of the standardized random sum of identically distributed self-adjoint variables and the standardized stopping random variable (rv) is equivalent to the convergence of all moments of the stopping rv together with the convergence of the ratio of its mean to its variance. We obtain central limit theorems for the random sums of free, independent and half independent self-adjoint variables with both deterministic and random scaling. Furthermore, we derive some scaling $*$-convergence limits for randomly indexed self-adjoint variables.

In this paper, we study the asymptotic behaviours of a critical branching random walk in $\mathbb{R}^d$ under the assumption that the offspring distribution belongs to the domain of attraction of an $\alpha$-stable law with $\alpha\in(1,2]$, and that the jump distribution has a finite $\frac{2\alpha}{\alpha-1}$-th moment. First, we establish the precise decay rate for the tail probability of the all-time maximal displacement $M^d$. Next, we investigate the maximal displacement $M_n^d$ at generation $n$ and prove a conditional limit theorem for the distribution of $M_n^d$ given that the process survives up to generation $n$. These results extend the corresponding 1-dimensional results of Lalley and Shao (2015) to the case $d\ge2$. Finally, we study the asymptotic behaviour of the total progeny $\zeta$. In particular, we show that, conditioned on the event $\{M^d\ge x\}$, $\zeta$ converges in distribution under an appropriate normalization. This result reveals a quantitative relationship between the maximal displacement and the total progeny size.