Lune

SODA2025Top-tier venue

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.

Questions to start from

Lune can draw on

its abstract · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Efficiently Batching Unambiguous Interactive Proofs cites Pseudorandomness Properties of Random Reversible Circuits
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. Pseudorandomness Properties of Random Reversible CircuitsWilliam Gay, William He, Nicholas Kocurek, Ryan O'DonnellCRYPTO 2025 · 1 citation
  2. Efficiently Batching Unambiguous Interactive ProofsBonnie Berger, Rohan Goyal, Matthew M. Hong, Yael Tauman KalaiFOCS 2025

Related papers

  1. Incompressibility and Spectral Gaps of Random CircuitsChi-Fang Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu et al.FOCS 2025 · 5 citations
  2. 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
  3. How Fast Does the Inverse Walk Approximate a Random Permutation?Vishesh Jain, Tianren Liu, Clayton Mizgerd, Angelos Pelecanos et al.CRYPTO 2026 · 1 citation
  4. Layout Graphs, Random Walks and the t-Wise Independence of SPN Block CiphersTianren Liu, Angelos Pelecanos, Stefano Tessaro, Vinod VaikuntanathanCRYPTO 2023 · 9 citations
  5. Entropic independence: optimal mixing of down-up random walksNima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham et al.STOC 2022 · 21 citations
Dusk over the sea between two cliffs drawn in fine vertical lines