ECCC-Report TR19-078https://eccc.weizmann.ac.il/report/2019/078Comments and Revisions published for TR19-078en-usSat, 01 Jun 2019 10:34:30 +0300
Paper TR19-078
| Pseudo-Mixing Time of Random Walks |
Itai Benjamini,
Oded Goldreich
https://eccc.weizmann.ac.il/report/2019/078We 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 string of length $2\log_2N$, and the incidence function of these graphs can be computed by Boolean circuits of size $poly(\log N)$.
Sat, 01 Jun 2019 10:34:30 +0300https://eccc.weizmann.ac.il/report/2019/078