Sampling Permutations with Cell Probes is Hard
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912743238402048 |
|---|---|
| author | Alekseev, Yaroslav Göös, Mika Myasnikov, Konstantin Riazanov, Artur Sokolov, Dmitry |
| author_facet | Alekseev, Yaroslav Göös, Mika Myasnikov, Konstantin Riazanov, Artur Sokolov, Dmitry |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_02724 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sampling Permutations with Cell Probes is Hard Alekseev, Yaroslav Göös, Mika Myasnikov, Konstantin Riazanov, Artur Sokolov, Dmitry Computational Complexity Data Structures and Algorithms 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. |
| title | Sampling Permutations with Cell Probes is Hard |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.02724 |