@article{Nisan1992,
  author  = {Nisan, Noam},
  title   = {Pseudorandom generators for space-bounded computation},
  journal = {Combinatorica},
  volume  = {12},
  number  = {4},
  pages   = {449--461},
  year    = {1992},
  doi     = {10.1007/BF01305237},
  url     = {https://doi.org/10.1007/BF01305237}
}

@article{NisanZuckerman1996,
  author  = {Nisan, Noam and Zuckerman, David},
  title   = {Randomness is linear in space},
  journal = {Journal of Computer and System Sciences},
  volume  = {52},
  number  = {1},
  pages   = {43--52},
  year    = {1996},
  doi     = {10.1006/jcss.1996.0004},
  url     = {https://doi.org/10.1006/jcss.1996.0004}
}

@article{SaksZhou1999,
  author  = {Saks, Michael and Zhou, Shiyu},
  title   = {{$\mathrm{BP}_{\mathrm H}\mathrm{SPACE}(S)\subseteq
              \mathrm{DSPACE}(S^{3/2})$}},
  journal = {Journal of Computer and System Sciences},
  volume  = {58},
  number  = {2},
  pages   = {376--403},
  year    = {1999},
  doi     = {10.1006/jcss.1998.1616},
  url     = {https://doi.org/10.1006/jcss.1998.1616}
}

@article{Reingold2008,
  author  = {Reingold, Omer},
  title   = {Undirected connectivity in log-space},
  journal = {Journal of the ACM},
  volume  = {55},
  number  = {4},
  pages   = {17:1--17:24},
  year    = {2008},
  doi     = {10.1145/1391289.1391291},
  url     = {https://doi.org/10.1145/1391289.1391291}
}

@inproceedings{RTV2006,
  author    = {Reingold, Omer and Trevisan, Luca and Vadhan, Salil},
  title     = {Pseudorandom walks on regular digraphs and the {RL} vs. {L} problem},
  booktitle = {Proceedings of the 38th Annual ACM Symposium on Theory of Computing},
  pages     = {457--466},
  year      = {2006},
  publisher = {Association for Computing Machinery},
  doi       = {10.1145/1132516.1132583},
  url       = {https://doi.org/10.1145/1132516.1132583}
}

@inproceedings{Hoza2021,
  author    = {Hoza, William M.},
  title     = {Better pseudodistributions and derandomization for space-bounded computation},
  booktitle = {Approximation, Randomization, and Combinatorial Optimization.
               Algorithms and Techniques (APPROX/RANDOM 2021)},
  series    = {Leibniz International Proceedings in Informatics},
  volume    = {207},
  pages     = {28:1--28:23},
  year      = {2021},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  doi       = {10.4230/LIPIcs.APPROX/RANDOM.2021.28},
  url       = {https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.28}
}

@book{BHV2008,
  author    = {Bekka, Bachir and de la Harpe, Pierre and Valette, Alain},
  title     = {{Kazhdan}'s property {(T)}},
  series    = {New Mathematical Monographs},
  volume    = {11},
  publisher = {Cambridge University Press},
  address   = {Cambridge},
  year      = {2008},
  isbn      = {978-0-521-88720-5},
  doi       = {10.1017/CBO9780511542749},
  url       = {https://doi.org/10.1017/CBO9780511542749}
}

@article{Kassabov2005,
  author  = {Kassabov, Martin},
  title   = {{Kazhdan} constants for {$\mathrm{SL}_n(\mathbb Z)$}},
  journal = {International Journal of Algebra and Computation},
  volume  = {15},
  number  = {5--6},
  pages   = {971--995},
  year    = {2005},
  doi     = {10.1142/S0218196705002712},
  url     = {https://doi.org/10.1142/S0218196705002712},
  eprint  = {math/0311487},
  archivePrefix = {arXiv}
}

@article{LMT2000,
  author  = {Lange, Klaus-J{\"o}rn and McKenzie, Pierre and Tapp, Alain},
  title   = {Reversible space equals deterministic space},
  journal = {Journal of Computer and System Sciences},
  volume  = {60},
  number  = {2},
  pages   = {354--367},
  year    = {2000},
  doi     = {10.1006/jcss.1999.1672},
  url     = {https://doi.org/10.1006/jcss.1999.1672}
}

@article{Shalom1999,
  author  = {Shalom, Yehuda},
  title   = {Bounded generation and {Kazhdan}'s property {(T)}},
  journal = {Publications Math{\'e}matiques de l'IH{\'E}S},
  volume  = {90},
  pages   = {145--168},
  year    = {1999},
  doi     = {10.1007/BF02698832},
  url     = {https://numdam.org/articles/10.1007/BF02698832/}
}

@article{ChengHoza2022,
  author  = {Cheng, Kuan and Hoza, William M.},
  title   = {Hitting Sets Give Two-Sided Derandomization of Small Space},
  journal = {Theory of Computing},
  volume  = {18},
  number  = {21},
  pages   = {1--32},
  year    = {2022},
  doi     = {10.4086/toc.2022.v018a021},
  url     = {https://theoryofcomputing.org/articles/v018a021/}
}

@article{CaiChakaravarthyVanMelkebeek2006,
  author  = {Cai, Jin-Yi and Chakaravarthy, Venkatesan T. and van Melkebeek, Dieter},
  title   = {Time-Space Tradeoff in Derandomizing Probabilistic Logspace},
  journal = {Theory of Computing Systems},
  volume  = {39},
  number  = {1},
  pages   = {189--208},
  year    = {2006},
  doi     = {10.1007/s00224-005-1264-9},
  url     = {https://pages.cs.wisc.edu/~jyc/papers/tradeoff.pdf}
}

@article{Gill1977,
  author = {Gill, John},
  title = {Computational Complexity of Probabilistic {Turing} Machines},
  journal = {SIAM Journal on Computing},
  volume = {6},
  number = {4},
  pages = {675--695},
  year = {1977},
  doi = {10.1137/0206049}
}

@inproceedings{AleliunasKLLR1979,
  author = {Aleliunas, Romas and Karp, Richard M. and Lipton, Richard J. and Lov{\'a}sz, L{\'a}szl{\'o} and Rackoff, Charles},
  title = {Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems},
  booktitle = {20th Annual Symposium on Foundations of Computer Science},
  pages = {218--223},
  year = {1979},
  publisher = {IEEE},
  doi = {10.1109/SFCS.1979.34}
}

@article{Simon1981,
  author = {Simon, Janos},
  title = {On tape-bounded probabilistic {Turing} machine acceptors},
  journal = {Theoretical Computer Science},
  volume = {16},
  number = {1},
  pages = {75--91},
  year = {1981},
  doi = {10.1016/0304-3975(81)90032-3}
}

@article{BorodinCookPippenger1983,
  author = {Borodin, Allan and Cook, Stephen and Pippenger, Nicholas},
  title = {Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines},
  journal = {Information and Control},
  volume = {58},
  number = {1--3},
  pages = {113--136},
  year = {1983},
  doi = {10.1016/S0019-9958(83)80060-6}
}

@article{Savitch1970,
  author = {Savitch, Walter J.},
  title = {Relationships between nondeterministic and deterministic tape complexities},
  journal = {Journal of Computer and System Sciences},
  volume = {4},
  number = {2},
  pages = {177--192},
  year = {1970},
  doi = {10.1016/S0022-0000(70)80006-X}
}

@article{Nisan1994RLinSC,
  author  = {Nisan, Noam},
  title   = {{$\mathrm{RL}\subseteq\mathrm{SC}$}},
  journal = {Computational Complexity},
  volume  = {4},
  number  = {1},
  pages   = {1--11},
  year    = {1994},
  doi     = {10.1007/BF01205052},
  url     = {https://doi.org/10.1007/BF01205052}
}

@inproceedings{NisanSzemerediWigderson1992,
  author = {Noam Nisan and Endre Szemer{\'e}di and Avi Wigderson},
  title = {Undirected connectivity in {$O(\log^{1.5} n)$} space},
  booktitle = {Proceedings of the 33rd Annual Symposium on Foundations of Computer Science},
  series = {FOCS '92},
  pages = {24--29},
  publisher = {IEEE Computer Society},
  year = {1992},
  doi = {10.1109/SFCS.1992.267822}
}

@article{ArmoniTaShmaWigdersonZhou2000,
  author = {Roy Armoni and Amnon Ta-Shma and Avi Wigderson and Shiyu Zhou},
  title = {An {$O(\log(n)^{4/3})$} space algorithm for {$(s,t)$} connectivity in undirected graphs},
  journal = {Journal of the ACM},
  volume = {47},
  number = {2},
  pages = {294--311},
  year = {2000},
  doi = {10.1145/333979.333984}
}

@inproceedings{Reingold2005,
  author = {Omer Reingold},
  title = {Undirected {ST}-connectivity in log-space},
  booktitle = {Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing},
  series = {STOC '05},
  pages = {376--385},
  publisher = {ACM},
  year = {2005},
  doi = {10.1145/1060590.1060647}
}

@inproceedings{ChenCohenDoronKhaskelbergTaShma2026,
  author = {Chen, Ben and Cohen, Gil and Doron, Dean and Khaskelberg, Yuval and Ta-Shma, Amnon},
  title = {Improved Error Reduction for Weighted {PRGs}},
  booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  series = {Leibniz International Proceedings in Informatics},
  volume = {392}, pages = {39:1--39:23}, year = {2026},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  doi = {10.4230/LIPIcs.APPROX/RANDOM.2026.39},
  url = {https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2026.39}
}

@misc{ChengWu2026SC,
  author = {Cheng, Kuan and Wu, Ruiyang},
  title = {{SC} Derandomization for Regular {ROBPs} and Models Beyond {BPL}},
  year = {2026},
  eprint = {2609.23603}, archivePrefix = {arXiv}, primaryClass = {cs.CC},
  note = {Version 1, September 20, 2026},
  url = {https://arxiv.org/abs/2609.23603}
}

@misc{PyneTell2026,
  author = {Pyne, Edward and Tell, Roei},
  title = {Using Hardness vs Randomness to Design Low-Space Algorithms},
  howpublished = {Electronic Colloquium on Computational Complexity, Report TR26-045},
  year = {2026},
  url = {https://eccc.weizmann.ac.il/report/2026/045/}
}

@inproceedings{PyneRazZhan2023,
  author = {Pyne, Edward and Raz, Ran and Zhan, Wei},
  title = {Certified Hardness vs. Randomness for Log-Space},
  booktitle = {64th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2023)},
  pages = {989--1007}, publisher = {IEEE}, year = {2023},
  doi = {10.1109/FOCS57990.2023.00061},
  note = {Full version: arXiv:2303.16413},
  url = {https://arxiv.org/abs/2303.16413}
}

@article{BravermanCohenGarg2020,
  author = {Braverman, Mark and Cohen, Gil and Garg, Sumegha},
  title = {Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs},
  journal = {SIAM Journal on Computing},
  volume = {49}, number = {5}, pages = {STOC18-242--STOC18-299},
  year = {2020}, doi = {10.1137/18M1197734},
  url = {https://doi.org/10.1137/18M1197734}
}

@inproceedings{CohenDoronRenardSberloTaShma2021,
  author = {Cohen, Gil and Doron, Dean and Renard, Oren and Sberlo, Ori and Ta-Shma, Amnon},
  title = {Error Reduction for Weighted {PRGs} Against Read Once Branching Programs},
  booktitle = {36th Computational Complexity Conference (CCC 2021)},
  series = {Leibniz International Proceedings in Informatics},
  volume = {200}, pages = {22:1--22:17}, year = {2021},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  doi = {10.4230/LIPIcs.CCC.2021.22},
  url = {https://doi.org/10.4230/LIPIcs.CCC.2021.22}
}

@article{Schwartz1980,
  author = {Schwartz, Jacob T.},
  title = {Fast Probabilistic Algorithms for Verification of Polynomial Identities},
  journal = {Journal of the ACM}, volume = {27}, number = {4},
  pages = {701--717}, year = {1980}, doi = {10.1145/322217.322225},
  url = {https://doi.org/10.1145/322217.322225}
}

@article{CarterWegman1979,
  author = {Carter, J. Lawrence and Wegman, Mark N.},
  title = {Universal Classes of Hash Functions},
  journal = {Journal of Computer and System Sciences},
  volume = {18}, number = {2}, pages = {143--154}, year = {1979},
  doi = {10.1016/0022-0000(79)90044-8},
  url = {https://doi.org/10.1016/0022-0000(79)90044-8}
}

@article{CookMcKenzie1987,
  author = {Cook, Stephen A. and McKenzie, Pierre},
  title = {Problems Complete for Deterministic Logarithmic Space},
  journal = {Journal of Algorithms},
  volume = {8}, number = {3}, pages = {385--394}, year = {1987},
  doi = {10.1016/0196-6774(87)90018-6},
  url = {https://www.cs.toronto.edu/~sacook/homepage/cook_mckenzie.pdf}
}

@incollection{Avizienis1963,
  author = {Avizienis, Algirdas},
  title = {On a Flexible Implementation of Digital Computer Arithmetic},
  editor = {Popplewell, C. M.},
  booktitle = {Information Processing 1962},
  publisher = {North-Holland}, year = {1963}, pages = {664--670},
  url = {https://www.ece.ucdavis.edu/~vojin/CLASSES/EPFL/Papers/1-Avizienis-Flex-Implmnt%20of%20Digital%20Com%20Arith.pdf}
}

@inproceedings{StockmeyerMeyer1973,
  author = {Stockmeyer, Larry J. and Meyer, Albert R.},
  title = {Word Problems Requiring Exponential Time (Preliminary Report)},
  booktitle = {Proceedings of the Fifth Annual ACM Symposium on Theory of Computing},
  publisher = {Association for Computing Machinery},
  year = {1973}, pages = {1--9},
  doi = {10.1145/800125.804029},
  url = {https://people.csail.mit.edu/meyer/meyer-stockmeyer-word-probs.pdf}
}

@inproceedings{AjtaiKomlosSzemeredi1987,
  author = {Ajtai, Mikl{\'o}s and Koml{\'o}s, J{\'a}nos and Szemer{\'e}di, Endre},
  title = {Deterministic simulation in {LOGSPACE}},
  booktitle = {Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing},
  pages = {132--140},
  year = {1987},
  publisher = {Association for Computing Machinery},
  doi = {10.1145/28395.28410},
  url = {https://doi.org/10.1145/28395.28410}
}

@article{BabaiNisanSzegedy1992,
  author = {Babai, L{\'a}szl{\'o} and Nisan, Noam and Szegedy, M{\'a}ri{\'o}},
  title = {Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs},
  journal = {Journal of Computer and System Sciences},
  volume = {45},
  number = {2},
  pages = {204--232},
  year = {1992},
  doi = {10.1016/0022-0000(92)90047-M},
  url = {https://doi.org/10.1016/0022-0000(92)90047-M}
}

@inproceedings{AhmadinejadKelnerMurtaghPeeblesSidfordVadhan2020,
  author = {Ahmadinejad, AmirMahdi and Kelner, Jonathan and Murtagh, Jack and Peebles, John and Sidford, Aaron and Vadhan, Salil},
  title = {High-precision estimation of random walks in small space},
  booktitle = {61st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2020)},
  pages = {1295--1306},
  year = {2020},
  publisher = {IEEE},
  doi = {10.1109/FOCS46700.2020.00123},
  note = {Full version: arXiv:1912.04524},
  url = {https://arxiv.org/abs/1912.04524}
}

@inproceedings{CohenDoronSberloTaShma2023,
  author = {Cohen, Gil and Doron, Dean and Sberlo, Ori and Ta-Shma, Amnon},
  title = {Approximating Iterated Multiplication of Stochastic Matrices in Small Space},
  booktitle = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing},
  pages = {35--45},
  year = {2023},
  publisher = {Association for Computing Machinery},
  doi = {10.1145/3564246.3585181},
  url = {https://doi.org/10.1145/3564246.3585181}
}

@inproceedings{BuhrmanCleveKouckyLoffSpeelman2014,
  author = {Buhrman, Harry and Cleve, Richard and Kouck{\'y}, Michal and Loff, Bruno and Speelman, Florian},
  title = {Computing with a Full Memory: Catalytic Space},
  booktitle = {Proceedings of the 46th Annual ACM Symposium on Theory of Computing},
  pages = {857--866},
  year = {2014},
  publisher = {Association for Computing Machinery},
  doi = {10.1145/2591796.2591874},
  url = {https://doi.org/10.1145/2591796.2591874}
}

@article{Riesz1927,
  author  = {Riesz, Marcel},
  title   = {Sur les maxima des formes bilin{\'e}aires et sur les fonctionnelles lin{\'e}aires},
  journal = {Acta Mathematica},
  volume  = {49},
  pages   = {465--497},
  year    = {1927},
  url     = {https://archive.ymsc.tsinghua.edu.cn/pacm_download/117/5399-11511_2007_Article_BF02564121.pdf}
}

@phdthesis{Thorin1948,
  author = {Thorin, G. O.},
  title = {Convexity theorems generalizing those of {M. Riesz} and {Hadamard} with some applications},
  school = {Lund University},
  year = {1948},
  note = {Russian translation by Yu. T. Medvedev, \emph{Matematika} 1 (1957), no.~3, 43--78. \href{https://www.mathnet.ru/eng/mat17}{Translation and bibliographic record}},
  url = {https://www.mathnet.ru/eng/mat17}
}