[1]   AmirMahdi Ahmadinejad, Jonathan A. Kelner, Jack Murtagh, John Peebles, Aaron Sidford, and Salil Vadhan: High-precision estimation of random walks in small space. In Proc. 61st FOCS, pp. 1295–1306. IEEE Comp. Soc., 2020. [doi:10.1109/FOCS46700.2020.00123]

[2]   Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff: Random walks, universal traversal sequences, and the complexity of maze problems. In Proc. 20th FOCS, pp. 218–223. IEEE Comp. Soc., 1979. [doi:10.1109/SFCS.1979.34]

[3]   Noga Alon: Eigenvalues and expanders. Combinatorica, 6(2):83–96, 1986. Preliminary version in STOC’84. [doi:10.1007/BF02579166]

[4]   Noga Alon: Explicit expanders of every degree and size. Combinatorica, 2021. [doi:10.1007/s00493-020-4429-x, arXiv:2003.11673]

[5]   Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta: Simple constructions of almost k-wise independent random variables. Random Struct. Algor., 3(3):289–304, 1992. See also addendum in vol. 4(1), 1993, pp. 199–120. [doi:10.1002/rsa.3240030308]

[6]   Noga Alon and Vitaly D. Milman: λ₁, isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory–B, 38(1):73–88, 1985. [doi:10.1016/0095-8956(85)90092-9]

[7]   Noga Alon, Oded Schwartz, and Asaf Shapira: An elementary construction of constant-degree expanders. Combin. Probab. Comput., 17(3):319–327, 2008. [doi:10.1017/S0963548307008851]

[8]   Sanjeev Arora and Boaz Barak: Computational Complexity: A modern approach. Cambridge Univ. Press, 2009.

[9]   Joshua Batson, Daniel A. Spielman, Nikhil Srivastava, and Shang-Hua Teng: Spectral sparsification of graphs: Theory and algorithms. Comm. ACM, 56(8):87–94, 2013. [doi:10.1145/2492007.2492029]

[10]   Paul W. Beame, Stephen A. Cook, and H. James Hoover: Log depth circuits for division and related problems. SIAM J. Comput., 15(4):994–1003, 1986. [doi:10.1137/0215070]

[11]   Mark Braverman, Anup Rao, Ran Raz, and Amir Yehudayoff: Pseudorandom generators for regular branching programs. SIAM J. Comput., 43(3):973–986, 2014. Preliminary version in FOCS’10. [doi:10.1137/120875673]

[12]   Joshua Brody and Elad Verbin: The coin problem and pseudorandomness for branching programs. In Proc. 51st FOCS, pp. 30–39. IEEE Comp. Soc., 2010. [doi:10.1109/FOCS.2010.10]

[13]   Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, and Shang-Hua Teng: Scalable parallel factorizations of SDD matrices and efficient sampling for Gaussian graphical models. 2014. [arXiv:1410.5392]

[14]   Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, and Shang-Hua Teng: Spectral sparsification of random-walk matrix polynomials. 2015. [arXiv:1502.03496]

[15]   Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup Rao, Aaron Sidford, and Adrian Vladu: Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs. In Proc. 49th STOC, pp. 410–419. ACM Press, 2017. [doi:10.1145/3055399.3055463]

[16]   Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, and Adrian Vladu: Faster algorithms for computing the stationary distribution, simulating random walks, and more. In Proc. 57th FOCS, pp. 583–592. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.69]

[17]   Anindya De: Pseudorandomness for permutation and regular branching programs. In Proc. 26th IEEE Conf. on Comput. Complexity (CCC’11), pp. 221–231. IEEE Comp. Soc., 2011. [doi:10.1109/CCC.2011.23]

[18]   Ofer Gabber and Zvi Galil: Explicit constructions of linear-sized superconcentrators. J. Comput. System Sci., 22(3):407–420, 1981. Preliminary version in FOCS’79. [doi:10.1016/0022-0000(81)90040-4]

[19]   Oded Goldreich: Computational complexity: A conceptual perspective. Cambridge Univ. Press, 2008. [doi:10.1017/CBO9780511804106]

[20]   Oded Goldreich: On constructing expanders for any number of vertices. In Oded Goldreich, editor, Computational Complexity and Property Testing, volume 12050 of LNCS, pp. 374–379. Springer, 2020. Preliminary version in Author’s home page. [doi:10.1007/978-3-030-43662-9_21]

[21]   William Hesse, Eric Allender, and David A. Mix Barrington: Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. System Sci., 65(4):695–716, 2002. With 2014 update in JCSS, Vol. 80(2), 496–497. [doi:10.1016/j.jcss.2013.09.002]

[22]   Roger A. Horn and Charles R. Johnson: Matrix Analysis. Cambridge Univ. Press, 1990. [doi:10.1017/CBO9781139020411]

[23]   Russell Impagliazzo, Noam Nisan, and Avi Wigderson: Pseudorandomness for network algorithms. In Proc. 26th STOC, pp. 356–364. ACM Press, 1994. [doi:10.1145/195058.195190]

[24]   Gorav Jindal, Pavel Kolev, Richard Peng, and Saurabh Sawlani: Density independent algorithms for sparsifying k-step random walks. In Proc. 20th Internat. Workshop on Approximation Algorithms for Combinat. Opt. Probl. (APPROX’17), pp. 14:1–17. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.APPROX-RANDOM.2017.14]

[25]   Rasmus Kyng, Jakub Pachocki, Richard Peng, and Sushant Sachdeva: A framework for analyzing resparsification algorithms. In Proc. 28th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’17). SIAM, 2017. [doi:10.1137/1.9781611974782.132, arXiv:1611.06940]

[26]   Yin Tat Lee, Richard Peng, and Daniel A. Spielman: Sparsified Cholesky solvers for SDD linear systems. 2015. [arXiv:1506.08204]

[27]   Po-ling Loh and Martin J. Wainwright: Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses. In Proc. 25th Adv. Neural Info. Proc. Sys. (NIPS’12), pp. 2087–2095. Curran Assoc., 2012. NIPS.

[28]   Grigory A. Margulis: Explicit constructions of expanders. Problemy Peredachi Informatsii, 9(4):71–80, 1973. MathNet.ru.

[29]   Gary L. Miller and Richard Peng: Approximate maximum flow on separable undirected graphs. In Proc. 24th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’13), pp. 1151–1170. SIAM, 2013. [doi:10.1137/1.9781611973105.83]

[30]   Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil P. Vadhan: Derandomization beyond connectivity: Undirected Laplacian systems in nearly logarithmic space. In Proc. 58th FOCS, pp. 801–812. IEEE Comp. Soc., 2017. [doi:10.1109/FOCS.2017.79]

[31]   Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil P. Vadhan: Deterministic approximation of random walks in small space. In Proc. 23rd Internat. Conf. on Randomization and Computation (RANDOM’19), pp. 42:1–22. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.APPROX-RANDOM.2019.42]

[32]   Joseph Naor and Moni Naor: Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput., 22(4):838–856, 1993. [doi:10.1137/0222053]

[33]   Richard Peng and Daniel A. Spielman: An efficient parallel solver for SDD linear systems. In Proc. 46th STOC, pp. 333–342. ACM Press, 2014. [doi:10.1145/2591796.2591832]

[34]   Omer Reingold: Undirected connectivity in log-space. J. ACM, 55(4):17:1–24, 2008. [doi:10.1145/1391289.1391291]

[35]   Omer Reingold, Salil Vadhan, and Avi Wigderson: Entropy waves, the zig-zag graph product, and new constant-degree expanders. Ann. Math., 155(1):157–187, 2002. [doi:10.2307/3062153]

[36]   Eyal Rozenman and Salil Vadhan: Derandomized squaring of graphs. In Proc. 9th Internat. Workshop on Randomization and Computation (RANDOM’05), pp. 436–447. Springer, 2005. [doi:10.1007/11538462_37]

[37]   Michael Saks and Shiyu Zhou: BP_HSPACE(S) ⊆ DSPACE(S^3∕2). J. Comput. System Sci., 58(2):376–403, 1999. Preliminary version in FOCS’95. [doi:10.1006/jcss.1998.1616]

[38]   Daniel A. Spielman and Shang-Hua Teng: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proc. 36th STOC, pp. 81–90. ACM Press, 2004. [doi:10.1145/1007352.1007372]

[39]   Daniel A. Spielman and Shang-Hua Teng: Spectral sparsification of graphs. SIAM J. Comput., 40(4):981–1025, 2011. [doi:10.1137/08074489X]

[40]   Thomas Steinke: Pseudorandomness for permutation branching programs without the group theory. Electron. Colloq. Comput. Complexity, TR12-083, 2012. [ECCC]

[41]   R. Michael Tanner: Explicit concentrators from generalized N-gons. SIAM J. Alg. Discr. Methods, 5(3):287–293, 1984. [doi:10.1137/0605030]