Sampling Permutations with Cell Probes is Hard
Authors
Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, Dmitry Sokolov
Categories
Abstract
Suppose we are given an infinite sequence of input cells, each initialized with a uniform random symbol from $[n]$. How hard is it to output a sequence in $[n]^n$ that is close to a uniform random permutation? Viola (SICOMP 2020) conjectured that if each output cell is computed by making $d$ probes to input cells, then $d\geqω(1)$. Our main result shows that, in fact, $d\geq (\log n)^{Ω(1)}$, which is tight up to the constant in the exponent. Our techniques also show that if the probes are nonadaptive, then $d\geq n^{Ω(1)}$, which is an exponential improvement over the previous nonadaptive lower bound due to Yu and Zhan (ITCS 2024). Our results also imply lower bounds against succinct data structures for storing permutations.
Sampling Permutations with Cell Probes is Hard
Categories
Abstract
Suppose we are given an infinite sequence of input cells, each initialized with a uniform random symbol from $[n]$. How hard is it to output a sequence in $[n]^n$ that is close to a uniform random permutation? Viola (SICOMP 2020) conjectured that if each output cell is computed by making $d$ probes to input cells, then $d\geqω(1)$. Our main result shows that, in fact, $d\geq (\log n)^{Ω(1)}$, which is tight up to the constant in the exponent. Our techniques also show that if the probes are nonadaptive, then $d\geq n^{Ω(1)}$, which is an exponential improvement over the previous nonadaptive lower bound due to Yu and Zhan (ITCS 2024). Our results also imply lower bounds against succinct data structures for storing permutations.
Authors
Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov et al. (+2 more)
Click to preview the PDF directly in your browser