Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > KONSTANTIN MYASNIKOV:
All reports by Author Konstantin Myasnikov:

TR25-177 | 14th November 2025
Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, Dmitry Sokolov

Sampling Permutations with Cell Probes is Hard

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 ... more >>>




ISSN 1433-8092 | Imprint