Papers

We study online discrepancy minimization: vectors $v_1,\ldots,v_T\in\mathbb{R}^n$ arrive sequentially, and each must immediately be assigned a sign $x_t\in\{\pm1\}$, with the aim of minimizing $\|\sum_{t=1}^T x_t v_t\|_\infty$. We give a polynomial-time potential-based algorithm combining a regularization of the $\ell_\infty$-norm with restriction to an adaptively chosen coordinate set. For i.i.d. inputs with independent, symmetric, centered, unit-variance sub-Gaussian coordinates of sub-Gaussian norm at most $\sigma$, the algorithm achieves terminal discrepancy $O(\sigma^8\sqrt{n})$ with probability at least $1-\exp(-\Omega(\sigma^3\sqrt{n}))$. If the coordinates are independently masked by Bernoulli variables with mean $k/n$, where $k\gtrsim(\log n)^2$, the bound improves to $O(\sigma^8\sqrt{k})$, with failure probability $\exp(-\Omega(\sigma^3\sqrt{k}))$. Both guarantees hold for every prescribed finite horizon $T$, with no dependence on $T$. The dense result substantially generalizes a theorem of Bansal and Spencer (2020) for Rademacher inputs and gives an efficient $O(\sqrt{n})$ bound for Gaussian inputs, as conjectured by Gamarnik et al. (2022). When $T$ is polynomially larger than $n$, this is conditionally close to optimal: under worst-case hardness assumptions for standard approximate lattice problems, Vafa and Vaikuntanathan (2025) showed that no polynomial-time algorithm, even offline, can improve the $\sqrt{n}$ scale by a fixed polynomial factor in $T/n$.

We study the $\beta=2$ partition function $\int_{|h| \leq \log^{\theta}(q)/2}|L(1/2+ih,\chi)|^2dh$ for typical Dirichlet characters modulo a large prime $q$ and $\theta \in (-1/2,0]$ motivated by a $q$-analogue of the Saksman–Webb conjectures. When $\theta <0$, we use Harper's randomisation argument to introduce explicit conditioning to recover moment upper bounds consistent with critical normalisation predicted there. As an application, we prove that for $q(1-o(1))$ Dirichlet characters modulo $q$, $\max_{|h| \leq 1/2}|L(1/2+ih,\chi)|\ll \frac{\log(q)}{(\log\log(q))^{3/4+o(1)}}$, establishing an upper bound matching the predictions of the $q$-analogue of the Fyodorov–Hiary–Keating conjectures up to second order.

We study rooted Gibbs-DLR measures in the directed polymer model on $\mathbb{Z}^2$ with an ergodic disorder distribution which satisfies an additional mild hypothesis. We prove that the set of extremal rooted Gibbs-DLR measures is closed and totally ordered, characterize extremality in terms of path coalescence, and show that each fully supported extremal rooted Gibbs measure canonically generates a globally consistent and coalescing family of extremal rooted Gibbs measures indexed by all lattice sites. These families are, moreover, totally ordered. Building on this structure, we prove strong existence and strong uniqueness of the associated Busemann process, together with an $L^1$ continuity theorem for the shift-covariant Busemann cocycles which is joint in the inverse temperature, the tilt parameter, and the random environment. This yields, as a corollary, in-probability continuity of the generated extremal Gibbs measures corresponding to directions of differentiability under bounded i.i.d. perturbations of the weights. In positive temperature, it shows in-probability convergence of the generated extremal Gibbs measures. At zero temperature, it also yields quenched subsequential large deviation principles for the corresponding positive-temperature rooted Gibbs-DLR measures on path space. The rate functions are determined by a zero-temperature Busemann cocycle and vanish precisely on the infinite geodesics generated by that cocycle.

Uniform stability is a classical tool for controlling the generalization error of a learning algorithm. Bousquet, Klochkov, and Zhivotovskiy (2020) showed that the problem can be reduced to a moment inequality for a sum of weakly interacting functions of independent random variables. Their bound contains an additional factor $\log n$, and they asked whether this factor can be removed. We answer this upper-bound question affirmatively. More specifically, let $Z=(Z_1,\ldots,Z_n)$ have independent coordinates and let $g_i(Z)$ satisfy $\mathbb E[g_i(Z)\mid Z_{-i}]=0, \ \left| \mathbb E[g_i(Z)\mid Z_i]\right|\le M, \ \text{for every } i = 1, \dots, n, $ where $Z_{-i}$ denotes all coordinates except $Z_i$. Assume additionally that changing any coordinate $Z_j$, $j\neq i$, changes $g_i$ by at most $\beta$, we prove that, for every $p\ge2$, for every $p\ge2$, $$ \left\| \sum_{i=1}^n g_i(Z)\right\|_p \le 16pn\beta+M\sqrt{2pn}. $$ This removes the $\log n$ factor from the previous bound and matches the lower bound of Bousquet, Klochkov, and Zhivotovskiy up to universal constants in the range covered by their construction. Our proof first establishes the required estimate on the Rademacher cube, then transfers it to arbitrary product distributions by a two-copy randomization argument.

Let $h>0$. For a complete and separable $\mathbb{R}$-tree $(T,d)$ equipped with a root $\rho$ and a finite Borel measure $\mu$, we define the $h$-mass-erased tree by removing from $T$ all fringe subtrees of mass less than $h$ and we equip it with a suitable measure such that the erasure operators $(\mathcal{E}_h)_{h\ge 0}$ form a semigroup that is continuous for the Gromov-weak topology. Then, we say that a sequence $\boldsymbol{\mu}_n=(T_n,d_n,\rho_n,\mu_n)$, $n\in\mathbb{N}$, converges in the sense of mass erasure if $(\mathcal{E}_h\boldsymbol{\mu}_n)_{n\in\mathbb{N}}$ converges Gromov-weakly for all $h\ge 0$. This notion of convergence is strictly weaker than Gromov-weak convergence and we establish criteria to relate the two notions. We define a distance function that metrizes convergence in the sense of mass erasure. By extending the notion of measured $\mathbb{R}$-trees to allow mass on the boundary (the far ends of infinite geodesics), we obtain a complete metric space. Next, we identify random trees of finite type (that is, discrete trees with edge lengths) satisfying the regenerative branching property as a specific class of measured (sub)critical GW forests. We then show that this class of trees is preserved by mass erasure and we compute the law of these mass-erased GW forests explicitly. Finally, we establish a limit theorem for these measured (sub)critical GW forests to converge to standard measured Lévy forests, i.e. those whose total mass has the same distribution as the total population of a continuous-state branching process. This includes cases with bounded variation by crucially using the convergence in the sense of mass erasure and it extends the cases studied previously.

We consider the Langevin diffusion $dX_t = - \beta \nabla V(X_t) dt + \sqrt{2} dB_t$ for a general nonnegative real-analytic potential $V$ and a large parameter $\beta$. In the large-$\beta$ limit the process is confined to the zero set of $V$, assuming that it starts there. We derive a candidate limiting evolution on the zero set. To do so, the zero set is partitioned into strata according to a measure of local codimension known as the local learning coefficient and its multiplicity. It is then shown that the Dirichlet form associated with $X$ converges in a certain sense to a hierarchy of Dirichlet forms corresponding to a stochastic evolution on the strata. This evolution is strongly biased toward higher-dimensional, or "more singular", strata. This result is motivated by a question from Watanabe's singular learning theory regarding the learning dynamics of overparameterized statistical models and the generalization puzzle in deep learning. The result suggests a mechanism for the observation that stochastic gradient methods tend to be biased toward singular solutions that generalize well.

The stabilising effect of multiplicative noise for stochastic differential equations, though counterintuitive, has been observed and investigated extensively in last decades. In practice, it is desirable to know if such stabilisation holds also for the discretised setting. In this paper, we address this problem by means of sharp upper and lower estimates for Lyapunov exponents of Milstein schemes for non-autonomous stochastic differential equations. These estimates provide precise large time behaviour in both almost sure and $p$-moment sense. In particular, our results show the preservation of stabilisation from the continuum setting to the discretised setting. One main idea of our analysis is to exploit the second order term concerning the stochastic noise from the Milstein scheme to obtain precise estimates for Taylor expansions of logarithmic and power functions.

Let $K$ be a symmetric convex body in $\mathbb{R}^d$ and let $f(K)$ denote the largest constant $c$ such that every finite collection of translates of $K$ contains a pairwise disjoint subcollection whose total volume is at least $c$ times the volume of the union of the original collection. The classical Vitali covering lemma gives $f(K)\geq3^{-d}$. In this paper, we establish two improvements. First, by a purely combinatorial argument, we prove that $$ f(K)\geq \frac{2}{3^d + 2^d} $$ for every symmetric convex body $K$. This improves the Vitali bound by a factor tending to $2$ as $d$ tends to infinity. Second, using a weighted hard-core model together with a weighted geometric estimate for intersections of Euclidean balls, we show that, for all sufficiently large $d$, $$ f(B^d)\geq \left( \log\frac{3}{1+\sqrt3} -O\left(\frac{\log d}{d}\right) \right)d\,3^{-d}, $$ where $B^d$ is the unit Euclidean ball in $\mathbb{R}^d$. Thus, the classical lower bound is improved by a factor of order $d$.

We study the self-intersection time of the non-backtracking random walk on connected undirected graphs. For every fixed $\Delta \geq 3$ we show that the expected self-intersection time is $O(\sqrt{n} \log n)$ on $n$-vertex graphs with minimum degree at least $3$ and maximum degree at most $\Delta$. For regular graphs with a uniform spectral gap, we improve this to $O(\sqrt{n})$. We also show an $\Omega(\sqrt{n})$ lower bound on a class of regular expanders. Our upper bound on the expected self-intersection time implies an improved mixing time bound on Glauber dynamics for the Ising model on $\Delta$-regular graphs at the tree uniqueness threshold.

We determine the finiteness boundary of the Novikov exponential moment for a one-dimensional constant-volatility mean-reverting diffusion. A localised change of measure cancels the squared drift and leaves a Brownian Feynman-Kac functional with potential $q/2$, where $q=-\lambda'$. If $q(\theta+y)\sim\kappa_\infty y^2$, the exact spectral boundary is $\kappa_\infty\sigma^2T^2=\pi^2$; for cubic drift it becomes $c\sigma^2T^2=\pi^2/3$, and equality is divergent. On the spectral equality surface, the first lower-order transition occurs at power $4/3$, where an explicit coefficient separates the two sides. For symmetric finite pure-power tails, exact tuning generates the recursion $\beta_n=1+3^{-(n+1)}$. We prove that this recursion gives a complete classification of the class. Each individual tail is decided after finitely many comparisons, but the required depth is unbounded: arbitrarily long common critical prefixes can lead to opposite outcomes. The drift-removing stochastic exponential nevertheless remains a true martingale; under the physical law it has no higher moments on the steep-drift class, while the reverse density is essentially bounded.

We provide a general ansatz for the paracontrolled approach introduced by Gubinelli, Imkeller, Perkowski for treating singular SPDEs. The ansatz proposed covers a large class of equations. It is described via decorated trees that encode its coefficients and its stochastic data. The main novelty is the recursive definition of the paracontrolled stochastic iterated integrals that involve a well-chosen combinatorial set of words. The paralinearisation is performed via a lift of iterated paraproducts to modelled distributions and the reconstruction theorem coming from Regularity Structures. We also provide a fixed point argument and the renormalised equation with this ansatz when one uses the preparation map formalism that encompasses the BPHZ renormsalition. The last main result is the convergence of the renormalised stochastic data via the BPHZ renormalisation via an adaptation of the spectral gap approach. One obtains in the end a general solution theory for parabolic singular SPDEs via the paracontrolled approach.

We consider discrete-time non-linear stochastic dynamical systems where the driving noise is not i.i.d. but an autoregressive process (“red noise”). Under a standard dissipativity condition, we prove geometrically fast convergence to a stationary distribution in total variation.

In this paper we provide Monte Carlo and deep neural network approximations for stochastic representations of solutions to linear elliptic partial differential equations with constant diffusion, drift and killing. Building on the modified Walk-on-Spheres algorithm of Beznea et al. (arXiv:2209.01432), we introduce Monte Carlo estimators that explicitly incorporate sampled random times arising in the analyzed stochastic representations. We establish uniform error bounds for these estimators and show that, under suitable assumptions, a prescribed approximation accuracy is achieved with sample complexities growing at most polynomially in both the inverse accuracy and the problem dimension. Furthermore, we prove a deep neural network approximation result for the stochastic representations. Assuming suitable neural network representations of the boundary data and the distance function to the boundary, we use the constructed Monte Carlo to design deep neural networks that approximate the representation uniformly with a number of parameters growing at most polynomially in the inverse accuracy and the problem dimension. These results extend previous complexity analyses to a broader class of elliptic equations involving drift and killing.

We study the discrepancy of balancing $n$ independent sample paths of fractional Brownian motion with Hurst exponent $H\in(0,1)$ on $[0,1]$, an infinite-dimensional analogue of balancing Gaussian vectors. We establish a phase transition at $H=1/2$: with high probability, the discrepancy is $\Omega(n^{1/2-H})$ and $\mathcal O(n^{1/2-H}(\log n)^{c(H)})$, where $c(H)=H+1/2$ if $H\geq 1/2$ and $c(H)=1/2$ otherwise. At the critical exponent $H=1/2$, we show that the discrepancy is $\Theta(1)$ with constant probability as $n\to\infty$. In this regime, we further characterize the geometry of the solution space by computing the expected number of local minima, establishing an overlap gap property near the existence threshold, and proving its absence at every diverging optimality threshold. We also give randomized polynomial-time algorithms that compute signings with discrepancy $\mathcal O(n^{1/2-H}\sqrt{\log n})$ for $H<1/2$, $\mathcal O((\log n)^{3/2})$ for $H=1/2$, and $\mathcal O(\sqrt{\log n})$ for $H>1/2$, with high probability. Our analysis combines a truncated balancing argument based on a wavelet representation of fractional Brownian motion with probabilistic methods.

In previous work, the density of the martingale limit in Schröder branching processes was expressed as a convergent double power-law series with oscillatory terms. The proof relied on two assumptions, one of which imposed a geometric restriction on the critical angle of the Julia set of the offspring generating function near $1$. In this paper, we show that both assumptions can be removed. We derive explicit bounds on the expansion coefficients, which imply locally uniform convergence of the double series. The coefficients decay exponentially in one summation index, with the rate explicitly determined by the critical angle, and super-exponentially in the other. Finally, we investigate the behavior of the critical angle and describe regimes in which it approaches its minimum. This analysis shows how the geometry of the Julia set influences the magnitude of the oscillatory corrections in the left-tail expansion.

A target moves between two sites according to a discrete-time Markov chain with a $2\times2$ transition matrix $M$. At each epoch one site is searched at positive cost, and a search may overlook a target that is present. Ross conjectured that an optimal policy is threshold in the posterior probability that the target is at site~1. MacPhee and Jordan proved the conjecture throughout the nonpositive-determinant ($\det M\le0$) regime and for part of the positive-determinant ($\det M>0$) regime, leaving the remaining cases open. We prove threshold optimality throughout the positive-determinant regime, completing Ross's conjecture for all parameter values.

We establish three averaging principles for distribution-dependent stochastic reaction–diffusion equations with rapidly oscillating coefficients on the torus $\mathbb T^d$, $d\le3$. First, solutions converge in mean square, uniformly on finite time intervals, to solutions of the averaged equation. Under a contraction condition, both the original and averaged equations admit unique bounded entire solutions whose mean-square distance vanishes uniformly for all $t\in\mathbb R$. At the level of probability laws, the original nonautonomous equation possesses a family of pullback attractors, whereas the averaged equation has a global attractor; the former converge upper-semicontinuously to the latter, uniformly over the coefficient hull. As an application, we present a class of stochastic reaction–diffusion models motivated by large-scale interacting systems.

Optimal transport and Gromov–Wasserstein distances are useful tools for comparing probability measures and metric measure spaces, but their balanced formulations force all mass to be matched. This constraint is often too strong for data with outliers, missing parts, or only partial overlap. In this paper, we develop entropic partial optimal transport for Gaussian mixture models and define a partial mixture Gromov–Wasserstein distance. For the finite entropic partial optimal transport problem, we prove the existence and uniqueness of the minimizer and establish quantitative large-penalty estimates. Moreover, the resulting entropic partial component couplings induce continuous partial transport plans through Gaussian optimal maps. We analyze their large-penalty and subsequent zero-entropy limits and construct the associated displacement interpolations and barycentric projection maps. In addition, by identifying each Gaussian mixture with a finite metric measure space of Gaussian components, we establish the metric property and large-penalty limit of the partial mixture Gromov–Wasserstein distance. Finally, numerical experiments on synthetic Gaussian mixtures and point clouds illustrate the effects of the penalty and entropic regularization and the robustness of partial matching to outliers.

Sample $n$ i.i.d. points from a triangle, according to some continuous density function. Given two vertices $A,B$ of the triangle, what is the maximum number of samples that form a convex chain with initial point $A$ and terminal point $B$? We show that to leading order, the answer is $cn^{1/3}$, generalizing a result of Ambrus and Bárány that considered uniformly distributed points. Furthermore, we express the constant $c$ using a variational formula whose maximizer (if unique) gives the limiting curve formed by the longest convex chain. By comparison, for $n$ i.i.d. samples from the unit square, the length of the longest monotone chain is asymptotically $c'n^{1/2}$. Despite the difference in scale, our formula is nicely connected to one established for $c'$ by Deuschel and Zeitouni.

We study a restarting Josephus process in which the participants retain their linear order and counting restarts at the current leftmost survivor after every deletion. For step size $m$, put $q=m-1$, and let $F_n(q)$ denote the initial position of the survivor. Reverse insertion gives $F_1(q)=1$ and $F_k(q)=F_{k-1}(q)+\mathbf{1}_{\{q\bmod k<F_{k-1}(q)\}}$. Writing $L_n=\operatorname{lcm}(1,\ldots,n)$, we establish three results for the compatible residue system in this recurrence. First, the full period group of $F_n$ is exactly $L_n\mathbb{Z}$. Second, $F_n$ is surjective onto $\{1,\ldots,n\}$. The proof is constructive and unconditional but computer-assisted: a Chinese-remainder construction and explicit prime estimates reduce it to a finite exact certificate. Third, if $\widetilde Q_n$ is uniform modulo $L_n$, then $(F_n(\widetilde Q_n)-1)/(n-1)$ converges to a symmetric, nondegenerate law on $[0,1]$. A common Haar coupling yields almost-sure and $L^r$ convergence for every $1\le r<\infty$, together with an $O(n^{-1/4})$ bound in $W_1$. Logarithmic boundary-mass estimates rule out every symmetric beta law. We also formulate endpoint dominance as an open problem, prove strict dominance over the two nearest internal positions for every $n\ge4$, exclude prime levels as minimal counterexamples, and verify the claim exactly through $n=49$.

We establish a Schauder estimate for a nonlocal Cauchy problem with drift. The leading operator is the generator of a non-degenerate $\alpha$-stable process with $\alpha\in(0,1)$, and the drift is $\beta$-Hölder continuous with $\beta \in (1-\alpha,1)$. The proof relies on a refined conic Littlewood–Paley decomposition and a one-dimensional one-sided dyadic maximum principle.

We consider the probability that a discrete random matrix $M_n(\xi)$ is strongly non-singular, meaning all its leading principal submatrices are non-singular. This property is equivalent to the existence of an LU factorization. We show that for any discrete random variable $\xi$ with finite support and $|\xi|_\infty < 1$, there is a constant probability that $M_n(\xi)$ is strongly non-singular with a growth factor bounded by $n^{5/2+\delta}$. Furthermore, we provide a tight asymptotic lower bound for this probability as $|\xi|_\infty \to 0$. Finally, we provide exact counts for strongly non-singular binary matrices up to $n=9$ and use these to derive improved upper bounds for the Bernoulli case.

In this paper, we consider a Bernoulli random graph~\(G\) on~\(n\) vertices with non-uniform edge probabilities, where each vertex has an independent mark and each edge is equipped with an independent positive weight. The cost of an edge depends on the weight as well the marks of the endvertices and we estimate the growth of the maximum and minimum cost of a spanning tree containing all the vertices. For edge weights with heavy tails and vertex marks distributed uniformly in the unit square, we obtain a phase transition in terms of the tail decay exponent~\(s:\) If~\(s\) is large, then the maximum cost is essentially determined by the vertex locations and if~\(s\) is small, then the edge weights crucially influence the maximum cost. We derive a similar result for minimum cost spanning trees and use martingale difference based methods to establish the~\(L^2-\)convergence of the extremal cost, appropriately scaled and centred.

Cells often estimate chemical concentrations from only a few diffusing molecules, whose stochastic motion limits sensing precision. We consider a perfect monitoring instrument that records the instantaneous molecular density throughout a finite region without perturbing the concentration field or distinguishing molecular identities. The standard Berg-Purcell estimator weights all positions uniformly. Here we derive the optimal spatial weighting within a large class of unbiased estimators for both concentration and gradient sensing. Variance minimization maps to an electrostatic problem. Surprisingly, although the instrument monitors the entire volume, the optimal estimator assigns all weight to its boundary, reducing the uncertainty in both concentration and gradient sensing. We extend the results to arbitrary geometries and spatial dimensions.

We prove a sharp spatial regularity theorem for the Itô and Stratonovich cross integrals of continuous semimartingales in separable Hilbert spaces. Without global moment assumptions, both integrals admit versions that are almost surely jointly continuous in the two time variables, with values in the little weak-trace ideal. This regularity is optimal even for Wiener processes with deterministic trace-one covariance. Given any positive sequence tending to zero, we construct such a process for which the singular values of its Lévy area, multiplied by their indices, tend to zero but have termwise ratios to the prescribed sequence tending to infinity almost surely. The same property holds simultaneously for both self-integrals. The upper bound follows from a rank-one cancellation in Itô's formula for a determinant, together with finite-rank approximation. For the lower bound, conditional Gaussian estimates and orthogonal time functions yield finite-dimensional spectral bounds, which are combined through a trace-one covariance to obtain lower bounds for all sufficiently large indices.

We study the distribution of the two-replica overlap $R_{1,2}$ in the Ising and spherical Sherrington-Kirkpatrick models at the critical inverse temperature $\beta = 1$. Our main result shows that in both models, $R_{1,2}$ has scale $N^{-1/3}$, and the quenched distribution of $N^{1/3} R_{1,2}$ converges to an explicit random probability measure defined in terms of the reflected $\mathrm{Airy}_1$ point process. As a consequence, we characterize the limiting value of $N^{2/3} \mathbb{E} \langle R_{1,2}^2 \rangle$, answering a question of Talagrand \cite{talagrand2011mean2}. For the spherical SK model, we obtain the limit by representing the Gibbs measure as an anisotropic Gaussian on $\mathbb{R}^N$ conditioned to have norm $\sqrt{N}$, and then passing to the $\mathrm{Airy}_1$ scaling limit at the GOE spectral edge. For the Ising SK model, the proof is based on a sphere-to-cube comparison principle showing that the quenched distributions of $N^{1/3} R_{1,2}$ under the spherical and Ising Gibbs measures asymptotically coincide. This paper is a companion to \cite{du2026fluctuations}, where we introduced a related comparison principle to identify the limiting fluctuations of the SK free energy. Most of the arguments in this paper were generated using GPT-5.6 Pro, with the aim of exploring further consequences of the ideas developed in that work.

We study the conditionally resampled sliding-window count kernel associated with the empirical counts of length-$n$ windows from a stationary finite-state reversible Markov chain. Although the resulting count process is generally not Markov, its stationary one-step conditional law defines a genuine Markov kernel. For every fixed strictly positive reversible kernel \(P\) on a finite state space, we present a Poincaré inequality for the induced count kernel $\tP_n$ of length $n$. In other words, we derive the lower bound of the spectral gap $\Gap(\tP_n)$ of $\tP_n$ as \[ \Gap(\tP_n)\ge \frac{c(P)}{n}, \] where \(c(P)>0\) depends only on \(P\). The proof combines a martingale oscillation inequality for the stationary path law with a direct comparison of coordinate oscillations to the Dirichlet form of the count kernel. A linear statistic of the count vector gives the matching \(O(1/n)\) upper bound, so for every fixed strictly positive reversible \(P\) one has \(\Gap(\tP_n)=\Theta_P(1/n)\). The resulting count-space Poincaré inequality yields a local-to-global variance bound for finite-window count statistics and, together with a general matrix-concentration principle, operator-norm concentration for matrix-valued empirical averages.

We establish counting and sampling analogues of the Lovász Local Lemma: we give efficient algorithms for approximately counting and exactly sampling satisfying assignments of general constraint satisfaction problems (CSPs) in the local lemma regime $$4 \mathrm{e} p (D+1)^2\leq 1, $$ where $p$ is the maximum constraint violation probability and $D$ is the maximum dependency degree. This condition is tight up to constant factors under $\mathbf{NP}\neq\mathbf{RP}$, matching known hardness bounds for counting and sampling in natural subclasses of CSPs. Our key ingredient is a novel $2$-tree expansion for constraint marginal probabilities that exhibits exponential decay of correlations throughout this regime. This expansion yields deterministic polynomial-time approximate counting for fixed local parameters, randomized approximate counting with quadratic cost, and exact sampling in expected near-linear time when the local parameters are fixed.

The random-cluster model with cluster weight $0<q<1$ is expected to exhibit negative dependence, but without FKG even pairwise negative correlation remains open on general graphs. We study the model on the infinite $\Delta$-regular tree with wired boundary conditions. Write $\widehat p:=p/(p+q(1-p))$ and $p_{\mathsf c}:=q/(\Delta+q-2)$. Classical results identify the product wired state for $p\le p_{\mathsf c}$ and construct a percolative all-wired limit for $p>p_{\mathsf c}$. We prove that the supercritical wired DLR specification has a unique Gibbs measure, namely this all-wired limit. Consequently, the wired DLR phase diagram is complete: the unique measure is Bernoulli bond percolation with parameter $\widehat p$ for $p\le p_{\mathsf c}$, while it percolates for $p>p_{\mathsf c}$. We also establish negative dependence across wired branches. On a finite wired tree, the vector of branch-connectivity indicators satisfies conditional negative association under positive external fields (CNA+). Hence bounded increasing observables supported on disjoint collections of branches incident to a common vertex have nonpositive covariance. The same inequality holds in the unique infinite-volume wired measure for every $p$, with equality for $p\le p_{\mathsf c}$.

In this paper, we consider a random geometric graph (RGG)~\(G\) formed by~\(n\) vertices distributed uniformly in the unit square~\(S\) on the plane and equip each edge of~\(G\) with an independent weight. We assume that the adjacency distance between vertices is larger than the connectivity threshold and estimate the maximum weight of a path connecting two fixed points~\(O_1\) and~\(O_2\) in~\(S,\) using edges of~\(G\) that satisfy length and weight constraints. Our strategy is to first divide the space between~\(O_1\) and~\(O_2\) into small squares and identify nice squares containing heavy edges. We then use an iterative stitching procedure to connect these heavy edges and estimate the weight of the resulting path~\(P.\) Finally, we invoke a multi-level scaling procedure along with weight segmentation to establish an upper bound for the maximum weight of any path between~\(O_1\) and~\(O_2\) and thereby demonstrate the near-optimality of~\(P.\) We also illustrate our results using examples involving edge weights satisfying power law and exponential decay.