[1]   Eric Allender, Robert Beals, and Mitsunori Ogihara: The complexity of matrix rank and feasible systems of linear equations. Comput. Complexity, 8(2):99–126, 1999. Preliminary version in STOC’96. [doi:10.1007/s000370050023]

[2]   Kazuyuki Amano: Bounding the randomized decision tree complexity of read-once boolean functions. In Proc. 22nd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’11), pp. 1729–1744. ACM Press, 2011. [ACM:2133169]

[3]   Andris Ambainis: Polynomial degree vs. quantum query complexity. J. Comput. System Sci., 72(2):220–238, 2006. Preliminary version in FOCS’03. [doi:10.1016/j.jcss.2005.06.006, arXiv:quant-ph/0305028]

[4]   Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, and Shengyu Zhang: Any AND-OR formula of size N can be evaluated in time N^1∕2+o(1) on a quantum computer. SIAM J. Comput., 39(6):2513–2530, 2010. Preliminary version in FOCS’07. [doi:10.1137/080712167]

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

[6]   Howard Barnum and Michael Saks: A lower bound on the quantum query complexity of read-once functions. J. Comput. System Sci., 69(2):244–258, 2004. [doi:10.1016/j.jcss.2004.02.002, arXiv:quant-ph/0201007]

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

[8]   Amos Beimel, Anna Gál, and Mike Paterson: Lower bounds for monotone span programs. Comput. Complexity, 6(1):29–45, 1996. Preliminary version in FOCS’95. [doi:10.1007/BF01202040]

[9]   Aleksandrs Belovs: Span-program-based quantum algorithm for the rank problem. Technical report, 2011. [arXiv:1103.0842]

[10]   Aleksandrs Belovs: Span programs for functions with constant-sized 1-certificates: extended abstract. In Proc. 44th STOC. ACM Press, 2012. [doi:10.1145/2213977.2213985, arXiv:quant-ph/0611054]

[11]   Aleksandrs Belovs and Troy Lee: Quantum algorithm for k-distinctness with prior knowledge on the input. Technical report, 2011. [arXiv:1108.3022]

[12]   Aleksandrs Belovs and Ben W. Reichardt: Span programs and quantum algorithms for st-connectivity and claw detection. Technical report, 2012. [arXiv:1203.2603]

[13]   Maria Luisa Bonet and Samuel R. Buss: Size-depth tradeoffs for Boolean formulae. Inform. Process. Lett., 49(3):151–155, 1994. [doi:10.1016/0020-0190(94)90093-0]

[14]   Nader H. Bshouty, Richard Cleve, and Wayne Eberly: Size-depth tradeoffs for algebraic formulas. SIAM J. Comput., 24(4):682–705, 1995. Preliminary version in FOCS’91. [doi:10.1137/S0097539792232586]

[15]   Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David L. Yonge-Mallo: Discrete-query quantum algorithm for NAND trees. Theory of Computing, 5(1):119–123, 2009. [doi:10.4086/toc.2009.v005a005]

[16]   Ronald Cramer and Serge Fehr: Optimal black-box secret sharing over arbitrary abelian groups. In 22nd Ann. Internat. Cryptology Conf. (CRYPTO’02), pp. 272–287. Springer, 2002. [doi:10.1007/3-540-45708-9_18]

[17]   Edward Farhi, Jeffrey Goldstone, and Sam Gutmann: A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing, 4(1):169–190, 2008. [doi:10.4086/toc.2008.v004a008]

[18]   Dmitry Gavinsky and Tsuyoshi Ito: A quantum query algorithm for the graph collision problem. Technical report, 2012. [arXiv:1204.1527]

[19]   Gene H. Golub and Charles F. Van Loan: Matrix Computations. Johns Hopkins, Baltimore, 3rd edition, 1996.

[20]   Lov K. Grover: A fast quantum mechanical algorithm for database search. In Proc. 28th STOC, pp. 212–219. ACM Press, 1996. [doi:10.1145/237814.237866, arXiv:quant-ph/9605043]

[21]   Lov K. Grover: Tradeoffs in the quantum search algorithm. Phys. Rev. A, 66:052314, 2002. [doi:10.1103/PhysRevA.66.052314, arXiv:quant-ph/0201152]

[22]   Rafi Heiman and Avi Wigderson: Randomized vs. deterministic decision tree complexity for read-once Boolean functions. Comput. Complexity, 1:311–329, 1991. Preliminary version in Structure in Complexity Theory’91. [doi:10.1007/BF01212962]

[23]   Peter Høyer, Troy Lee, and Robert Špalek: Source codes of semidefinite programs for ADV^±. [Link], 2006.

[24]   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, arXiv:quant-ph/0611054]

[25]   T. S. Jayram, Ravi Kumar, and D. Sivakumar: Two applications of information complexity. In Proc. 35th STOC, pp. 673–682. ACM Press, 2003. [doi:10.1145/780542.780640]

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

[27]   Shelby Kimmel: Quantum adversary (upper) bound. Technical report, 2011. [arXiv:1101.0797]

[28]   A. Yu. Kitaev: Quantum measurements and the Abelian stabilizer problem. Technical report, 1995. [arXiv:quant-ph/9511026]

[29]   Troy Lee, Frédéric Magniez, and Miklos Santha: A learning graph based quantum query algorithm for finding constant-size subgraphs. Technical report, 2011. [arXiv:1109.5135]

[30]   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. Press, 2011. [doi:10.1109/FOCS.2011.75, arXiv:1011.3020]

[31]   Frédéric Magniez, Ashwin Nayak, Miklos Santha, and David Xiao: Improved bounds for the randomized decision tree complexity of recursive majority. In Proc. 38th Internat. Colloq. on Automata, Languages and Programming (ICALP’11), pp. 317–329. Springer, 2011. [doi:10.1007/978-3-642-22006-7_27]

[32]   Daniel Nagaj, Pawel Wocjan, and Yong Zhang: Fast amplification of QMA. Quantum Inf. Comput., 9(11):1053–1068, 2011. [ACM:2012106, arXiv:0904.1549]

[33]   Michael A. Nielsen and Isaac L. Chuang: Quantum computation and quantum information. Cambridge University Press, Cambridge, 2000.

[34]   Ventzislav Nikov, Svetla Nikova, and Bart Preneel: On the size of monotone span programs. In 4th Internat. Conf. on Security in Communication Networks (SCN’04), pp. 249–262. Springer, 2004. [doi:10.1007/978-3-540-30598-9_18]

[35]   Ben W. Reichardt: Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function (70 pp.). Technical report, 2009. Extended abstract in FOCS’09. [arXiv:0904.2759]

[36]   Ben Reichardt: Faster quantum algorithm for evaluating game trees. In Proc. 22nd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’11), pp. 546–559. ACM Press, 2011. [ACM:2133079, arXiv:0907.1623]

[37]   Ben Reichardt: Reflections for quantum query algorithms. In Proc. 22nd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’11), pp. 560–569. ACM Press, 2011. [ACM:2133080, arXiv:1005.1601]

[38]   Ben W. Reichardt: Span-program-based quantum algorithm for evaluating unbalanced formulas. 6th Conf. Theory of Quantum Computation, Communication and Cryptography (TQC), 2011. [arXiv:0907.1622]

[39]   Ben W. Reichardt and Robert Špalek: Span-program-based quantum algorithm for evaluating formulas. In Proc. 40th STOC, pp. 103–112. ACM Press, 2008. [doi:10.1145/1374376.1374394, arXiv:0710.2630v3]

[40]   Michael E. Saks and Avi Wigderson: Probabilistic Boolean decision trees and the complexity of evaluating game trees. In Proc. 27th FOCS, pp. 29–38. IEEE Comp. Soc. Press, 1986. [doi:10.1109/SFCS.1986.44]

[41]   Miklos Santha: On the Monte Carlo boolean decision tree complexity of read-once formulae. Random Structures Algorithms, 6(1):75–88, 1995. Preliminary version in Structure in Complexity Theory’91. [doi:10.1002/rsa.3240060108]

[42]   Marc Snir: Lower bounds on probabilistic linear decision trees. Theoret. Comput. Sci., 38:69–82, 1985. [doi:10.1016/0304-3975(85)90210-5]

[43]   Mario Szegedy: Quantum speed-up of Markov chain based algorithms. In Proc. 45th FOCS, pp. 32–41. IEEE Comp. Soc. Press, 2004. [doi:10.1109/FOCS.2004.53, arXiv:quant-ph/0401053]

[44]   Bohua Zhan, Shelby Kimmel, and Avinatan Hassidim: Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure. In Innovations in Theoretical Computer Science 2012 (ITCM’12), pp. 249–265. ACM Press, 2012. [doi:10.1145/2090236.2090258, arXiv:1101.0796]

[45]   Yechao Zhu: Quantum query complexity of subgraph containment with constant-sized certificates. Technical report, 2011. [arXiv:1109.4165]