Title: Sampling Permutations with Cell-Probes is Hard
Speaker: Artur Riazanov (EPFL, Switzerland)
Invited by: Bruno Loff (LASIGE, DM/FCUL)
When: October 7, 2025, 12h00
Where: FCUL, 6.2.33

Abstract: Generating uniformly random permutations is a very basic task that is routinely done in randomized algorithms, there is a very simple algorithm that does it in linear time. Doing this in parallel is more challenging with a vast literature including non-trivial upper bounds in switching networks (Czumaj, STOC 2015), low-depth circuits (Hagerup, ICALP 1991), EREW PRAM (Czumaj, Kanarek, Kutyłowski, Loryś, SODA 1999). We study this question in the cell-probe model: given an unlimited supply of uniform symbols in [n], generate the elements of a permutation S_n by making several probes (queries) to the uniform string for each output symbol. Before our work it was not known if sampling is possible with two probes. The challenge to show this impossibility was posed by Viola (SICOMP 2020), who gave a log log n lower bound for the case of non-adaptive probes. The non-adaptive bound was later improved by Yu and Zhan (ITCS 2024) to almost log n. We show two lower bounds (1) superconstant for the adaptive case (2) polynomial for the non-adaptive case. Both of our results yield new lower bounds for succinct data structures. This is joint work with Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, and Dmitry Sokolov.

Bio: Artur Riazanov is a PhD student of Mika Goos at the Swiss Federal Technology Institute of Lausanne (EPFL).

This presentation is supported by the project HOFGA, Grant agreement ID: 101041696, funded by European Reserach Council’s Horizon Europe programme.