## Pseudo-Mixing Time of Random Walks

#### Webpage for a paper by Itai Benjamini and Oded Goldreich

#### Abstract

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)=\omega(\log\log N)$.
Furthermore, the vertices of these graphs can be represented by strings
of length $2\log_2N$, and the incidence function of these graphs can be
computed by Boolean circuits of size $poly(\log N)$.

#### Material available on-line

- First version posted:
June 2019.
- Revisions: none yet.

Back to
either Oded Goldreich's homepage
or general list of papers.