CS Paper Radar

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

Haoran Wang

cs.DS math.PR ·submitted 2026-11-15 06:17 UTC · v1
theory

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$.

Closest papers

Nearest neighbours by meaning across the whole index.

On the Pseudo-Mixing of Kac's Walk

cs.CR math.PRcs.LG ·2026-08-18 ·Natesh S. Pillai, Aaron Smith, Vinod Vaikuntanathan
theoryhighly cited similarity 0.63
Abstract · 48 pages

Motivated by a conjecture of Vaikuntanathan and Zamir, we study the pseudo-mixing of Kac's walk on $\mathrm{SO}(n)$: whether short trajectories are indistinguishable from Haar measure by low-complexity tests. We prove that the first $k$ columns mix in Wasserstein distance in $O(n(k+\log n)\log n)$ steps for fixed accuracy, resolving a conjecture of Oliveira. Combining this with a representation-theoretic variance bound, we show that if $T=ω(nk(k+\log n)\log n)$, then every degree-$k$ polynomial normalized to have unit Haar variance has expectation under the $T$-step law within $o(1)$ of its Haar expectation. As an application, we show that this pseudo-mixing estimate can be used to prove the effectiveness of a fast Johnson--Lindenstrauss transform with the usual target dimension.

0.42

Optimal mixing of the systematic scan dynamics via approximate tensorization of entropy

cs.DM math.PR ·2026-09-04 ·Antonio Blanca, Md Tahmidur Rafid
similarity 0.63
Abstract

We study the mixing time of the systematic scan dynamics for high-dimensional discrete distributions. This Markov chain updates coordinates sequentially according to a fixed predetermined order, in contrast to the Glauber dynamics that updates coordinates selected uniformly at random. The systematic scan is often favored in practice because it exhibits strong empirical performance, but its theoretical analysis remains far less developed than that of Glauber dynamics. We take a step toward addressing this imbalance by showing that two standard functional notions of weak dependence between the coordinates of the distribution provide strong convergence guarantees for the systematic scan dynamics. First, we show that approximate tensorization of entropy implies optimal $O(\log n)$ mixing time for every scan order under standard marginal, connectivity, and bounded interaction degree assumptions about the distribution. Second, we show that approximate tensorization of variance yields a constant-factor contraction of the variance functional per scan, which in turn implies an optimal $O(1)$ relaxation time for the natural additive and multiplicative reversibilizations of the systematic scan dynamics. Compared with our entropy result, the variance bound improves the dependence on the maximum interaction degree from exponential to quadratic and requires weaker assumptions on the distribution. As concrete applications of our results, we establish optimal $O(\log n)$ mixing of the systematic scan dynamics for bounded-degree antiferromagnetic two-spin systems in the tree-uniqueness region and for the ferromagnetic $q$-state Potts model on square boxes in $\mathbb{Z}^2$ throughout its subcritical regime.

0.28

Optimal Marginal Mixing for Transvection-Based Trapdoored Matrices over Large Fields

cs.CR ·2026-11-03 ·Mark Braverman, Aayush Jain, Stephen Newman
hot direction similarity 0.63
Abstract

\emph{Trapdoored matrices} are pseudorandom matrices admitting a fast matrix-vector multiplication algorithm given the secret key. We study a candidate family of such matrices: matrices generated by short random \emph{transvection walks} on \(\mathrm{SL}_n(\mathbb{F}_q)\), whose steps are given by adding a random multiple of a random row of the current state to another. We show that the worst-case time for any nonempty set \(\mathcal{S}\subseteq [n]\times[n]\) of matrix entries to come within TV distance \(\varepsilon\leq \frac{1}{4}\) of its stationary marginal under this walk is \(Θ(|\mathcal{S}|+n\log(n/\varepsilon))\), uniformly over all \(\mathcal{S}\) and \(q\geq Q_\mathrm{all}(n)\). This is asymptotically optimal, and resolves open questions about the mixing times of transvection walks. We derive concrete upper and lower bounds for \(n\geq 256\). Surprisingly, our bounds also hold conditioned on the row-pair structure of the walk, except on a fraction at most \(\varepsilon\) of such structures. This implies that these walks may be pseudorandom even after conditioning on the row-pair structure, and therefore that trapdoored matrices built with these walks may be universal. Assuming the conjectured structure-conditioned pseudorandomness of short walks, we exhibit highly efficient, highly parallelizable, and universal trapdoored matrices over \(\mathrm{SL}_n(\mathbb{F}_q)\), \(\mathrm{GL}_n(\mathbb{F}_q)\), and \(\mathbb{F}_q^{n\times n}\). The families over \(\mathrm{SL}_n(\mathbb{F}_q)\) and \(\mathrm{GL}_n(\mathbb{F}_q)\) admit equally efficient trapdoors for their inverses, making them the first to do so for finite-field trapdoored matrices. We discuss attacks, analyzing one in detail, and lay out directions for further investigation.

0.35

On two proofs of $d^2$ mixing of weighted Dikin walks

cs.DS cs.LGmath.OCmath.PR+1 ·2026-08-28 ·Yuansi Chen, Yunbum Kook
similarity 0.62
Abstract · 36 pages. AI disclosure included

We study the mixing time of weighted Dikin walks for sampling from exponential distributions on polytopes and truncated positive-semidefinite (PSD) cones. Our first result gives a general total-variation mixing bound under strong self-concordance, $\barν$-symmetry, and mixed-trace regularity on the local metric. The key idea is to control the Metropolis--Hastings acceptance probability on a high-probability region rather than at every point. Applying this framework to the Lee--Sidford, Lewis-weight, and John metrics yields an $\widetilde O(d^2)$ mixing bound for sampling from polytopes, while applying it to a hybrid barrier yields an $\widetilde O(d^4)$ mixing bound for sampling from truncated PSD cones. Our second result establishes stronger $χ^2$-divergence guarantees and pointwise acceptance control using a new fourth-order bootstrap condition. For a suitably scaled Lee--Sidford metric, this yields an $\widetilde O(d^2)$ mixing bound in $χ^2$-divergence, improving on the previous $\widetilde O(d^{9/4})$ bound.

0.09

Constant-Factor Matching-Size Estimation in Random-Order Streams

cs.DS ·2026-11-16 ·Alireza Farhadi, Mohammad Hajiaghayi, Morteza Monemizadeh
similarity 0.62
Abstract

We give a one-pass algorithm that estimates the maximum matching size of an arbitrary simple graph within a constant factor using $O(\log^2 n)$ bits of space. The edges arrive exactly once in uniformly random order. The algorithm succeeds with probability at least $2/3$, does not require the number of edges in advance, and has worst-case total running time $O((m+1)\log(n+2))$ on a word RAM. Kapralov, Khanna, and Sudan (SODA 2014) obtained a polylogarithmic approximation in polylogarithmic space. Kapralov, Mitrović, Norouzi-Fard, and Tardos (SODA 2020) subsequently gave a constant-factor approximation from independent uniform edge samples and an $O(\log^2 n)$-approximation in random order. We obtain a constant factor in the latter model with the same $O(\log^2 n)$ space bound. The main ingredient is a comparison between the memory states of a recursive sampling algorithm under sampling with and without replacement. We account jointly for the sampled edges retained by the recursion and the positions at which they arrived. Randomized thresholds limit the additional information stored in numerical counters. A bound on the expected work of the entire recursion then removes the loss from its logarithmic depth. The resulting estimator repeatedly improves a coarse estimate while storing only one recursion stack.

0.12

Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs

cs.DS math.PR ·2026-09-11 ·Zhidan Li, Kuan Yang
similarity 0.62
Abstract · A revised version

We develop a framework for deterministic approximate counting of multi-spin systems beyond bounded-degree graphs. The algorithm recursively constructs rational polytopes containing the true marginal vectors and uses linear-fractional programming to obtain certified bounds on marginal ratios. For positive interactions on graphs of polynomial connective constant $D$, we establish strong spatial mixing whenever $Dc<1$, where $c$ bounds the Birkhoff contraction coefficients of the interactions. Under the same condition, we also give a deterministic fully polynomial-time approximation scheme (\textbf{FPTAS}) for the partition function. We further extend the framework to proper colorings of sparse Erdős-Rényi random graphs using recursion on permissive blocks. For every fixed $η\in(0,1)$, sufficiently large fixed $d$, and fixed integer $q\ge(2+η)d$, we obtain an \textbf{FPTAS} for counting proper $q$-colorings of $G\sim\mathcal G(n,d/n)$ with high probability over $G$. This improves the leading constant $3$ in the earlier counting guarantee of Yin and Zhang (APPROX/RANDOM, 2016) to $2$, and asymptotically matches the spatial mixing regime established by Yin (ICALP, 2014).

0.26

A subquadratic upper bound for the mixing time of the Thorp shuffle

cs.DS math.PR ·2026-10-03 ·Yunjiang Jiang
theory similarity 0.62
Abstract · 31 pages

Let $n=2^d$. We prove that the worst-start total-variation mixing time of the full labelled Thorp shuffle satisfies, for every fixed $0<\varepsilon<1$, \[ t_{\mathrm{mix}}(\varepsilon) \le C_* d^{5/3}+O_\varepsilon\!\left(d^{4/3}\log(d+2)\right), \qquad C_*=5.1536951454\ldots . \] Time is measured in ordinary Thorp shuffles. This improves the previously published full-deck upper bound $O(d^3)$ of Morris. The geometric starting point is elementary: label the $n=2^d$ positions by binary strings. One physical Thorp shuffle is a random swap layer on one coordinate matching of the $d$-dimensional cube, followed by a deterministic cyclic rotation of the coordinates. In a rotating frame that deterministic rotation disappears, so $d$ successive physical shuffles become one \emph{sweep}: one independent random swap layer in each coordinate direction. The proof then combines five ingredients. First, a collision-graph representation and negative dependence give pointwise smoothing for ordered marked cards. Second, an entropy argument is sharpened by moving an endpoint moment up to the critical exponent $β_c=\log_2(3/2)$, yielding an entropy-preparation clock $s^2/(2\log(3/2))+O(s\log s)$. Third, exact multiplicities in the ordered $h$-tuple permutation representation amplify marked-card bounds into Fourier operator and energy estimates on low representation levels. Fourth, entropy truncation produces a positive mixture whose regular component retains the marked-card budget. Finally, only two long blocks need this entropy regularization: a shorter third block is used solely for additional low-level smoothing. Optimizing the three block lengths gives the constant above.

0.57

Shared Randomness and Parallel Rounds in Permutation Sampling

cs.IT cs.DS ·2026-10-31 ·Haoxiang Huang
similarity 0.62
Abstract

We study the shared randomness needed to sample a uniform permutation in parallel output rounds. Coordinates committed in the same round are independent conditional on the complete history and the current shared choice. Previous outputs are public; local computation and private randomness are free. We charge each shared choice by the logarithm of its conditional support size and sum these costs along the worst execution path. At every fixed round density $ρ\in(0,1)$, the optimal limiting total-variation error under any $o(n)$ shared budget matches the conditional-marginal optimum, even with arbitrary local kernels and adaptive coordination. A fixed improvement requires linear cost. For exact sampling in $R=Θ(n)$ rounds, the optimum is $nΦ(R/n)+O(\log n)$, where $Φ$ linearly interpolates $Φ(1/q)=\log q$. A protocol attaining this rate uses an initial seed and at most one further binary shared choice. When $\lceil n/2\rceil\le R\le n$, the finite optimum is $\log\binom{2(n-R)}{n-R}$, attained by an initial seed alone. The approximate converse uses an entropy inequality for sparse injections to control overlap with the target. The exact construction reuses randomness retained in a shared label partition after the first-stage outputs are exposed.

0.22