More Efficient Approximate k-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities
Lucas Gretta, William He, Angelos Pelecanos
Abstract
We prove that the permutation computed by a reversible circuit with Õ (nk · log(1/ε )) random 3-bit gates is ε-approximately k-wise independent. Our bound improves on currently known bounds in the regime when the approximation error ε is not too small and is optimal up to logarithmic factors when ε is a constant. We obtain our results by analyzing the log-Sobolev constants of appropriate Markov chains rather than their spectral gaps.
Ask Lune
Know where this paper stands in minutes, not an afternoon.
Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
its abstract · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers2
Related papers
- Incompressibility and Spectral Gaps of Random CircuitsChi-Fang Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu et al.FOCS 2025 · 5 citations
- Optimal mixing of the down-up walk on independent sets of a given sizeVishesh Jain, Marcus Michelen, Huy Tuan Pham, Thuy-Duong VuongFOCS 2023 · 3 citations
- How Fast Does the Inverse Walk Approximate a Random Permutation?Vishesh Jain, Tianren Liu, Clayton Mizgerd, Angelos Pelecanos et al.CRYPTO 2026 · 1 citation
- Layout Graphs, Random Walks and the t-Wise Independence of SPN Block CiphersTianren Liu, Angelos Pelecanos, Stefano Tessaro, Vinod VaikuntanathanCRYPTO 2023 · 9 citations
- Entropic independence: optimal mixing of down-up random walksNima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham et al.STOC 2022 · 21 citations
