CS Paper Radar

A Randomized Approximation Algorithm for Doubly Free-Boundary Macdonald Processes

Zhongyang Li

cs.DM math.PRcs.DSmath.COstat.CO ·submitted 2026-10-13 16:48 UTC · v1
theory

Abstract

We construct an approximate sampler for finite doubly free-boundary Macdonald rail-yard processes with Macdonald, boundary, and edge parameters in $(0,1)$. The construction allows arbitrary finite sequences of additions and removals of horizontal or vertical strips and all four boundary types. It reverses a finite commutation--reflection history from a partition sequence whose entries are equal, with the common partition weighted by both boundaries. We derive local reconstruction kernels from the skew Cauchy, Littlewood, and branching identities. Bulk and boundary updates combine integer increments with conditional shape sampling at a prescribed size; same-sign swaps use finite conditional resampling. For $K$ reflection periods and an initial partition-size cutoff $M$, the algorithm terminates almost surely and samples the resulting approximating law exactly. We prove total variation convergence to the target process as $K,M\to\infty$ and give explicit bounds for both truncation errors, decaying geometrically in the cutoffs for fixed input parameters. Under fixed parameter bounds, we also bound the expected operation count of direct enumeration in a unit-cost model. We further construct an exact rejection sampler for the initial partition law without a size cutoff or evaluation of its normalizing constant. Using this sampler removes the size-truncation error, leaving only the error from the finite reflection history.

Closest papers

Nearest neighbours by meaning across the whole index.

Displacement Moments and Path-Terminal Separation in Brownian Interpolant Sampling

cs.LG math.PR ·2026-10-27 ·Zhong Han
theory similarity 0.58
Abstract · 51 pages, 2 figures, including an 8-page main text. Revised exposition and streamlined appendices

We prove early-stopped, target-to-output KL guarantees for Brownian interpolant Euler sampling from the true source under arbitrary Borel couplings, even with nonintegrable endpoints. At fixed stopping time and noise level, a fourth displacement moment yields an $O(N^{-1})$ discretization term. A second moment suffices for fixed-law convergence with grid refinement and vanishing drift error. For one fixed coupling with no displacement moment above two, the original and comparison paths have KL of orders one and $1/\log N$ relative to the exact-drift Euler path. On the same geometric grid, terminal KL is at most $C/N^2$. The path decomposition identifies the information about the source discarded by Markov projection. When the original bridge is Markov, current-state Euler sampling has an $O((M_2+d)/N)$ discretization term. We prove expected stopped-output KL consistency for a learner trained on iid endpoint pairs with fresh true-source initialization. In a spatial image control, iterative sampling has worse fair energy scores than direct prediction with resampled residuals. Uniform terminal rates for general second-moment couplings remain open.

0.29

Optimal mixing of random-to-random shuffling on linear extensions

cs.DS math.PR ·2026-11-15 ·Haoran Wang
theory similarity 0.57
Abstract

Uniform sampling of linear extensions is a basic problem in randomized algorithms and the study of finite posets. We prove that the random-to-random shuffle of Ayyer, Schilling, and Thiéry mixes in $O(n\log n+n\log(1/\varepsilon))$ steps on every $n$-element poset, establishing their conjectured mixing order. With constant-time order queries, this gives an $\varepsilon$-approximate uniform sampler using $O(n^2(\log n+\log(1/\varepsilon)))$ elementary operations after preprocessing. The proof establishes relative-entropy contraction by a factor $1-1/n$ for the promotion half-step. Consequently, the uniform extended-promotion chain has the same mixing order. We represent complete promotion scans as reflected coordinate paths in the order polytope and prove that a convex potential with gradients in the same polytope has diagonal Hessian mass at most one along each path. Applying this estimate to an optimal transport potential yields a sharp entropy factorization for every finite-entropy input. Linearization also gives the spectral-gap lower bound $(n+1)/n^2$.

0.32

Approximating #BIS in $\exp(\widetilde O(n^{1/3}))$ Time

cs.DS ·2026-11-04 ·Jingcheng Liu, Yitong Yin
similarity 0.56
Abstract

We give randomized algorithms for approximately counting and nearly uniformly sampling independent sets in arbitrary bipartite graphs (#BIS). At fixed accuracy, both algorithms run in $\exp(O(n^{1/3}\log^{4/3}n))$ time on $n$-vertex graphs. More generally, the same running-time dependence on the number of variables holds for approximate counting and sampling with efficiently evaluable positive log-supermodular weights on Boolean variables. A weighted Sinclair-Jerrum walk on the self-reduction tree reduces these tasks to coarse lower estimates of residual log-partition functions. We obtain these estimates by optimizing a concave relaxation of an exact variational principle on the tree; threshold smoothing certifies that the low-degree search suffices.

0.29

An FPRAS for Antiferromagnetic Ising Models on Random Regular Bipartite Graphs

cs.DS math.PR ·2026-08-19 ·Zhidan Li, Kuan Yang
similarity 0.56
Abstract

We design randomized approximation schemes for the partition function of antiferromagnetic Ising models with uniform external field on random regular bipartite graphs. Our algorithm generalizes the approach of Kocurek, Oveis Gharan and Tjowasi (arXiv, 2026) for hard-core models on the same random graph model beyond the uniqueness threshold. We show that, as long as $λ$ is upper bounded by a constant and $λ(1 - β) \lesssim Δ^{-1/2}$, an efficient randomized algorithm approximates the partition function with high probability. The algorithm first truncates configurations that are large on either side of the bipartition and then samples from Gibbs distributions conditioned on fixed sizes on one or both sides. To choose an optimal truncation bound, we establish concentration properties of the Gibbs distribution on random regular bipartite graphs. Then we apply high-dimensional expansion and prove trickle-down theorems to obtain fast samplers for the conditioned distributions.

0.18

Mixing Times of Switch Chains via High-Dimensional Expansion

cs.DM math.PRmath.CO ·2026-10-07 ·Sawyer Jack Robertson
similarity 0.55
Abstract · 52 pages, 3 figures

The switch chain is a Markov chain defined on the set of labelled realizations of a given graphical degree sequence. At each step, a pair of vertex-disjoint edges is chosen at random and the process attempts to replace them with a uniformly chosen perfect matching of the same four vertices, rejecting any proposal that would create a multiple edge. The resulting process is reversible with respect to the uniform distribution on all realizations. We investigate the mixing time of this chain by viewing realizations as the facets of a simplicial complex and studying a variant of the original process called the simplicial switch chain, which we analyze using tools from the theory of high-dimensional expansion. Our technical contributions include a proof that links of faces of sufficiently high codimension are strong spectral expanders and a comparison between the Dirichlet energies of large block updates and two-edge updates. Our main result is an $O(Δ^{2}m\log m)$ bound on the mixing time of both simplicial and classical switch chains whenever $m\ge CΔ^{8}$, where $m$ is the number of edges, $Δ$ is the maximum prescribed degree, and $C>0$ is an absolute constant. For sequences on $n$ vertices with fixed maximum degree, this proves that the chain mixes in $O(n\log n)$ steps, resolving a longstanding conjecture of Cooper, Dyer, and Greenhill and extending its conclusion to irregular degree sequences.

0.22

Bounded Relative Boundary Implies Narrow DNF Approximation

cs.CC cs.DM ·2026-08-31 ·Chenghua Liu, Boning Meng
theory similarity 0.55
Abstract · 13 pages; proof and exposition revised, Lean repository linked

We prove Friedgut's conjecture (J. Amer. Math. Soc. 12 (1999)) that every increasing family in the $p$-biased discrete cube with bounded relative boundary can be approximated arbitrarily well by one whose minimal elements have size bounded independently of the dimension and the bias. For $0<p\le 1/2$, every increasing Boolean function with total resampling influence at most $K$ is $\varepsilon$-close under $μ_p^n$ to a monotone DNF of width $\exp(O((K+1)^2/\varepsilon^2))$, from which the full conjecture follows for all $p\in(0,1)$. We build on Hatami's pseudo-junta theorem (Ann. of Math. 176 (2012)), whose approximator need not be increasing. Our randomized shifts produce an increasing approximator that is measurable with respect to a controlled refinement of Hatami's adaptive partition. Retaining only short positive certificates yields the desired narrow DNF.

0.35

Efficient Posterior Sampling for $\mathbb Z_2$ Synchronization

cs.DS math.PRmath.ST ·2026-10-06 ·Zhangsong Li
similarity 0.55
Abstract · 41 pages

Consider the $\mathbb Z_2$ synchronization problem \[ \boldsymbol{Y} = \fracλ{\sqrt n} θθ^{\top} + \boldsymbol{Z}, \] where $θ$ 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 $λ>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.

0.32

Sampling and Curvature in First-Exit Comparisons for Momentum SGD

cs.LG ·2026-10-18 ·Haiyi Li
similarity 0.54
Abstract · 84 pages, including references and appendices

First-exit prediction for momentum SGD depends on sampling information that pointwise gradient laws omit. Strongly convex finite pools with identical pointwise laws and matched iid momentum dynamics can have different reshuffled exits; even analytic pools with uniformly close pointwise laws can have separated exit probabilities. For persistent sampling in one dimension, we establish an explicit $O(h)$ mean-exit comparison with a finite-rate switching process under nonvanishing component velocities and step-size conditions; iid sampling instead averages to an ODE. Retaining realized minibatches and sampled curvature yields finite-window exit brackets beyond this regime. In 32 trained ridge-logistic runs, 29 meet prespecified targets with rounding-certified brackets; an enclosure control explains most of the width advantage. Exact-real certificates establish finite means at the original tested radii for three ResNet-18 checkpoints and give local finite-mean conditions for tanh and ViT networks; their upper bounds remain loose, and original-radius ViT mean guarantees remain unresolved despite 128 fresh continuation paths. A two-network replication gives 32/32 successful seeds in each of four finite-path persistence comparisons. Independent equal-length controls retain slower exits after refresh resets than without resets, but the refresh-versus-random ordering reverses with update length at both networks. These interventions do not causally decompose raw momentum SGD. Neural step-size scaling does not validate the switching limit.

0.31