Pseudo-mixing Time of Random Walks.
Itaï Benjamini, Oded Goldreich · 2020
We introduce the notion of pseudo-mixing time of a graph, defined as the number of steps in a random walk that suffices for generating a vertex that looks random to any polynomial-time observer. Here, in addition to the tested vertex, the observer is also provided with oracle access to the incidence function of the graph.