BARC talk by Artur Riazanov

Monday, April 20, 2026, 11:00-12:00, Artur Riazanov, PhD student at EPFL, will be giving a BARC talk on "Sampling Permutations with Cell-Probes is Hard".

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.


Bio:
Artur Riazanov is a PhD student at EPFL supervised by Mika Göös. Prior to this, Artur was at St. Petersburg department of Steklov Institute and at St. Petersburg Academic University working with Dmitry Itsykson. Before going from St. Petersburg to EPFL Artur enjoyed a long visit at Technion in Israel, hosted byYuval Filmus.

Artur's research interest include communication complexity, circuit complexity and proof complexity.

Host: Amir Yehudayoff