Pseudo-Mixing Time of Random Walks

摘要

We introduce the notion of pseudo-mixing time of a graph define as the number of steps in a random walk that suffices for generating a vertex that looks random to any polynomial-time observer, where, in addition to the tested vertex, the observer is also provided with oracle access to the incidence function of the graph. Assuming the existence of one-way functions, we show that the pseudo-mixing time of a graph can be much smaller than its mixing time. Specifically, we present bounded-degree N -vertex Cayley graphs that have pseudo-mixing time t for any t ( N ) = ( log log N ) . Furthermore, the vertices of these graphs can be represented by string of length 2 log 2 N , and the incidence function of these graphs can be computed by Boolean circuits of size pol y ( log N ) .