Sampling Permutations with Cell Probes is Hard

Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov +2

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…