Papers for

randomized algorithm developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Mixing time bounds connect quantum and classical random walks

A Tale of Two Walks: Kipnis, Marchioro and Presutti Meet Kac in a Quantum World

Abstract: We reveal an unexpected connection between the parallel Kac's walk and the Kipnis-Marchioro-Presutti (KMP) process. The twirling channel induced by the parallel Kac's walk on the symmetric subspace is exactly encoded by a classical Markov chain on partitions, which lifts to a parallel KMP process on complete graphs. This correspondence reduces the analysis of the twirling channel to the mixing of the parallel KMP process. We prove that $O(\log d+\log(1/\varepsilon))$ repetitions suffice to approximate Haar twirling on the symmetric subspace of $(\mathbb C^d)^{\otimes t}$ to error $\varepsilon$, uniformly in the number of copies $t$. For the standard KMP process on general graphs, we prove a mixing-time analogue of Aldous's conjecture: at fixed accuracy, the mixing time of the $t$-particle process is at most a constant times the single-particle mixing time multiplied by the logarithm of the number of vertices, uniformly in $t$. As an application, we improve the total variation mixing-time bound for coordinate hit-and-run on the $n$-dimensional standard simplex from $\widetilde O(n^3)$ (Kook and Vempala, 2026) to $\widetilde O(n)$, while removing the dependence on the initial distribution. Our main technical contribution is conditional product structure for both parallel and standard KMP processes. Conditioned on suitable auxiliary randomness, the labeled particles evolve independently. Combining this structure with an exact coupling yields mixing bounds uniform in the number of particles for both unlabeled KMP models. These bounds are sharp up to logarithmic factors and imply rapid convergence of the parallel Kac twirling channel on the symmetric subspace.

Tue 29 SeptData Structures and Algorithms
The gist
The paper finds a surprising link between two types of random processes: a quantum-inspired walk and a classical model used to describe particle movement. The researchers show that understanding one process helps analyze the other, making it easier to grasp how quickly these systems reach a balanced state. They improved mathematical bounds on how fast this balancing happens, especially in complex settings like high-dimensional spaces. This work could help in areas that rely on random sampling or mixing techniques.
Open → 2609.38044v1