School Seminar Series

Sampling Permutations with Cell-Probes is Hard

8th June 2026, 13:00 add to calenderAshton Lecture Theatre
Artur Riazanov
EPFL

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, ALP 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.
add to calender (including abstract)

Biography

Artur has just graduated from a PhD program at EPFL advised by Mika Göös. Before that he was a research assistant at Technion hosted by Yuval Filmus, and even before that he was a Junior Researcher at PDMI advised by Dmitry Itsykson. He does research in communication and circuit complexity.

Additional Materials