[1]   Scott Aaronson, Shalev Ben-David, and Robin Kothari: Separations in query complexity using cheat sheets. In Proc. 48th STOC, pp. 863–876. ACM Press, 2016. [doi:10.1145/2897518.2897644, arXiv:1511.01937, ECCC:TR15-175]

[2]   Noga Alon, Troy Lee, Adi Schraibman, and Santosh Vempala: The approximate rank of a matrix and its algorithmic applications. In Proc. 45th STOC, pp. 675–684. ACM Press, 2013. [doi:10.1145/2488608.2488694, ECCC:TR12-169]

[3]   Andris Ambainis: Quantum lower bounds by quantum arguments. J. Comput. System Sci., 64(4):750–767, 2002. Preliminary version in STOC’00. [doi:10.1006/jcss.2002.1826, arXiv:quant-ph/0002066]

[4]   Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach. Cambridge Univ. Press, 2009. Book.

[5]   László Babai, Anna Gál, and Avi Wigderson: Superpolynomial lower bounds for monotone span programs. Combinatorica, 19(3):301–319, 1999. [doi:10.1007/s004930050058]

[6]   Howard Barnum, Michael E. Saks, and Mario Szegedy: Quantum query complexity and semi-definite programming. In Proc. 18th IEEE Conf. on Comput. Complexity (CCC’03), pp. 179–193. IEEE Comp. Soc., 2003. [doi:10.1109/CCC.2003.1214419]

[7]   Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp: Quantum amplitude amplification and estimation. In Samual J. Lomonaca and Howard E. Brandt, editors, Quantum Computation and Quantum Information: A Millennium Volume, pp. 53–74. Amer. Math. Soc., 2002. [doi:10.1090/conm/305, arXiv:quant-ph/0005055]

[8]   Mark Bun and Justin Thaler: A nearly optimal lower bound on the approximate degree of AC⁰. SIAM J. Comput., 49(4):59–96, 2020. Preliminary version in FOCS’17. [doi:10.1137/17M1161737, arXiv:1703.05784, ECCC:TR17-051]

[9]   Bill Fefferman and Cedric Yen-Yu Lin: A complete characterization of unitary quantum space. In Proc. 9th Innovations in Theoret. Comp. Sci. Conf. (ITCS’18), pp. 4:1–21. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ITCS.2018.4, arXiv:1604.01384]

[10]   Bill Fefferman and Zachary Remscrim: Eliminating intermediate measurements in space-bounded quantum computation. In Proc. 53rd STOC, pp. 1343–1356. ACM Press, 2021. [doi:10.1145/3406325.3451051, arXiv:2006.03530, ECCC:TR20-088]

[11]   Anna Gál: A characterization of span program size and improved lower bounds for monotone span programs. Comput. Complexity, 10(4):277–296, 2001. Preliminary version in STOC’98. [doi:10.1007/s000370100001]

[12]   Uma Girish, Ran Raz, and Wei Zhan: Quantum logspace algorithm for powering matrices with bounded norm. In Proc. 48th Internat. Colloq. on Automata, Languages, and Programming (ICALP’21), pp. 73:1–20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021. [doi:10.4230/LIPIcs.ICALP.2021.73, arXiv:2006.04880, ECCC:TR20-087]

[13]   Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov: Adventures in monotone complexity and TFNP. In Proc. 10th Innovations in Theoret. Comp. Sci. Conf. (ITCS’19), pp. 38:1–19. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ITCS.2019.38, ECCC:TR18-163]

[14]   Peter Høyer, Troy Lee, and Robert Špalek: Negative weights make adversaries stronger. In Proc. 39th STOC, pp. 526–535. ACM Press, 2007. [doi:10.1145/1250790.1250867]

[15]   Tsuyoshi Ito and Stacey Jeffery: Approximate span programs. Algorithmica, 81(6):2158–2195, 2019. Preliminary version in ICALP’16. [doi:10.1007/s00453-018-0527-1, arXiv:1507.00432]

[16]   Stacey Jeffery: Frameworks for Quantum Algorithms. Ph. D. thesis, University of Waterloo, 2014. Available at http://uwspace.uwaterloo.ca/handle/10012/8710.

[17]   Stacey Jeffery: Span programs and quantum space complexity. In Proc. 11th Innovations in Theoret. Comp. Sci. Conf. (ITCS’20), pp. 4:1–37. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.ITCS.2020.4, arXiv:1908.04232]

[18]   Stacey Jeffery and Shelby Kimmel: Quantum algorithms for graph connectivity and formula evaluation. Quantum, 1:26:1–40, 2017. [doi:10.22331/q-2017-08-17-26, arXiv:1704.00765]

[19]   Richard Jozsa, Barbara Kraus, Akimasa Miyake, and John Watrous: Matchgate and space-bounded quantum computations are equivalent. Proc. Royal Soc. A, 466(2115):809–830, 2010. [doi:10.1098/rspa.2009.0433]

[20]   Mauricio Karchmer and Avi Wigderson: On span programs. In Proc. 8th IEEE Conf. Structure in Complexity Theory (SCT’93), pp. 102–111. IEEE Comp. Soc., 1993. [doi:10.1109/SCT.1993.336536]

[21]   Alexei Y. Kitaev: Quantum measurements and the Abelian stabilizer problem. Electron. Colloq. Comput. Complexity, TR96-003, 1996. [ECCC, arXiv:quant-ph/9511026]

[22]   Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy: Quantum query complexity of state conversion. In Proc. 52nd FOCS, pp. 344–353. IEEE Comp. Soc., 2011. [doi:10.1109/FOCS.2011.75]

[23]   Satyanarayana V. Lokam: Complexity lower bounds using linear algebra. Found. Trends Theor. Comp. Sci., 4(1–2):1–155, 2009. [doi:10.1561/0400000011]

[24]   Toniann Pitassi and Robert Robere: Strongly exponential lower bounds for monotone computation. In Proc. 49th STOC, pp. 1246–1255. ACM Press, 2017. [doi:10.1145/3055399.3055478, ECCC:TR16-188]

[25]   Alexander A. Razborov: Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica, 10(1):81–93, 1990. [doi:10.1007/BF02122698]

[26]   Alexander A. Razborov: On submodular complexity measures. In Proc. London Math. Soc. Symposium on Boolean Function Complexity, pp. 76–83, 1992. Author’s website.

[27]   Ben W. Reichardt: Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function. In Proc. 50th FOCS, pp. 544–551. IEEE Comp. Soc., 2009. [doi:10.1109/FOCS.2009.55, arXiv:0904.2759]

[28]   Ben W. Reichardt and Robert Špalek: Span-program-based quantum algorithm for evaluating formulas. Theory of Computing, 8(13):291–319, 2012. Preliminary version in STOC’08. [doi:10.4086/toc.2012.v008a013]

[29]   Robert Robere, Toniann Pitassi, Benjamin Rossman, and Stephen A. Cook: Exponential lower bounds for monotone span programs. In Proc. 57th FOCS, pp. 406–415. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.51, ECCC:TR16-064]

[30]   Alexander A. Sherstov: The pattern matrix method. SIAM J. Comput., 40(6):1969–2000, 2011. [doi:10.1137/080733644, arXiv:0906.4291]

[31]   John Watrous: Space-bounded quantum complexity. J. Comput. System Sci., 59(2):281–326, 1999. [doi:10.1006/jcss.1999.1655]