We give a deterministic, nearly logarithmic-space algorithm that given an undirected graph \(G\), a positive integer \(r\), and a set \(S\) of vertices, approximates the conductance of \(S\) in the \(r\)-step random walk on \(G\) to within a factor of \(1+ϵ\), where \(ϵ > 0\) is an arbitrarily small constant. More generally, our algorithm computes an \(ϵ\)-spectral approximation to the normalized Laplacian of the \(r\)-step walk. Our algorithm combines the derandomized square graph operation (Rozenman and Vadhan, 2005), which we recently used for solving Laplacian systems in nearly logarithmic space (Murtagh, Reingold, Sidford, and Vadhan, 2017), with ideas from (Cheng, Cheng, Liu, Peng, and Teng, 2015), which gave an algorithm that is time-efficient (while ours is space-efficient) and randomized (while ours is deterministic) for the case of even \(r\) (while ours works for all \(r\)). Along the way, we provide some new results that generalize technical machinery and yield improvements over previous work. First, we obtain a nearly linear-time randomized algorithm for computing a spectral approximation to the normalized Laplacian for odd \(r\). Second, we define and analyze a generalization of the derandomized square for irregular graphs and for sparsifying the product of two distinct graphs. As part of this generalization, we also give a strongly explicit construction of expander graphs of every size.
Computational Complexity
Deterministic approximation of random walks in small space.” Theory of Computing Special Issue on RANDOM '19 (Forthcoming). Publisher's VersionAbstract
. “
Pseudorandom generators for read-once monotone branching programs.” Electronic Colloquium on Computational Complexity (ECCC) 2021, no. 18 (2021). Publisher's VersionAbstract
. “
Pseudodistributions that beat all pseudorandom generators.” Electronic Colloquium on Computational Complexity (ECCC) 2021, no. 19 (2021). Publisher's VersionAbstract
. “
Pseudorandom generators for unbounded-width permutation branching programs.” 12th Innovations in Theoretical Computer Science (ITCS '21) . Leibniz International Proceedings in Informatics (LIPIcs), 2021. Publisher's VersionAbstract
. “
Inaccessible entropy I: Inaccessible entropy generators and statistically hiding commitments from one-way functions.” arXiv: 2010.05586 [cs.CR] (2020). ArXiv VersionAbstract
. “
Spectral sparsification via bounded-independence sampling.” In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 168:39:1-39:21. Leibniz International Proceedings in Informatics (LIPIcs), Schloss-Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Publisher's VersionAbstract
. “
High-precision estimation of random walks in small space.” 61st Annual IEEE Symposium on the Foundations of Computer Science (FOCS 2020). IEEE, 2020. Publisher's VersionAbstract
. “
Inaccessible entropy II: IE functions and universal one-way hashing.” Theory of Computing 16, no. 8 (2020): 1-55. Publisher's VersionAbstract
. “
Computational entropy.” In Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali (Oded Goldreich, Ed.), 693-726. ACM, 2019. Publisher's VersionAbstract
. “
Differential privacy on finite computers.” Journal of Privacy and Confidentiality 9, no. 2 (2019). Publisher's VersionAbstract
. “
Unifying computational entropies via Kullback-Leibler divergence.” In Advances in Cryptology: CRYPTO 2019, A. Boldyreva and D. Micciancio, (Eds), 11693:831-858. Springer Verlag, Lecture Notes in Computer Science, 2019. Publisher's VersionAbstract
. “
The complexity of computing the optimal composition of differential privacy.” Theory of Computing 14 (2018): 1-35. Publisher's VersionAbstract
. “
A tight lower bound for entropy flattening.” In 33rd Computational Complexity Conference (CCC 2018), 102:23:21-23:28. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik: Leibniz International Proceedings in Informatics (LIPIcs), 2018. Publisher's VersionAbstract
. “
The Many Entropies in One-way Functions.” In Tutorials on the Foundations of Cryptography, 159-217. Springer, Yehuda Lindell, ed. 2017. Publisher's VersionAbstract
. “
The Complexity of Differential Privacy.” In Tutorials on the Foundations of Cryptography, 347-450. Springer, Yehuda Lindell, ed. 2017. Publisher's VersionAbstract
. “