@inproceedings{Grover96,
  author = {Lov K. Grover},
  title = {A Fast Quantum Mechanical Algorithm for Database Search},
  booktitle = {Proceedings of the 28th Annual ACM Symposium on Theory of Computing},
  pages = {212--219},
  year = {1996},
  publisher = {ACM},
  doi = {10.1145/237814.237866},
  eprint = {quant-ph/9605043},
  archivePrefix = {arXiv}
}

@article{BBCMW01,
  author = {Robert Beals and Harry Buhrman and Richard Cleve and Michele Mosca and Ronald de Wolf},
  title = {Quantum Lower Bounds by Polynomials},
  journal = {Journal of the ACM},
  volume = {48},
  number = {4},
  pages = {778--797},
  year = {2001},
  doi = {10.1145/502090.502097},
  eprint = {quant-ph/9802049},
  archivePrefix = {arXiv}
}

@article{BBBV97,
  author = {Charles H. Bennett and Ethan Bernstein and Gilles Brassard and Umesh Vazirani},
  title = {Strengths and Weaknesses of Quantum Computing},
  journal = {SIAM Journal on Computing},
  volume = {26},
  number = {5},
  pages = {1510--1523},
  year = {1997},
  doi = {10.1137/S0097539796300933},
  eprint = {quant-ph/9701001},
  archivePrefix = {arXiv}
}

@inproceedings{GPW15,
  author = {Mika G{\"o}{\"o}s and Toniann Pitassi and Thomas Watson},
  title = {Deterministic Communication vs. Partition Number},
  booktitle = {Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science},
  pages = {1077--1088},
  year = {2015},
  publisher = {IEEE},
  doi = {10.1109/FOCS.2015.70}
}

@article{ABBLSS17,
  author = {Andris Ambainis and Kaspars Balodis and Aleksandrs Belovs and Troy Lee and Miklos Santha and Juris Smotrovs},
  title = {Separations in Query Complexity Based on Pointer Functions},
  journal = {Journal of the ACM},
  volume = {64},
  number = {5},
  pages = {32:1--32:24},
  year = {2017},
  doi = {10.1145/3106234},
  eprint = {1506.04719},
  archivePrefix = {arXiv}
}

@inproceedings{ABK16,
  author = {Scott Aaronson and Shalev Ben-David and Robin Kothari},
  title = {Separations in Query Complexity Using Cheat Sheets},
  booktitle = {Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing},
  pages = {863--876},
  year = {2016},
  publisher = {ACM},
  doi = {10.1145/2897518.2897644},
  eprint = {1511.01937},
  archivePrefix = {arXiv}
}

@article{AA18,
  author = {Scott Aaronson and Andris Ambainis},
  title = {{Forrelation}: A Problem That Optimally Separates Quantum from Classical Computing},
  journal = {SIAM Journal on Computing},
  volume = {47},
  number = {3},
  pages = {982--1038},
  year = {2018},
  doi = {10.1137/15M1050902},
  eprint = {1411.5729},
  archivePrefix = {arXiv}
}

@inproceedings{Tal20,
  author = {Avishay Tal},
  title = {Towards Optimal Separations between Quantum and Randomized Query Complexities},
  booktitle = {Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science},
  pages = {228--239},
  year = {2020},
  publisher = {IEEE},
  doi = {10.1109/FOCS46700.2020.00030},
  eprint = {1912.12561},
  archivePrefix = {arXiv}
}

@inproceedings{BS21,
  author = {Nikhil Bansal and Makrand Sinha},
  title = {{$k$-Forrelation} Optimally Separates Quantum and Classical Query Complexity},
  booktitle = {Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing},
  pages = {1303--1316},
  year = {2021},
  publisher = {ACM},
  doi = {10.1145/3406325.3451040},
  eprint = {2008.07003},
  archivePrefix = {arXiv}
}

@article{SSW23,
  author = {Alexander A. Sherstov and Andrey A. Storozhenko and Pei Wu},
  title = {An Optimal Separation of Randomized and Quantum Query Complexity},
  journal = {SIAM Journal on Computing},
  volume = {52},
  number = {2},
  pages = {525--567},
  year = {2023},
  doi = {10.1137/22M1468943},
  eprint = {2008.10223},
  archivePrefix = {arXiv},
  note = {Preliminary version in STOC 2021}
}

@inproceedings{ABKRT21,
  author = {Scott Aaronson and Shalev Ben-David and Robin Kothari and Shravas Rao and Avishay Tal},
  title = {Degree vs. Approximate Degree and Quantum Implications of {Huang}'s Sensitivity Theorem},
  booktitle = {Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing},
  pages = {1330--1342},
  year = {2021},
  publisher = {ACM},
  doi = {10.1145/3406325.3451047},
  eprint = {2010.12629},
  archivePrefix = {arXiv}
}

@article{Huang19,
  author = {Hao Huang},
  title = {Induced Subgraphs of Hypercubes and a Proof of the {Sensitivity Conjecture}},
  journal = {Annals of Mathematics},
  volume = {190},
  number = {3},
  pages = {949--955},
  year = {2019},
  doi = {10.4007/annals.2019.190.3.6},
  eprint = {1907.00847},
  archivePrefix = {arXiv}
}

@misc{Midrijanis04,
  author = {Gatis Midrijanis},
  title = {Exact Quantum Query Complexity for Total {Boolean} Functions},
  year = {2004},
  eprint = {quant-ph/0403168},
  archivePrefix = {arXiv},
  note = {arXiv:quant-ph/0403168}
}

@article{Ambainis02,
  author = {Andris Ambainis},
  title = {Quantum Lower Bounds by Quantum Arguments},
  journal = {Journal of Computer and System Sciences},
  volume = {64},
  number = {4},
  pages = {750--767},
  year = {2002},
  doi = {10.1006/jcss.2002.1826},
  eprint = {quant-ph/0002066},
  archivePrefix = {arXiv}
}

@inproceedings{BSS03,
  author = {Howard Barnum and Michael E. Saks and Mario Szegedy},
  title = {Quantum Query Complexity and Semi-Definite Programming},
  booktitle = {Proceedings of the 18th Annual IEEE Conference on Computational Complexity},
  pages = {179--193},
  year = {2003},
  publisher = {IEEE},
  doi = {10.1109/CCC.2003.1214419}
}

@article{SpalekSzegedy06,
  author = {Robert {\v S}palek and Mario Szegedy},
  title = {All Quantum Adversary Methods Are Equivalent},
  journal = {Theory of Computing},
  volume = {2},
  number = {1},
  pages = {1--18},
  year = {2006},
  doi = {10.4086/toc.2006.v002a001},
  eprint = {quant-ph/0409116},
  archivePrefix = {arXiv}
}

@article{Nisan91,
  author = {Noam Nisan},
  title = {{CREW PRAMs} and Decision Trees},
  journal = {SIAM Journal on Computing},
  volume = {20},
  number = {6},
  pages = {999--1007},
  year = {1991},
  doi = {10.1137/0220062}
}

@article{NisanSzegedy94,
  author = {Noam Nisan and Mario Szegedy},
  title = {On the Degree of {Boolean} Functions as Real Polynomials},
  journal = {Computational Complexity},
  volume = {4},
  number = {4},
  pages = {301--313},
  year = {1994},
  doi = {10.1007/BF01263419}
}

@article{BBHT98,
  author = {Michel Boyer and Gilles Brassard and Peter H{\o}yer and Alain Tapp},
  title = {Tight Bounds on Quantum Searching},
  journal = {Fortschritte der Physik},
  volume = {46},
  number = {4--5},
  pages = {493--506},
  year = {1998},
  eprint = {quant-ph/9605034},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/quant-ph/9605034}
}

@incollection{BHMT02,
  author = {Gilles Brassard and Peter H{\o}yer and Michele Mosca and Alain Tapp},
  title = {Quantum Amplitude Amplification and Estimation},
  booktitle = {Quantum Computation and Quantum Information},
  editor = {Lomonaco, Jr., Samuel J.},
  series = {Contemporary Mathematics},
  volume = {305},
  pages = {53--74},
  year = {2002},
  publisher = {American Mathematical Society},
  doi = {10.1090/conm/305/05215},
  eprint = {quant-ph/0005055},
  archivePrefix = {arXiv}
}

@misc{DurrHoyer96,
  author = {Christoph D{\"u}rr and Peter H{\o}yer},
  title = {A Quantum Algorithm for Finding the Minimum},
  year = {1996},
  eprint = {quant-ph/9607014},
  archivePrefix = {arXiv},
  note = {arXiv:quant-ph/9607014}
}

@inproceedings{SYZ04,
  author = {Xiaoming Sun and Andrew C. Yao and Shengyu Zhang},
  title = {Graph Properties and Circular Functions: How Low Can Quantum Query Complexity Go?},
  booktitle = {Proceedings of the 19th Annual IEEE Conference on Computational Complexity},
  pages = {286--293},
  year = {2004},
  publisher = {IEEE},
  doi = {10.1109/CCC.2004.1313851}
}

@inproceedings{MPS23,
  author = {Nikhil S. Mande and Manaswi Paraashar and Nitin Saurabh},
  title = {Randomized and Quantum Query Complexities of Finding a King in a Tournament},
  booktitle = {43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  series = {Leibniz International Proceedings in Informatics},
  volume = {284},
  pages = {30:1--30:19},
  year = {2023},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  doi = {10.4230/LIPIcs.FSTTCS.2023.30},
  eprint = {2308.02472},
  archivePrefix = {arXiv}
}

@misc{BK26,
  author = {Shalev Ben-David and Robin Kothari},
  title = {Randomized Query Complexity Can Beat Certificate Complexity},
  year = {2026},
  eprint = {2609.15063},
  archivePrefix = {arXiv},
  note = {arXiv:2609.15063}
}

@misc{AIK26,
  author = {Andris Ambainis and J{\=a}nis Iraids and Martins Kokainis},
  title = {Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity},
  year = {2026},
  eprint = {2609.11664},
  archivePrefix = {arXiv},
  note = {arXiv:2609.11664v2}
}

@article{Shaltiel03,
  author = {Ronen Shaltiel},
  title = {Towards Proving Strong Direct Product Theorems},
  journal = {Computational Complexity},
  volume = {12},
  number = {1--2},
  pages = {1--22},
  year = {2003},
  doi = {10.1007/s00037-003-0175-x}
}

@article{Drucker12,
  author = {Andrew Drucker},
  title = {Improved Direct Product Theorems for Randomized Query Complexity},
  journal = {Computational Complexity},
  volume = {21},
  number = {2},
  pages = {197--244},
  year = {2012},
  doi = {10.1007/s00037-012-0043-7},
  eprint = {1005.0644},
  archivePrefix = {arXiv}
}

@inproceedings{Yao77,
  author = {Andrew Chi-Chih Yao},
  title = {Probabilistic Computations: Toward a Unified Measure of Complexity},
  booktitle = {Proceedings of the 18th Annual Symposium on Foundations of Computer Science},
  pages = {222--227},
  year = {1977},
  publisher = {IEEE},
  doi = {10.1109/SFCS.1977.24}
}