BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260605T050051Z
UID:Seminar-dept-1492@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20260608T130000
DTEND:20260608T140000
SUMMARY:School Seminar Series
DESCRIPTION:Artur Riazanov: Sampling Permutations with Cell-Probes is Hard\n\nGenerating 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.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1492
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR