% Generated from data/catalog.json. Preserve the source JSON as authoritative.
% Preprint entries do not imply absence of a later published version.

@article{BdW02,
  author = {Harry Buhrman and Ronald de Wolf},
  title = {{Complexity measures and decision tree complexity: a survey}},
  year = {2002},
  journal = {Theoretical Computer Science},
  volume = {288},
  number = {1},
  pages = {21--43},
  doi = {10.1016/S0304-3975(01)00144-X},
  url = {https://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf},
  note = {Inspected source: SHA-256 7002019660c498b652611acf5cdbe264ea9c4a139f8f4da6e82e12822e5d9122; downloaded 2026-10-17}
}

@article{HKP11,
  author = {Pooya Hatami and Raghav Kulkarni and Denis Pankratov},
  title = {{Variations on the Sensitivity Conjecture}},
  year = {2011},
  journal = {Theory of Computing Library, Graduate Surveys},
  volume = {4},
  pages = {1--27},
  doi = {10.4086/toc.gs.2011.004},
  url = {https://tocmirror.cs.uchicago.edu/articles/gs004/},
  eprint = {1011.0354},
  archivePrefix = {arXiv},
  note = {Inspected source: SHA-256 dc988b3171d00dda91d609f3dd0758f9f6b08da58e11302ca454abcf4f694ede; downloaded 2026-10-17}
}

@misc{Amb18,
  author = {Andris Ambainis},
  title = {{Understanding Quantum Algorithms via Query Complexity}},
  year = {2017},
  url = {https://arxiv.org/abs/1712.06349},
  eprint = {1712.06349},
  archivePrefix = {arXiv},
  note = {Inspected source: SHA-256 6d2bfa659d7d29617635627ec6ab998b984cec6b5c8ef5cca8db69e226f40f80; downloaded 2026-10-17}
}

@article{BT22,
  author = {Mark Bun and Justin Thaler},
  title = {{Approximate Degree in Classical and Quantum Computing}},
  year = {2022},
  journal = {Foundations and Trends in Theoretical Computer Science},
  volume = {15},
  number = {3--4},
  pages = {229--423},
  doi = {10.1561/0400000107},
  url = {https://open.bu.edu/items/88330d18-3f1f-4fc4-8552-17e432f8475f},
  note = {Preferred citation on repository cover uses 2022; repository deposit is dated 2023. Author manuscript pagination differs from journal pagination.; Inspected source: OpenBU author manuscript, 15 December 2022; 124 PDF pages including repository cover}
}

@article{Nis91,
  author = {Noam Nisan},
  title = {{CREW PRAMs and Decision Trees}},
  year = {1991},
  journal = {SIAM Journal on Computing},
  volume = {20},
  number = {6},
  pages = {999--1007},
  doi = {10.1137/0220062},
  url = {https://epubs.siam.org/doi/10.1137/0220062},
  note = {Inspected source: Journal full text still not inspected. Original conference predecessor Nis89 is now available and checked separately.}
}

@article{NS94,
  author = {Noam Nisan and Mario Szegedy},
  title = {{On the degree of Boolean functions as real polynomials}},
  year = {1994},
  journal = {Computational Complexity},
  volume = {4},
  number = {4},
  pages = {301--313},
  doi = {10.1007/BF01263419},
  url = {https://web.vu.lt/mif/s.jukna/boolean/Nisan-Szegedy.pdf},
  note = {Inspected source: SHA-256 059743f397f0a148e9117ee2f7762bd9a73b80b023c033ffca1e5fae6c2f9abe; downloaded 2026-10-17}
}

@article{BBCMW01,
  author = {Robert Beals and Harry Buhrman and Richard Cleve and Michele Mosca and Ronald de Wolf},
  title = {{Quantum lower bounds by polynomials}},
  year = {2001},
  journal = {Journal of the ACM},
  volume = {48},
  number = {4},
  pages = {778--797},
  doi = {10.1145/502090.502097},
  url = {https://arxiv.org/abs/quant-ph/9802049},
  eprint = {quant-ph/9802049},
  archivePrefix = {arXiv},
  note = {Inspected source: quant-ph/9802049v3}
}

@misc{Mid04,
  author = {Gatis Midrijanis},
  title = {{Exact quantum query complexity for total Boolean functions}},
  year = {2004},
  url = {https://arxiv.org/abs/quant-ph/0403168},
  eprint = {quant-ph/0403168},
  archivePrefix = {arXiv},
  note = {Inspected source: quant-ph/0403168v2}
}

@article{Aar02,
  author = {Scott Aaronson},
  title = {{Quantum Certificate Complexity}},
  year = {2008},
  journal = {Journal of Computer and System Sciences},
  volume = {74},
  number = {3},
  pages = {313--322},
  doi = {10.1016/j.jcss.2007.06.020},
  url = {https://arxiv.org/abs/quant-ph/0210020},
  eprint = {quant-ph/0210020},
  archivePrefix = {arXiv},
  note = {Stable key retained. Original preprint 2002; CCC 2003 version; journal 2008. Do not use the erroneous SIAM citation in the 2015 cheat-sheet preprint. Later 12-page author manuscript inspected separately: footnote 3 explicitly corrects a false superfluous claim in the old Theorem 10 proof. Do not identify it as the 10-page journal PDF.; Inspected source: quant-ph/0210020v1}
}

@article{KT13,
  author = {Raghav Kulkarni and Avishay Tal},
  title = {{On Fractional Block Sensitivity}},
  year = {2016},
  journal = {Chicago Journal of Theoretical Computer Science},
  volume = {2016},
  number = {8},
  pages = {1--16},
  doi = {10.4086/cjtcs.2016.008},
  url = {https://eccc.weizmann.ac.il/report/2013/168/},
  note = {ECCC TR13-168, revision 1 (30 November 2013); Stable key retains original report year. Proof locators currently refer to the 2013 ECCC PDF; final journal metadata checked independently. Final-version theorem-number reconciliation is explicit.; Inspected source: ECCC TR13-168 revision 1}
}

@inproceedings{ABK16,
  author = {Scott Aaronson and Shalev Ben-David and Robin Kothari},
  title = {{Separations in query complexity using cheat sheets}},
  year = {2016},
  booktitle = {Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016)},
  publisher = {ACM},
  pages = {863--876},
  doi = {10.1145/2897518.2897644},
  url = {https://arxiv.org/abs/1511.01937},
  eprint = {1511.01937},
  archivePrefix = {arXiv},
  note = {Inspected source: PDF retrieved 2026-10-17; pin revision before final audit}
}

@article{ABBLS17,
  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}},
  year = {2017},
  journal = {Journal of the ACM},
  volume = {64},
  number = {5},
  pages = {1--24},
  doi = {10.1145/3106234},
  url = {https://arxiv.org/abs/1506.04719},
  eprint = {1506.04719},
  archivePrefix = {arXiv},
  note = {Publisher metadata reports 24 article pages; article 32. Conference version STOC 2016, pp.800–813, DOI 10.1145/2897518.2897524.; Article 32; Inspected source: SHA-256 1b7803487ac696b1f8d81ee7bc26d55ed7a3c4ff4b78928faa269b71358fe66c; downloaded 2026-10-17}
}

@article{Hua19,
  author = {Hao Huang},
  title = {{Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture}},
  year = {2019},
  journal = {Annals of Mathematics},
  volume = {190},
  number = {3},
  pages = {949--955},
  doi = {10.4007/annals.2019.190.3.6},
  url = {https://arxiv.org/abs/1907.00847},
  eprint = {1907.00847},
  archivePrefix = {arXiv},
  note = {Publisher-deposited metadata checked.; Inspected source: SHA-256 9193d2dac7b3f6b6a84270884c6143913ae5a0ba9bf3db19273f9703db0ed6a2; downloaded 2026-10-17}
}

@inproceedings{ABKBRT21,
  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}},
  year = {2021},
  booktitle = {Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021)},
  publisher = {ACM},
  pages = {1330--1342},
  doi = {10.1145/3406325.3451047},
  url = {https://arxiv.org/abs/2010.12629},
  eprint = {2010.12629},
  archivePrefix = {arXiv},
  note = {Inspected source: 32-page arXiv PDF retrieved 2026-10-17; revision pin pending}
}

@article{SSW20,
  author = {Alexander A. Sherstov and Andrey A. Storozhenko and Pei Wu},
  title = {{An Optimal Separation of Randomized and Quantum Query Complexity}},
  year = {2023},
  journal = {SIAM Journal on Computing},
  volume = {52},
  number = {2},
  pages = {525--567},
  doi = {10.1137/22M1468943},
  url = {https://arxiv.org/abs/2008.10223},
  eprint = {2008.10223},
  archivePrefix = {arXiv},
  note = {Stable key reflects original preprint year 2020; canonical publication is 2023.; Inspected source: 2008.10223v4}
}

@inproceedings{BK19,
  author = {Shalev Ben-David and Robin Kothari},
  title = {{Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge}},
  year = {2019},
  booktitle = {14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {Leibniz International Proceedings in Informatics},
  volume = {135},
  pages = {2:1--2:23},
  doi = {10.4230/LIPIcs.TQC.2019.2},
  url = {https://arxiv.org/abs/1902.03660},
  eprint = {1902.03660},
  archivePrefix = {arXiv},
  note = {TQC 2019 version exists; reconcile proceedings metadata.; Inspected source: SHA-256 91e8000b3876342b789180762b8770ae5bd13e324cb56bc07bf42d07159d6f32; downloaded 2026-10-17}
}

@misc{IJKKSWW23,
  author = {Vishnu Iyer and Siddhartha Jain and Robin Kothari and Matt Kovacs-Deak and Vinayak M. Kumar and Luke Schaeffer and Daochen Wang and Michael Whitmeyer},
  title = {{On the Rational Degree of Boolean Functions and Applications}},
  year = {2023},
  url = {https://arxiv.org/abs/2310.08004},
  eprint = {2310.08004},
  archivePrefix = {arXiv},
  note = {Citation year is original preprint year; inspected revision is dated 2025. Main-text Proposition 6, not stale abstract metadata, governs the stored symmetric constant.; Inspected source: 2310.08004v2, 14 April 2025; PDF author list checked}
}

@misc{BK24,
  author = {Shalev Ben-David and Srijita Kundu},
  title = {{Separations in query complexity for total search problems}},
  year = {2024},
  url = {https://arxiv.org/abs/2410.16245},
  eprint = {2410.16245},
  archivePrefix = {arXiv},
  note = {Inspected source: 2410.16245v1}
}

@misc{CG22,
  author = {Sourav Chakraborty and Anna Gál and Mika Göös and Sophie Laplante and Rajat Mittal and Anupa Sunny},
  title = {{Certificate Games and Consequences for the Classical Adversary Bound}},
  year = {2025},
  url = {https://arxiv.org/abs/2211.03396},
  eprint = {2211.03396},
  archivePrefix = {arXiv},
  note = {Stable citation key retains the original preprint year 2022. This entry cites the six-author v3 of 10 March 2025 under its revised title. The five-author ITCS 2023 publication is a separate entry CG23proceedings.; Inspected source: 2211.03396v3 (10 March 2025)}
}

@misc{KLW14,
  author = {Jędrzej Kaniewski and Troy Lee and Ronald de Wolf},
  title = {{Query complexity in expectation}},
  year = {2014},
  url = {https://arxiv.org/abs/1411.7280},
  eprint = {1411.7280},
  archivePrefix = {arXiv},
  note = {Inspected source: SHA-256 f37b8913b8d0f547159870a6587f98867b138d2caa5d84a417bda8b00ce745db; downloaded 2026-10-17}
}

@misc{AIK26,
  author = {Andris Ambainis and Jānis Iraids and Martins Kokainis},
  title = {{Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity}},
  year = {2026},
  url = {https://arxiv.org/abs/2609.11664},
  eprint = {2609.11664},
  archivePrefix = {arXiv},
  note = {Inspected source: 2609.11664v3}
}

@misc{BK26,
  author = {Shalev Ben-David and Robin Kothari},
  title = {{Randomized query complexity can beat certificate complexity}},
  year = {2026},
  url = {https://arxiv.org/abs/2609.15063},
  eprint = {2609.15063},
  archivePrefix = {arXiv},
  note = {Inspected source: 2609.15063v1}
}

@misc{KLLPV26,
  author = {Chandrima Kayal and Sophie Laplante and Émile Larroque and Krišjānis Prūsis and Jevgēnijs Vihrovs},
  title = {{Certification complexity of Boolean functions}},
  year = {2026},
  url = {https://arxiv.org/abs/2609.26757},
  eprint = {2609.26757},
  archivePrefix = {arXiv},
  note = {Inspected source: SHA-256 c0d8a867c70fc3691ac930c6cc49ab62013c7f4980d05f83f4fbc86c3e66a8a4; downloaded 2026-10-17}
}

@inproceedings{AGL26,
  author = {Hugo Aaronson and Tom Gur and Jiawei Li},
  title = {{Pseudo-deterministic Quantum Algorithms}},
  year = {2026},
  booktitle = {53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {LIPIcs},
  volume = {374},
  pages = {3:1--3:22},
  doi = {10.4230/LIPIcs.ICALP.2026.3},
  url = {https://doi.org/10.4230/LIPIcs.ICALP.2026.3},
  eprint = {2602.17647},
  archivePrefix = {arXiv},
  note = {Preprint and final proceedings both inspected; Theorems 1, 3, 4, 5 and 37 use final numbering.; Full preprint and ICALP proceedings differ in theorem numbering; each claim states the inspected version.; Inspected source: ICALP 2026 proceedings, 22 pages, plus full arXiv preprint, 29 pages; claim locators distinguish these versions.}
}

@inproceedings{CG26,
  author = {Sourav Chakraborty and Anna Gál},
  title = {{Nearly Tight Bounds on the Block Number of Boolean Functions in Terms of Sensitivity}},
  year = {2026},
  booktitle = {51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume = {386},
  pages = {61:1--61:17},
  doi = {10.4230/LIPIcs.MFCS.2026.61},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.61},
  note = {Publisher BibTeX checked.; Inspected source: MFCS 2026 final PDF, 17 pages}
}

@misc{ARS26,
  author = {Mehil Agarwal and Shravas Rao and Fang Song},
  title = {{Noisy Quantum Query Complexity via Fractional Block Sensitivity}},
  year = {2026},
  url = {https://arxiv.org/abs/2610.00506},
  eprint = {2610.00506},
  archivePrefix = {arXiv},
  note = {Inspected source: SHA-256 2fcded93cb40a7623dc038b31988c9a62b4079136889326b0d716485fbbfe0d8; downloaded 2026-10-17}
}

@article{KSP20,
  author = {Rohan Karthikeyan and Siddharth Sinha and Vallabh Patil},
  title = {{On the resolution of the sensitivity conjecture}},
  year = {2020},
  journal = {Bulletin of the American Mathematical Society},
  volume = {57},
  number = {4},
  pages = {615--638},
  doi = {10.1090/bull/1697},
  url = {https://arxiv.org/abs/1912.05406},
  eprint = {1912.05406},
  archivePrefix = {arXiv},
  note = {Inspected source: SHA-256 0381cb50624fdfc4e40ca2a6170897ebf0ce781528e5dbe069d446e43f27e48d; downloaded 2026-10-17}
}

@inproceedings{CDM23,
  author = {Arkadev Chattopadhyay and Yogesh Dahiya and Meena Mahajan},
  title = {{Query Complexity of Search Problems}},
  year = {2023},
  booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume = {272},
  pages = {34:1--34:15},
  doi = {10.4230/LIPIcs.MFCS.2023.34},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.34},
  note = {Inspected source: SHA-256 8fd32dafe815f403972bfc4eea028f9a83c1b2cec06ae5d8fe352a91edf29160; downloaded 2026-10-17}
}

@misc{CMP24,
  author = {Arjan Cornelissen and Nikhil S. Mande and Subhasree Patro},
  title = {{Quantum Sabotage Complexity}},
  year = {2024},
  doi = {10.4230/LIPIcs.FSTTCS.2024.19},
  url = {https://arxiv.org/abs/2408.12595},
  eprint = {2408.12595},
  archivePrefix = {arXiv},
  note = {Preprint cited; proceedings version identified by DOI. Model variants differ in access and output.; Inspected source: SHA-256 bbe0a27507b0bf0ed0614fa4c4637377e1dd97dd6168a4eabb9beba26c4d5847; downloaded 2026-10-17}
}

@misc{BJKM24,
  author = {Farzan Byramji and Vatsal Jha and Chandrima Kayal and Rajat Mittal},
  title = {{Relations between monotone complexity measures based on decision tree complexity}},
  year = {2024},
  url = {https://arxiv.org/abs/2406.07859},
  eprint = {2406.07859},
  archivePrefix = {arXiv},
  note = {Inspected source: 2406.07859v2}
}

@misc{BKMNSS25,
  author = {Deepu Benson and Balagopal Komarath and Nikhil Mande and Sai Soumya Nalli and Jayalal Sarma and Karteek Sreenivasaiah},
  title = {{Sensitivity and Query Complexity under Uncertainty}},
  year = {2025},
  url = {https://arxiv.org/abs/2507.00148},
  eprint = {2507.00148},
  archivePrefix = {arXiv},
  note = {Inspected source: 2507.00148v1}
}

@article{DM23,
  author = {Yogesh Dahiya and Meena Mahajan},
  title = {{On (simple) decision tree rank}},
  year = {2023},
  journal = {Theoretical Computer Science},
  volume = {978},
  pages = {114177},
  doi = {10.1016/j.tcs.2023.114177},
  url = {https://www.imsc.res.in/~meena/papers/rank-tcs.pdf},
  eprint = {2209.12877},
  archivePrefix = {arXiv},
  note = {114177 is the article identifier, not a page range.; Inspected source: SHA-256 2c4937c9e93e4c4d786642f441e6f1b37285875aa41189870fb3b0fb2060c7f1; downloaded 2026-10-17}
}

@article{LM26,
  author = {Alison Hsiang-Hsuan Liu and Nikhil S. Mande},
  title = {{Instance complexity of Boolean functions}},
  year = {2026},
  journal = {Discrete Mathematics \& Theoretical Computer Science},
  volume = {28},
  number = {2},
  doi = {10.46298/dmtcs.15917},
  url = {https://dmtcs.episciences.org/en/articles/18512},
  note = {Inspected source: SHA-256 0065fb2761ceea3f60352e1f1a16c228309fc3b6929a8df8418dd1aeb91f23b8; downloaded 2026-10-17}
}

@inproceedings{Tal13,
  author = {Avishay Tal},
  title = {{Properties and Applications of Boolean Function Composition}},
  year = {2013},
  booktitle = {Proceedings of the 4th Conference on Innovations in Theoretical Computer Science (ITCS 2013)},
  publisher = {ACM},
  pages = {441--454},
  doi = {10.1145/2422436.2422485},
  url = {https://eccc.weizmann.ac.il/report/2012/163/},
  note = {ECCC TR12-163; Inspected source: SHA-256 9d59db5e3cf2588196c027173f3e7f058ebf282d1b3ec7721cd6f4915a0d4104; downloaded 2026-10-17}
}

@article{GSS13,
  author = {Justin Gilmer and Michael Saks and Srikanth Srinivasan},
  title = {{Composition limits and separating examples for some Boolean function complexity measures}},
  year = {2016},
  journal = {Combinatorica},
  volume = {36},
  number = {3},
  pages = {265--311},
  doi = {10.1007/s00493-014-3189-x},
  url = {https://arxiv.org/abs/1306.0630},
  eprint = {1306.0630},
  archivePrefix = {arXiv},
  note = {Stable key retains CCC 2013 origin; CCC pp.185–196, DOI 10.1109/CCC.2013.27. Working proof locators refer to arXiv PDF.; Inspected source: SHA-256 e3c66f2ddea294aec9c79fbbff1a0c8177a14dbf1aa4ef0756dec65048073cf9; downloaded 2026-10-17}
}

@misc{Pro21,
  author = {Nikolay V. Proskurin},
  title = {{On Separation between the Degree of a Boolean Function and the Block Sensitivity}},
  year = {2021},
  url = {https://arxiv.org/abs/2101.08600},
  eprint = {2101.08600},
  archivePrefix = {arXiv},
  note = {Inspected source: 2101.08600v2}
}

@misc{Mei26,
  author = {Alexander Meiburg},
  title = {{Block Sensitivity can exceed Spectral Sensitivity Squared}},
  year = {2026},
  url = {https://arxiv.org/abs/2608.00851},
  eprint = {2608.00851},
  archivePrefix = {arXiv},
  note = {Inspected source: 2608.00851v1}
}

@misc{AP14,
  author = {Andris Ambainis and Krišjānis Prūsis},
  title = {{A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity}},
  year = {2014},
  url = {https://arxiv.org/abs/1402.5078},
  eprint = {1402.5078},
  archivePrefix = {arXiv},
  note = {Inspected source: SHA-256 1334bfc283d089dadbcbeddda1c81d3f9670b4b7daa1c2b0cf7b3562e61dad82; downloaded 2026-10-17}
}

@misc{Mid05,
  author = {Gatis Midrijanis},
  title = {{On randomized and quantum query complexities}},
  year = {2005},
  url = {https://arxiv.org/abs/quant-ph/0501142},
  eprint = {quant-ph/0501142},
  archivePrefix = {arXiv},
  note = {Inspected source: SHA-256 b9054a7d926c47f8447933d8b30b6002799eedd083556a696b52c920e8665a94; downloaded 2026-10-17}
}

@misc{OAI26,
  author = {OpenAI},
  title = {{A Nearly Quartic Separation Between Randomized and Quantum Query Complexity}},
  year = {2026},
  url = {https://github.com/openai/math/blob/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/A-Nearly-Quartic-Separation-Between-Randomized-and-Quantum-Query-Complexity-October-5-2026/quartic-query-separation.pdf},
  note = {Corporate author as printed. Theorem and proof route inspected; no claim of journal acceptance or independent full-proof verification.; repository\_preprint; Inspected source: 5 October 2026 PDF at Git commit 1581d4cbdd69a0faf34b2089614fe2a814316a6a}
}

@inproceedings{MNP24,
  author = {Rajat Mittal and Sanjay S. Nair and Sunayana Patro},
  title = {{On query complexity measures and their relations for symmetric functions}},
  year = {2024},
  booktitle = {Algorithms and Discrete Applied Mathematics (CALDAM 2024)},
  publisher = {Springer, Cham},
  series = {Lecture Notes in Computer Science},
  volume = {14508},
  pages = {59--73},
  doi = {10.1007/978-3-031-52213-0_5},
  url = {https://arxiv.org/abs/2110.12616v5},
  eprint = {2110.12616},
  archivePrefix = {arXiv},
  note = {Publication metadata checked against Springer. Proof locators refer to the longer arXiv v5, not necessarily to the proceedings numbering.; CALDAM 2024, pp.59–73; Inspected source: 2110.12616v5, 19 February 2024}
}

@article{Wel22,
  author = {Jake Wellens},
  title = {{Relationships between the number of inputs and other complexity measures of Boolean functions}},
  year = {2022},
  journal = {Discrete Analysis},
  volume = {2022},
  pages = {1--21},
  doi = {10.19086/da.57741},
  url = {https://arxiv.org/abs/2005.00566v2},
  eprint = {2005.00566},
  archivePrefix = {arXiv},
  note = {Article 19; Inspected source: 2005.00566v2; final publication printed in PDF}
}

@misc{CPS22,
  author = {Rahul Chugh and Supartha Podder and Swagato Sanyal},
  title = {{Decision Tree Complexity versus Block Sensitivity and Degree}},
  year = {2022},
  url = {https://arxiv.org/abs/2209.08042},
  eprint = {2209.08042},
  archivePrefix = {arXiv}
}

@inproceedings{BHT17,
  author = {Shalev Ben-David and Pooya Hatami and Avishay Tal},
  title = {{Low-Sensitivity Functions from Unambiguous Certificates}},
  year = {2017},
  booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {Leibniz International Proceedings in Informatics},
  volume = {67},
  pages = {28:1--28:23},
  doi = {10.4230/LIPIcs.ITCS.2017.28},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.28}
}

@misc{AS11,
  author = {Andris Ambainis and Xiaoming Sun},
  title = {{New separation between s(f) and bs(f)}},
  year = {2011},
  url = {https://eccc.weizmann.ac.il/report/2011/116/},
  note = {ECCC TR11-116}
}

@inproceedings{LNS20,
  author = {Sophie Laplante and Reza Naserasr and Anupa Sunny},
  title = {{Sensitivity Lower Bounds from Linear Dependencies}},
  year = {2020},
  booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {Leibniz International Proceedings in Informatics},
  volume = {170},
  pages = {62:1--62:14},
  doi = {10.4230/LIPIcs.MFCS.2020.62},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.62}
}

@inproceedings{BS21,
  author = {Nikhil Bansal and Makrand Sinha},
  title = {{k-Forrelation optimally separates quantum and classical query complexity}},
  year = {2021},
  booktitle = {Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021)},
  publisher = {Association for Computing Machinery},
  pages = {1303--1316},
  doi = {10.1145/3406325.3451040},
  url = {https://arxiv.org/abs/2008.07003},
  eprint = {2008.07003},
  archivePrefix = {arXiv},
  note = {Publication metadata checked against the CWI institutional record and final author PDF; original preprint 2020.}
}

@misc{APV18,
  author = {Andris Ambainis and Krišjānis Prūsis and Jevgēnijs Vihrovs},
  title = {{On Block Sensitivity and Fractional Block Sensitivity}},
  year = {2018},
  url = {https://arxiv.org/abs/1810.02393},
  eprint = {1810.02393},
  archivePrefix = {arXiv},
  note = {Inspected source: 1810.02393v1}
}

@misc{KKWY26,
  author = {Robin Kothari and Matt Kovacs-Deak and Daochen Wang and Rain Zimin Yang},
  title = {{Rational degree is polynomially related to degree}},
  year = {2026},
  url = {https://arxiv.org/abs/2601.08727v3},
  eprint = {2601.08727},
  archivePrefix = {arXiv},
  note = {FOCS\_2026\_to\_appear\_as\_reported\_by\_authors; Inspected source: 2601.08727v3, 28 September 2026}
}

@inproceedings{CG23proceedings,
  author = {Sourav Chakraborty and Anna Gál and Sophie Laplante and Rajat Mittal and Anupa Sunny},
  title = {{Certificate Games}},
  year = {2023},
  booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {Leibniz International Proceedings in Informatics},
  volume = {251},
  pages = {32:1--32:24},
  doi = {10.4230/LIPIcs.ITCS.2023.32},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.32},
  note = {Five-author proceedings version, distinct from six-author revised preprint CG22.}
}

@article{Aar21survey,
  author = {Scott Aaronson},
  title = {{Open Problems Related to Quantum Query Complexity}},
  year = {2021},
  journal = {ACM Transactions on Quantum Computing},
  volume = {2},
  number = {4},
  pages = {14:1--14:9},
  doi = {10.1145/3488559},
  url = {https://www.scottaaronson.com/papers/open.pdf},
  eprint = {2109.06917},
  archivePrefix = {arXiv},
  note = {Article 14}
}

@article{HS05survey,
  author = {Peter Høyer and Robert Špalek},
  title = {{Lower Bounds on Quantum Query Complexity}},
  year = {2005},
  journal = {Bulletin of the European Association for Theoretical Computer Science},
  volume = {87},
  pages = {78--103},
  url = {https://arxiv.org/abs/quant-ph/0509153},
  eprint = {quant-ph/0509153},
  archivePrefix = {arXiv}
}

@article{Amb13,
  author = {Andris Ambainis},
  title = {{Superlinear Advantage for Exact Quantum Algorithms}},
  year = {2016},
  journal = {SIAM Journal on Computing},
  volume = {45},
  number = {2},
  pages = {617--631},
  doi = {10.1137/130939043},
  url = {https://arxiv.org/abs/1211.0721v6},
  eprint = {1211.0721},
  archivePrefix = {arXiv},
  note = {STOC 2013 origin, pp.891–900, DOI 10.1145/2488608.2488721. Stable key retains conference year.; Inspected source: arXiv v6, 9 July 2014; theorem/proof locators refer to that version}
}

@inproceedings{BT17,
  author = {Mark Bun and Justin Thaler},
  title = {{A Nearly Optimal Lower Bound on the Approximate Degree of AC\textasciicircum{}0}},
  year = {2017},
  booktitle = {58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017)},
  publisher = {IEEE},
  pages = {1--12},
  doi = {10.1109/FOCS.2017.10},
  url = {https://arxiv.org/abs/1703.05784},
  eprint = {1703.05784},
  archivePrefix = {arXiv},
  note = {Inspected source: arXiv original manuscript, 40 PDF pages; Theorem 38 / Section 5.2.2}
}

@article{GPW18,
  author = {Mika Göös and Toniann Pitassi and Thomas Watson},
  title = {{Deterministic Communication vs. Partition Number}},
  year = {2018},
  journal = {SIAM Journal on Computing},
  volume = {47},
  number = {6},
  pages = {2435--2450},
  doi = {10.1137/16M1059369},
  url = {https://eccc.weizmann.ac.il/report/2015/050/revision/1/},
  note = {Earlier FOCS 2015 version, pp.1077–1088, DOI 10.1109/FOCS.2015.70.; Inspected source: ECCC TR15-050 revision 1, manuscript dated 5 September 2017, deposited 15 May 2018}
}

@article{GJPW18,
  author = {Mika Göös and T. S. Jayram and Toniann Pitassi and Thomas Watson},
  title = {{Randomized Communication versus Partition Number}},
  year = {2018},
  journal = {ACM Transactions on Computation Theory},
  volume = {10},
  number = {1},
  pages = {4:1--4:20},
  doi = {10.1145/3170711},
  url = {https://eccc.weizmann.ac.il/report/2015/169/},
  note = {The original report title uses vs. rather than versus; proof locators below refer to that report, not necessarily journal numbering.; Article 4; Inspected source: ECCC TR15-169 original report, 20 PDF pages}
}

@inproceedings{AKK16,
  author = {Andris Ambainis and Martins Kokainis and Robin Kothari},
  title = {{Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions}},
  year = {2016},
  booktitle = {31st Conference on Computational Complexity (CCC 2016)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {Leibniz International Proceedings in Informatics},
  volume = {50},
  pages = {4:1--4:14},
  doi = {10.4230/LIPIcs.CCC.2016.4},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.4},
  note = {ECCC TR15-195 original is a single-author Robin Kothari version. Do not assign the final author list to that original version.; Inspected source: Three-author final proceedings PDF}
}

@article{NW95,
  author = {Noam Nisan and Avi Wigderson},
  title = {{On Rank vs. Communication Complexity}},
  year = {1995},
  journal = {Combinatorica},
  volume = {15},
  number = {4},
  pages = {557--565},
  doi = {10.1007/BF01192527},
  url = {https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/RANK/journal.pdf},
  note = {The Kushilevitz degree-3 six-variable gadget is attributed to Eyal Kushilevitz, private communication (1994), in this paper; no invented separate publication.}
}

@misc{Bal21,
  author = {Kaspars Balodis},
  title = {{Several Separations Based on a Partial Boolean Function}},
  year = {2021},
  url = {https://arxiv.org/abs/2103.05593v1},
  eprint = {2103.05593},
  archivePrefix = {arXiv},
  note = {A later joint paper incorporates the improvement; see BBGJK21, whose author list and title differ from the original BGJK preprint.; Inspected source: v1, 9 March 2021}
}

@article{BBGJK21,
  author = {Kaspars Balodis and Shalev Ben-David and Mika Göös and Siddhartha Jain and Robin Kothari},
  title = {{Unambiguous DNFs and Alon-Saks-Seymour}},
  year = {2023},
  journal = {SIAM Journal on Computing},
  pages = {FOCS21-157--FOCS21-173},
  doi = {10.1137/22M1480616},
  url = {https://arxiv.org/abs/2102.08348v2},
  eprint = {2102.08348},
  archivePrefix = {arXiv},
  note = {SIAM journal version published 2023; publisher still lists the special-section article without a numeric volume. FOCS 2021 version pp.116–124, DOI 10.1109/FOCS52979.2021.00020. Proof locators refer to arXiv v2, not necessarily final journal numbering. v1 had four authors and the title Unambiguous DNFs from Hex.; Inspected source: v2, 5 June 2021, 15 PDF pages}
}

@misc{Pab26,
  author = {Chirag Pabbaraju},
  title = {{Optimal Unambiguous DNFs and Alon-Saks-Seymour}},
  year = {2026},
  url = {https://arxiv.org/abs/2608.02533v2},
  eprint = {2608.02533},
  archivePrefix = {arXiv},
  note = {Cited as a 2026 preprint; do not invent future proceedings metadata.; SODA\_2027\_camera\_ready\_as\_reported\_by\_author; Inspected source: v2, 15 October 2026 (manuscript dated 16 October), 41 PDF pages}
}

@misc{Bal26,
  author = {Kaspars Balodis},
  title = {{An Optimal Separation Between Certificate Complexity and Approximate Degree}},
  year = {2026},
  url = {https://arxiv.org/abs/2608.30351v1},
  eprint = {2608.30351},
  archivePrefix = {arXiv},
  note = {arxiv\_preprint; Inspected source: v1, 31 August 2026, 17 PDF pages}
}

@inproceedings{SW86,
  author = {Michael Saks and Avi Wigderson},
  title = {{Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees}},
  year = {1986},
  booktitle = {27th Annual Symposium on Foundations of Computer Science (FOCS 1986)},
  publisher = {IEEE},
  pages = {29--38},
  doi = {10.1109/SFCS.1986.44},
  url = {https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SW86/SW86.pdf},
  note = {Inspected source: Original scanned proceedings; pp.29–31 visually inspected}
}

@inproceedings{Nis89,
  author = {Noam Nisan},
  title = {{CREW PRAMS and Decision Trees}},
  year = {1989},
  booktitle = {Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing (STOC 1989)},
  publisher = {Association for Computing Machinery},
  pages = {327--335},
  doi = {10.1145/73007.73038},
  url = {https://doi.org/10.1145/73007.73038},
  note = {Original obtained from user. R\_1 is expected query cost with false positives forbidden and acceptance at least 1/2 on 1-inputs; R\_2 is expected query cost with two-sided error at most 1/4. Do not identify its constants with default capped R at error 1/3.; Expanded journal version Nis91, SIAM Journal on Computing 20(6), 999–1007 (1991).; Inspected source: User-supplied original STOC 1989 pp.327–335; Section 1.2, Lemmas 2.4–2.5 and 4.1–4.2, Theorems 3–4; pp.329,333–334 visually checked.}
}

@misc{Kothari15,
  author = {Robin Kothari},
  title = {{Nearly optimal separations between communication (or query) complexity and partitions}},
  year = {2015},
  url = {https://eccc.weizmann.ac.il/report/2015/195/},
  note = {ECCC TR15-195; Predecessor of the three-author CCC 2016 paper AKK16; do not merge author lists.; Inspected source: Original single-author report, 13 PDF pages}
}

@inproceedings{HLS07,
  author = {Peter Høyer and Troy Lee and Robert Špalek},
  title = {{Negative Weights Make Adversaries Stronger}},
  year = {2007},
  booktitle = {Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (STOC 2007)},
  publisher = {Association for Computing Machinery},
  pages = {526--535},
  doi = {10.1145/1250790.1250867},
  url = {https://arxiv.org/abs/quant-ph/0611054},
  eprint = {quant-ph/0611054},
  archivePrefix = {arXiv},
  note = {Inspected source: arXiv author manuscript, 29 PDF pages; Definitions 1–2 and Theorem 2}
}

@inproceedings{LMRSS11,
  author = {Troy Lee and Rajat Mittal and Ben W. Reichardt and Robert Špalek and Mario Szegedy},
  title = {{Quantum Query Complexity of State Conversion}},
  year = {2011},
  booktitle = {52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011)},
  publisher = {IEEE},
  pages = {344--353},
  doi = {10.1109/FOCS.2011.75},
  url = {https://arxiv.org/abs/1011.3020v2},
  eprint = {1011.3020},
  archivePrefix = {arXiv},
  note = {Inspected source: v2, 23 August 2011; 19 PDF pages}
}

@misc{LS21survey,
  author = {Lily Li and Morgan Shirley},
  title = {{The General Adversary Bound: A Survey}},
  year = {2021},
  url = {https://arxiv.org/abs/2104.06380},
  eprint = {2104.06380},
  archivePrefix = {arXiv},
  note = {Cites the arXiv survey manuscript; abstract and contents inspected, not used to certify a primary theorem.}
}

@inproceedings{AB23,
  author = {Andris Ambainis and Aleksandrs Belovs},
  title = {{An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree}},
  year = {2023},
  booktitle = {38th Computational Complexity Conference (CCC 2023)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {LIPIcs},
  volume = {264},
  pages = {24:1--24:13},
  doi = {10.4230/LIPIcs.CCC.2023.24},
  url = {https://doi.org/10.4230/LIPIcs.CCC.2023.24},
  eprint = {2301.09218},
  archivePrefix = {arXiv},
  note = {Journal version AB25: computational complexity 34(2), article 14, 1–25 (2025), doi:10.1007/s00037-025-00277-4; journal proof text not inspected.}
}

@inproceedings{ABK21,
  author = {Anurag Anshu and Shalev Ben-David and Srijita Kundu},
  title = {{On Query-To-Communication Lifting for Adversary Bounds}},
  year = {2021},
  booktitle = {36th Computational Complexity Conference (CCC 2021)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {LIPIcs},
  volume = {200},
  pages = {30:1--30:39},
  doi = {10.4230/LIPIcs.CCC.2021.30},
  url = {https://doi.org/10.4230/LIPIcs.CCC.2021.30},
  eprint = {2012.03415},
  archivePrefix = {arXiv},
  note = {Theorem and lemma locators used here also occur in the final proceedings. Final Lemma 27 constructs q(x,i)=q\_x(i), not 2q\_x(i) as in arXiv v1; the published constant-one inequality is retained.; Inspected source: CCC 2021 final proceedings, 39 pages. Full preprint v1 also inspected; final version corrects the spurious factor 2 in the weight construction in the proof of Lemma 27.}
}

@inproceedings{AKPV18,
  author = {Andris Ambainis and Martins Kokainis and Krišjānis Prūsis and Jevgēnijs Vihrovs},
  title = {{All Classical Adversary Methods are Equivalent for Total Functions}},
  year = {2018},
  booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {LIPIcs},
  volume = {96},
  pages = {8:1--8:14},
  doi = {10.4230/LIPIcs.STACS.2018.8},
  url = {https://doi.org/10.4230/LIPIcs.STACS.2018.8},
  note = {Four-author proceedings version. Claims checked in the later five-author full preprint are attributed separately to AKPVZ18, not silently to this version.}
}

@misc{AKPVZ18,
  author = {Andris Ambainis and Martins Kokainis and Krišjānis Prūsis and Jevgēnijs Vihrovs and Aleksejs Zajakins},
  title = {{All Classical Adversary Methods are Equivalent for Total Functions}},
  year = {2018},
  url = {https://arxiv.org/abs/1709.08985v3},
  eprint = {1709.08985},
  archivePrefix = {arXiv},
  note = {Four-author STACS 2018 version, DOI 10.4230/LIPIcs.STACS.2018.8; author list and theorem locators are version-dependent; Inspected source: arXiv:1709.08985v3, 12 November 2018, 22 pages}
}

@inproceedings{GIPS21,
  author = {Shafi Goldwasser and Russell Impagliazzo and Toniann Pitassi and Rahul Santhanam},
  title = {{On the Pseudo-Deterministic Query Complexity of NP Search Problems}},
  year = {2021},
  booktitle = {36th Computational Complexity Conference (CCC 2021)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {LIPIcs},
  volume = {200},
  pages = {36:1--36:22},
  doi = {10.4230/LIPIcs.CCC.2021.36},
  url = {https://doi.org/10.4230/LIPIcs.CCC.2021.36}
}

@inproceedings{GS26,
  author = {Uma Girish and Rocco Servedio},
  title = {{Forrelation Is Extremally Hard}},
  year = {2026},
  booktitle = {17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {LIPIcs},
  volume = {362},
  pages = {72:1--72:22},
  doi = {10.4230/LIPIcs.ITCS.2026.72},
  url = {https://doi.org/10.4230/LIPIcs.ITCS.2026.72},
  eprint = {2508.02514},
  archivePrefix = {arXiv}
}

@misc{CDM23full,
  author = {Arkadev Chattopadhyay and Yogesh Dahiya and Meena Mahajan},
  title = {{Query Complexity of Search Problems}},
  year = {2023},
  url = {https://eccc.weizmann.ac.il/report/2023/039/},
  note = {Electronic Colloquium on Computational Complexity, Report TR23-039; MFCS 2023, DOI 10.4230/LIPIcs.MFCS.2023.34; full report contains proofs omitted from the proceedings}
}

@inproceedings{BHMT02,
  author = {Gilles Brassard and Peter Høyer and Michele Mosca and Alain Tapp},
  title = {{Quantum Amplitude Amplification and Estimation}},
  year = {2002},
  booktitle = {Quantum Computation and Information (Washington, DC, 2000)},
  publisher = {American Mathematical Society},
  series = {Contemporary Mathematics},
  volume = {305},
  pages = {53--74},
  doi = {10.1090/conm/305/05215},
  url = {https://arxiv.org/abs/quant-ph/0005055},
  eprint = {quant-ph/0005055},
  archivePrefix = {arXiv},
  note = {Inspected source: arXiv:quant-ph/0005055v1, 15 May 2000; Section 2.1, Theorem 4}
}

@article{DJ92,
  author = {David Deutsch and Richard Jozsa},
  title = {{Rapid Solution of Problems by Quantum Computation}},
  year = {1992},
  journal = {Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences},
  volume = {439},
  number = {1907},
  pages = {553--558},
  doi = {10.1098/rspa.1992.0167},
  url = {https://doi.org/10.1098/rspa.1992.0167},
  note = {Historical algorithm source. The restricted-promise witness in this repository has its own explicit one-phase-query proof; no claim that this is the circuit or exact query count printed in the 1992 article.}
}

@inproceedings{GGR13,
  author = {Oded Goldreich and Shafi Goldwasser and Dana Ron},
  title = {{On the Possibilities and Limitations of Pseudodeterministic Algorithms}},
  year = {2013},
  booktitle = {Proceedings of the 4th Innovations in Theoretical Computer Science Conference (ITCS 2013)},
  publisher = {ACM},
  pages = {127--138},
  doi = {10.1145/2422436.2422453},
  url = {https://www.wisdom.weizmann.ac.il/~oded/p_balg.html},
  note = {Full report: ECCC TR12-101 (2012); Inspected source: Author-hosted full report dated 10 August 2012; Theorem 4.1 and Corollary 4.2}
}

@inproceedings{CDMRS23,
  author = {Arkadev Chattopadhyay and Yogesh Dahiya and Nikhil S. Mande and Jaikumar Radhakrishnan and Swagato Sanyal},
  title = {{Randomized versus Deterministic Decision Tree Size}},
  year = {2023},
  booktitle = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)},
  publisher = {ACM},
  pages = {867--880},
  doi = {10.1145/3564246.3585199},
  url = {https://doi.org/10.1145/3564246.3585199},
  note = {Earlier full report: ECCC TR22-185; Inspected source: Published STOC paper from CWI repository, 14 pages}
}

@article{KLMY21survey,
  author = {Alexander Knop and Shachar Lovett and Sam McGuire and Weiqiang Yuan},
  title = {{Guest Column: Models of Computation between Decision Trees and Communication}},
  year = {2021},
  journal = {ACM SIGACT News},
  volume = {52},
  number = {2},
  pages = {46--70},
  doi = {10.1145/3471469.3471479},
  url = {https://cseweb.ucsd.edu/~shmcguir/papers/KLMYsigact.pdf}
}

@inproceedings{ZPP26,
  author = {Noah Fleming and Stefan Grosser and Siddhartha Jain and Jiawei Li and Hanlin Ren and Morgan Shirley and Weiqiang Yuan},
  title = {{Total Search Problems in ZPP}},
  year = {2026},
  booktitle = {17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {LIPIcs},
  volume = {362},
  pages = {60:1--60:26},
  doi = {10.4230/LIPIcs.ITCS.2026.60},
  url = {https://doi.org/10.4230/LIPIcs.ITCS.2026.60},
  note = {Full version ECCC TR25-204; Inspected source: Final ITCS 2026 proceedings; Definition 14 and Theorem 23}
}

@inproceedings{CMP22,
  author = {Arjan Cornelissen and Nikhil S. Mande and Subhasree Patro},
  title = {{Improved Quantum Query Upper Bounds Based on Classical Decision Trees}},
  year = {2022},
  booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {LIPIcs},
  volume = {250},
  pages = {15:1--15:22},
  doi = {10.4230/LIPIcs.FSTTCS.2022.15},
  url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2022.15},
  eprint = {2203.02968},
  archivePrefix = {arXiv},
  note = {Inspected source: Final FSTTCS proceedings, 22 pages; Theorems 4–8, Corollaries 9 and 27, Claim 12}
}

@article{LL16,
  author = {Cedric Yen-Yu Lin and Han-Hsuan Lin},
  title = {{Upper Bounds on Quantum Query Complexity Inspired by the Elitzur–Vaidman Bomb Tester}},
  year = {2016},
  journal = {Theory of Computing},
  volume = {12},
  number = {18},
  pages = {1--35},
  doi = {10.4086/toc.2016.v012a018},
  url = {https://theoryofcomputing.org/articles/v012a018/},
  eprint = {1410.0932},
  archivePrefix = {arXiv},
  note = {Conference version CCC 2015; Inspected source: Final 2016 journal PDF; Sections 3–5, Theorems 4.1, 5.4 and 5.5}
}

@article{BT20,
  author = {Salman Beigi and Leila Taghavi},
  title = {{Quantum Speedup Based on Classical Decision Trees}},
  year = {2020},
  journal = {Quantum},
  volume = {4},
  pages = {241},
  doi = {10.22331/q-2020-03-02-241},
  url = {https://doi.org/10.22331/q-2020-03-02-241},
  eprint = {1905.13095},
  archivePrefix = {arXiv},
  note = {Inspected source: Published Quantum article; Theorems 2 and 4}
}

@inproceedings{KLMY21,
  author = {Alexander Knop and Shachar Lovett and Sam McGuire and Weiqiang Yuan},
  title = {{Log-Rank and Lifting for AND-Functions}},
  year = {2021},
  booktitle = {Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021)},
  publisher = {ACM},
  pages = {197--208},
  doi = {10.1145/3406325.3450999},
  url = {https://doi.org/10.1145/3406325.3450999},
  eprint = {2010.08994},
  archivePrefix = {arXiv},
  note = {Preprint Definition 2.13 prints smallest p although the LP and use require largest feasible p. The LP normalization is used here. Final theorem numbering may differ.; Inspected source: Author-hosted full preprint dated 22 October 2020, 19 pages; definitions 2.10/2.13, Claim 4.4}
}

@inproceedings{LM19,
  author = {Bruno Loff and Sagnik Mukhopadhyay},
  title = {{Lifting Theorems for Equality}},
  year = {2019},
  booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {LIPIcs},
  volume = {126},
  pages = {50:1--50:19},
  doi = {10.4230/LIPIcs.STACS.2019.50},
  url = {https://doi.org/10.4230/LIPIcs.STACS.2019.50},
  note = {Lemma 11 proof omitted in proceedings; complete short proof inspected in KLMY21 Claim 4.4.; Inspected source: Final STACS proceedings, Definitions 9–10 and Lemma 11}
}

@article{EH89,
  author = {Andrzej Ehrenfeucht and David Haussler},
  title = {{Learning Decision Trees from Random Examples}},
  year = {1989},
  journal = {Information and Computation},
  volume = {82},
  number = {3},
  pages = {231--246},
  doi = {10.1016/0890-5401(89)90001-1},
  url = {https://doi.org/10.1016/0890-5401(89)90001-1},
  note = {Original rank/size attribution and metadata verified in CDMRS23 Proposition 2.11 and bibliography. Original full text not inspected in this pass; do not mark its proof independently source-checked.; Inspected source: User-supplied original Information and Computation 82(3), pp.231–246; Definition p.234, Lemma 1 p.235, Lemma 5 p.239, function rank p.241; relevant pages visually checked.}
}

@misc{DMbasis25,
  author = {Arkadev Chattopadhyay and Yogesh Dahiya and Shachar Lovett},
  title = {{Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis}},
  year = {2025},
  url = {https://eccc.weizmann.ac.il/report/2025/101/},
  eprint = {2507.13963},
  archivePrefix = {arXiv},
  note = {ECCC TR25-101; Most results extended in Restriction Trees for Sparsity and Applications; retain this report for the earlier version and its monotone results.; Inspected source: 32-page ECCC report; Theorem 1.1 and restriction-tree proof route}
}

@misc{Sparse25,
  author = {Arkadev Chattopadhyay and Yogesh Dahiya and Shachar Lovett},
  title = {{Restriction Trees for Sparsity and Applications}},
  year = {2025},
  url = {https://eccc.weizmann.ac.il/report/2025/172/},
  note = {ECCC TR25-172; STOC 2026, doi:10.1145/3798129.3800895. Final proceedings PDF not inspected; theorem numbers in this catalogue refer to the ECCC report.; Inspected source: 37-page ECCC report; Definitions 2.2–2.11, Theorems 4.6–4.7 and 4.12–4.13, Remark 1.2 and Claim 4.15}
}

@misc{CCM26,
  author = {Clément L. Canonne and Kenny Chen and Julián Mestre},
  title = {{The Quantumly Fast and the Classically Forrious}},
  year = {2026},
  url = {https://arxiv.org/abs/2602.07503v2},
  eprint = {2602.07503},
  archivePrefix = {arXiv},
  note = {Version 2 proves a NONADAPTIVE lower bound. Appendix D identifies a gap in the partial-spread construction of version 1; do not reuse the earlier adaptive claim.; Inspected source: arXiv v2, 1 October 2026, manuscript dated 2 October; 34 pages; Theorems 1 and 3, Appendix D}
}

@article{CMP25,
  author = {Arjan Cornelissen and Nikhil S. Mande and Subhasree Patro},
  title = {{Improved Quantum Query Upper Bounds Based on Classical Decision Trees}},
  year = {2025},
  journal = {Quantum},
  volume = {9},
  doi = {10.22331/q-2025-06-23-1777},
  url = {https://doi.org/10.22331/q-2025-06-23-1777},
  eprint = {2203.02968},
  archivePrefix = {arXiv},
  note = {Journal version of CMP22. Randomized relation bound has error 2/5; size counts nodes.; Article 1777; Inspected source: Publisher journal PDF; Theorem 1.3 and Corollary 5.5, including randomized-tree proof}
}

@article{CDM25,
  author = {Arkadev Chattopadhyay and Yogesh Dahiya and Meena Mahajan},
  title = {{Pseudo-Deterministic Query Complexity of Search Problems}},
  year = {2025},
  journal = {computational complexity},
  volume = {34},
  pages = {1--57},
  doi = {10.1007/s00037-025-00266-7},
  url = {https://doi.org/10.1007/s00037-025-00266-7},
  note = {Journal version of CDM23. Publisher HTML abstract says CONJ and ApproxHW, while downloaded article PDF uses (And, Or) and ApproxHamWt. Definitions here follow the pinned PDF, not the HTML abstract.; Article 20; Inspected source: Publisher PDF, published 8 November 2025; 57 pages; Theorems 3.1–3.2, Proposition 6.6 and Lemma 6.9}
}

@article{CHS20,
  author = {John Chiarelli and Pooya Hatami and Michael Saks},
  title = {{An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean Function}},
  year = {2020},
  journal = {Combinatorica},
  volume = {40},
  number = {2},
  pages = {237--244},
  doi = {10.1007/s00493-019-4136-7},
  url = {https://doi.org/10.1007/s00493-019-4136-7},
  eprint = {1801.08564},
  archivePrefix = {arXiv},
  note = {Inspected source: arXiv v3, 19 November 2018, six pages; original theorem and restriction-potential proof; journal metadata separately checked.}
}

@inproceedings{DFLLV21,
  author = {Neta Dafni and Yuval Filmus and Noam Lifshitz and Nathan Lindzey and Marc Vinyals},
  title = {{Complexity Measures on the Symmetric Group and Beyond}},
  year = {2021},
  booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {LIPIcs},
  volume = {185},
  pages = {87:1--87:5},
  doi = {10.4230/LIPIcs.ITCS.2021.87},
  url = {https://doi.org/10.4230/LIPIcs.ITCS.2021.87},
  eprint = {2010.07405},
  archivePrefix = {arXiv},
  note = {Combinatorial Theory 6(2), article 6 (2026), doi:10.5070/C6.68665; final journal proof text not inspected.; Inspected source: Full arXiv v1, 14 October 2020, 59 pages; Section 2.2, Theorem 3.1, Corollary 4.2 and Corollary 5.6. Locators refer to full preprint, not five-page extended abstract.}
}

@article{DFLLV26,
  author = {Neta Dafni and Yuval Filmus and Noam Lifshitz and Nathan Lindzey and Marc Vinyals},
  title = {{Complexity measures on the symmetric group and beyond}},
  year = {2026},
  journal = {Combinatorial Theory},
  volume = {6},
  number = {2},
  pages = {1--60},
  doi = {10.5070/C6.68665},
  url = {https://doi.org/10.5070/C6.68665},
  note = {Article 6; Inspected source: Final Combinatorial Theory 6(2), article 6, published 20 August 2026; 61-page downloaded PDF includes one repository cover plus 60 article pages. Definitions 2.1–2.2, Theorem 3.1, Lemmas 3.5–3.6, Corollaries 4.2–4.3 and 5.6/5.9/5.11, Section 8 checked.}
}

@misc{HKMP26,
  author = {Thomas Huffstutler and Upendra Kapshikar and David Miloschewsky and Supartha Podder},
  title = {{A Framework for Ruling Out Quantum Speedups}},
  year = {2026},
  url = {https://arxiv.org/abs/2603.29256},
  eprint = {2603.29256},
  archivePrefix = {arXiv},
  note = {MFCS 2026 final short version HKMP26final; initial arXiv submission title: From Promises to Totality: A Framework for Ruling Out Quantum Speedups.; Inspected source: arXiv:2603.29256v3, 30 September 2026, 40 pages; Definitions 12–19 and 45, Lemmas 32–35 and 48–51, Theorem 56. Overline-M notation visually checked.}
}

@inproceedings{HKMP26final,
  author = {Thomas Huffstutler and Upendra Kapshikar and David Miloschewsky and Supartha Podder},
  title = {{A Framework for Ruling out Quantum Speedups}},
  year = {2026},
  booktitle = {51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {LIPIcs},
  volume = {386},
  pages = {10:1--10:17},
  doi = {10.4230/LIPIcs.MFCS.2026.10},
  url = {https://doi.org/10.4230/LIPIcs.MFCS.2026.10},
  note = {Inspected source: Final proceedings PDF, 17 pages; proof and theorem numbering differ from the full arXiv version.}
}

@misc{DFLLV22author,
  author = {Neta Dafni and Yuval Filmus and Noam Lifshitz and Nathan Lindzey and Marc Vinyals},
  title = {{Complexity Measures on the Symmetric Group and Beyond}},
  year = {2022},
  url = {https://yuvalfilmus.cs.technion.ac.il/Papers/measures.pdf},
  note = {ITCS 2021 extended abstract DFLLV21; Combinatorial Theory 6(2), article 6 (2026), DFLLV26.; Inspected source: Author-hosted manuscript, 13 May 2022, 62 pages; Theorem 3.1, Corollaries 4.2–4.3 and 5.6/5.9/5.11, Section 9. Not asserted identical to the 2026 journal version.}
}

@article{AB25,
  author = {Andris Ambainis and Aleksandrs Belovs},
  title = {{An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree}},
  year = {2025},
  journal = {computational complexity},
  volume = {34},
  number = {2},
  pages = {1--25},
  doi = {10.1007/s00037-025-00277-4},
  url = {https://doi.org/10.1007/s00037-025-00277-4},
  note = {Online 3 October 2025; print December 2025. Conference proof inspected separately as AB23.; Article 14; Inspected source: Publisher abstract/metadata and author-institution bibliography only; journal full text not obtained.}
}

@article{AA14,
  author = {Scott Aaronson and Andris Ambainis},
  title = {{The Need for Structure in Quantum Speedups}},
  year = {2014},
  journal = {Theory of Computing},
  volume = {10},
  number = {6},
  pages = {133--166},
  doi = {10.4086/toc.2014.v010a006},
  url = {https://theoryofcomputing.org/articles/v010a006/},
  note = {Inspected source: Original journal PDF, 34 pages; Conjectures 1.5/1.7 and 7.1, Theorem 1.8 and appendix equivalence proof.}
}

@misc{GMNR26,
  author = {Uma Girish and Kunal Mittal and Barak Nehoran and Ran Raz},
  title = {{Distributional Variants of the Aaronson–Ambainis Conjecture}},
  year = {2026},
  url = {https://arxiv.org/abs/2609.35327},
  eprint = {2609.35327},
  archivePrefix = {arXiv},
  note = {Inspected source: arXiv:2609.35327v1, 28 September 2026, 23 pages; Definitions 2.4–2.5, Lemma 2.6, Theorems 3.3/4.3 and their proof routes.}
}

@inproceedings{BD16,
  author = {Shalev Ben-David},
  title = {{The Structure of Promises in Quantum Speedups}},
  year = {2016},
  booktitle = {11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {LIPIcs},
  volume = {61},
  pages = {7:1--7:14},
  doi = {10.4230/LIPIcs.TQC.2016.7},
  url = {https://doi.org/10.4230/LIPIcs.TQC.2016.7},
  note = {Inspected source: Original 14-page TQC proceedings; Definition 7, Theorems 5/8/12, Corollary 9 and proof route in Sections 3.2–3.3.}
}

@misc{Goos15,
  author = {Mika Göös},
  title = {{Lower Bounds for Clique vs. Independent Set}},
  year = {2015},
  url = {https://eccc.weizmann.ac.il/report/2015/012/},
  note = {ECCC TR15-012; Original report separately recorded from FOCS 2015 DOI 10.1109/FOCS.2015.69; no journal-version proof comparison asserted.; Inspected source: Original 24 January 2015 report, 13 pages, publisher PDF inspected via browser extraction}
}

@misc{FLLV20notes,
  author = {Yuval Filmus and Noam Lifshitz and Nathan Lindzey and Marc Vinyals},
  title = {{Complexity measures on the symmetric group}},
  year = {2020},
  pages = {1--8},
  url = {https://yuvalfilmus.cs.technion.ac.il/Talks/ComplexityMeasures-HUJI.pdf},
  note = {Four names on this notes cover; do not merge with the later five-author DFLLV paper. Section 7 records a historical hypergraphical-sensitivity question.; Inspected source: Dated June 24, 2020; 8-page author-hosted talk notes, inspected via original PDF extraction}
}

@article{CL12,
  author = {Yuk Hei Chan and Lap Chi Lau},
  title = {{On linear and semidefinite programming relaxations for hypergraph matching}},
  year = {2012},
  journal = {Mathematical Programming},
  volume = {135},
  number = {1–2},
  pages = {123--148},
  doi = {10.1007/s10107-011-0451-5},
  url = {https://cs.uwaterloo.ca/~lapchi/papers/hypergraph.pdf},
  note = {Selected LP integrality-gap attribution checked, not an exhaustive proof audit of all theorems. The authors credit the earlier unweighted result to Füredi (1981), and the weighted result to Füredi–Kahn–Seymour (1993); this record does not assert Chan–Lau priority.; Inspected source: 26-page author-hosted journal-layout manuscript, DOI on first page; publisher metadata checked}
}

@misc{OAIsens26,
  author = {OpenAI},
  title = {{A superquadratic separation between sensitivity and block sensitivity}},
  year = {2026},
  url = {https://github.com/openai/math/blob/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/A-superquadratic-separation-between-sensitivity-and-block-sensitivity-September-25-2026/paper.pdf},
  note = {Corporate author and date are printed on the original. Selected Theorem 1.1, recursive proof route and Corollary 4.3 inspected. Lean files linked by the source have not been rebuilt here. The manuscript credits Meiburg’s tournament architecture; that spectral-sensitivity result alone does not imply this ordinary-sensitivity separation.; repository\_preprint; Inspected source: September 25, 2026 paper, 11 pages, Git commit 1581d4cbdd69a0faf34b2089614fe2a814316a6a}
}

@misc{P2Msens26,
  author = {Prove2Me contributors},
  title = {{Block Sensitivity vs. Sensitivity: campaign and progress record}},
  year = {2026},
  url = {https://prove2.me/campaigns/block-sensitivity-vs-sensitivity},
  note = {Platform-reported formalization status is not an independent Lean build or a journal publication. Snapshot details and per-entry proof-access limits are recorded in data/sensitivity-campaign.json.; Inspected source: HTML snapshot 2026-10-22; SHA-256 72048a3086aab11326884e6337cccf17d7e482032be59ee8b54c412b2c4fce64}
}

@misc{P2Mdepth2026,
  author = {Prove2Me contributors},
  title = {{Block Sensitivity vs. Sensitivity: Depth-20 Improvement}},
  year = {2026},
  url = {https://prove2.me/missions/Block_Sensitivity_vs._Sensitivity%3A_Depth-20_Improvement},
  note = {Platform attests this goal proved. Acceptance/solve dates are distinguished from proposal text. No independent Lean rebuild or completeness of contributor attribution is claimed. See the witness card for proof-access limits.; Inspected source: Public goal page and dated campaign entry, inspected 17 October 2026}
}

@misc{P2M200726,
  author = {Prove2Me contributors},
  title = {{Block Sensitivity vs. Sensitivity: Reach 2.007}},
  year = {2026},
  url = {https://prove2.me/missions/Block_Sensitivity_vs._Sensitivity%3A_Reach_2.007},
  note = {Platform attests this goal proved. Acceptance/solve dates are distinguished from proposal text. No independent Lean rebuild or completeness of contributor attribution is claimed. See the witness card for proof-access limits.; Inspected source: Public goal page and dated campaign entry, inspected 17 October 2026}
}

@misc{P2M2020526,
  author = {Prove2Me contributors},
  title = {{Block Sensitivity vs. Sensitivity: Reach 2.0205}},
  year = {2026},
  url = {https://prove2.me/missions/Block_Sensitivity_vs._Sensitivity%3A_Reach_2.0205},
  note = {Platform attests this goal proved. Acceptance/solve dates are distinguished from proposal text. No independent Lean rebuild or completeness of contributor attribution is claimed. See the witness card for proof-access limits.; Inspected source: Public goal page and dated campaign entry, inspected 17 October 2026}
}

@misc{P2M2039126,
  author = {Prove2Me contributors},
  title = {{Block Sensitivity vs. Sensitivity: α ≥ 2.0391}},
  year = {2026},
  url = {https://prove2.me/missions/Block_Sensitivity_vs._Sensitivity%3A_%CE%B1_%E2%89%A5_2.0391},
  note = {Platform attests this goal proved. Acceptance/solve dates are distinguished from proposal text. No independent Lean rebuild or completeness of contributor attribution is claimed. See the witness card for proof-access limits.; Inspected source: Public goal page and dated campaign entry, inspected 17 October 2026}
}

@misc{P2M20526,
  author = {Prove2Me contributors},
  title = {{Block Sensitivity vs. Sensitivity: Reach 2.05}},
  year = {2026},
  url = {https://prove2.me/missions/Block_Sensitivity_vs._Sensitivity%3A_Reach_2.05},
  note = {Platform attests this goal proved. Acceptance/solve dates are distinguished from proposal text. No independent Lean rebuild or completeness of contributor attribution is claimed. See the witness card for proof-access limits.; Inspected source: Public goal page and dated campaign entry, inspected 17 October 2026}
}

@misc{P2M2063526,
  author = {abhishekdpseok},
  title = {{Campaign exponent 2.0635: separation exponent 2.0635}},
  year = {2026},
  url = {https://prove2.me/theorems/f4a6abf1-69b0-4785-a7d9-cd45649231b2},
  note = {Attribution follows the public source; usernames are retained where no verified full name is supplied. Platform verification is not an independent Lean replay by this atlas. Accepted solution downloads require authentication (HTTP 401).; Inspected source: Public primary statement, construction summary and status, inspected 22 October 2026; HTML SHA-256 88408d3e4f02ea03dfc7c3e5617032d2ef10ae9c750a9fd7acacaea3bb9aff4f}
}

@misc{P2M207526,
  author = {Robin Kothari and Codex},
  title = {{Seven-level nine-predicate certificate: separation exponent 2.075}},
  year = {2026},
  url = {https://prove2.me/theorems/49fdd176-c319-4f1e-b15f-b1fd5130f0bc},
  note = {Attribution follows the public source; usernames are retained where no verified full name is supplied. Platform verification is not an independent Lean replay by this atlas. Accepted solution downloads require authentication (HTTP 401).; Inspected source: Public primary statement, construction summary and status, inspected 22 October 2026; HTML SHA-256 36bb89af56451c29c1af9f81a4d678a994e17cc6b08375d2d75ddd4e729c1105}
}

@misc{P2M208526,
  author = {yousofy and Codex},
  title = {{Eight-layer nine-predicate refinement: separation exponent 2.085}},
  year = {2026},
  url = {https://prove2.me/theorems/7e54a28e-196b-40a3-a2c0-957e75db9e4f},
  note = {Attribution follows the public source; usernames are retained where no verified full name is supplied. Platform verification is not an independent Lean replay by this atlas. Accepted solution downloads require authentication (HTTP 401).; Inspected source: Public primary statement, construction summary and status, inspected 22 October 2026; HTML SHA-256 d0ce42a34dbb78398dfdcc4f4de067978ed14021fdef8c85c4bd835375630434}
}

@misc{P2M211926,
  author = {yousofy and Codex},
  title = {{Periodic two-stage profile invariant: separation exponent 2.119}},
  year = {2026},
  url = {https://prove2.me/theorems/cf005af0-93b2-44c1-991f-ddab41d85874},
  note = {Attribution follows the public source; usernames are retained where no verified full name is supplied. Platform verification is not an independent Lean replay by this atlas. Accepted solution downloads require authentication (HTTP 401).; Inspected source: Public primary statement, construction summary and status, inspected 22 October 2026; HTML SHA-256 ba5dcb59b06115376495e8d5a75357a90a46284a3c24247a3f0a0d8c084af2c9}
}

@misc{P2M2126,
  author = {Prove2Me contributors},
  title = {{Campaign checkpoint 2.10: separation exponent 2.1}},
  year = {2026},
  url = {https://prove2.me/theorems/34794a98-e5bd-4623-ae65-526fc87e9ad1},
  note = {Attribution follows the public source; usernames are retained where no verified full name is supplied. Platform verification is not an independent Lean replay by this atlas. Accepted solution downloads require authentication (HTTP 401).; Inspected source: Public primary statement, construction summary and status, inspected 22 October 2026; HTML SHA-256 2943cda457ad6e48a1603c273a6f77c63746fb58901c6177970a31d733ae7202}
}

@misc{P2M212729426,
  author = {Prove2Me contributors},
  title = {{Block Sensitivity vs. Sensitivity: Reach 2.127294}},
  year = {2026},
  url = {https://prove2.me/missions/Block_Sensitivity_vs._Sensitivity%3A_Reach_2.127294},
  note = {Attribution follows the public source; usernames are retained where no verified full name is supplied. Platform verification is not an independent Lean replay by this atlas. Accepted solution downloads require authentication (HTTP 401).; Inspected source: Public primary statement, construction summary and status, inspected 22 October 2026; HTML SHA-256 cb9002045a2182ee2fbcb0a63b3b3fd452c41ddeb68ef51d51af322fd12ee504}
}

@misc{P2M2130126,
  author = {yousofy and Codex},
  title = {{Coupled target and guard profiles: separation exponent 2.1301}},
  year = {2026},
  url = {https://prove2.me/theorems/ff7ef69d-ca91-413b-872c-cf760dc244dc},
  note = {Attribution follows the public source; usernames are retained where no verified full name is supplied. Platform verification is not an independent Lean replay by this atlas. Accepted solution downloads require authentication (HTTP 401).; Inspected source: Public primary statement, construction summary and status, inspected 22 October 2026; HTML SHA-256 afe0fcf432ddadd353772d99175525551957c24c6002c2ee2303d0d2d888622e}
}

@misc{P2M2130326,
  author = {yousofy and Codex},
  title = {{Shared local-lemma labeling, four-stage cycle: separation exponent 2.1303}},
  year = {2026},
  url = {https://prove2.me/theorems/637bbe88-761a-4bb9-bad9-78a8c1bb90c7},
  note = {Attribution follows the public source; usernames are retained where no verified full name is supplied. Platform verification is not an independent Lean replay by this atlas. Accepted solution downloads require authentication (HTTP 401).; Inspected source: Public primary statement, construction summary and status, inspected 22 October 2026; HTML SHA-256 39bf4d7e70c08122ef7de6a66e25ab6f6bdb07cccac3b62c9a4ed69f4cae0172}
}

@misc{P2M21326,
  author = {Prove2Me contributors},
  title = {{Block Sensitivity vs. Sensitivity: Reach 2.13}},
  year = {2026},
  url = {https://prove2.me/missions/Block_Sensitivity_vs._Sensitivity%3A_Reach_2.13},
  note = {Attribution follows the public source; usernames are retained where no verified full name is supplied. Platform verification is not an independent Lean replay by this atlas. Accepted solution downloads require authentication (HTTP 401).; Inspected source: Public primary statement, construction summary and status, inspected 22 October 2026; HTML SHA-256 ac1525f9b931a7bc00c4656c96c8ef8338cb77cf7892e564b56ac68554f40aa4}
}

@misc{P2M2130825579397823926,
  author = {yousofy and Codex},
  title = {{Six shared defect tolerances: separation exponent 2.1308255793978239}},
  year = {2026},
  url = {https://prove2.me/theorems/01bb63ef-ced2-4ae9-8b81-b5ed295526c6},
  note = {Attribution follows the public source; usernames are retained where no verified full name is supplied. Platform verification is not an independent Lean replay by this atlas. Accepted solution downloads require authentication (HTTP 401).; Inspected source: Public primary statement, construction summary and status, inspected 22 October 2026; HTML SHA-256 b04d6d55bc6a9d1517c3236ca84983dff96e9a4835359dcdd15543e821ec7429}
}

@misc{P2Mcoupledexact26,
  author = {yousofy and Codex},
  title = {{Coupled target/guard finite family}},
  year = {2026},
  url = {https://prove2.me/theorems/ddfe4bf3-88be-4876-a196-33c20c0319ff},
  note = {Attribution follows the public source; usernames are retained where no verified full name is supplied. Platform verification is not an independent Lean replay by this atlas. Accepted solution downloads require authentication (HTTP 401).; Inspected source: Public primary statement, construction summary and status, inspected 22 October 2026; HTML SHA-256 9e43d4388146c10b27df1c21b585fe7cb5df694f8ca3b9fdc9e28cee0a98843c}
}

@misc{P2Msharedexact26,
  author = {yousofy and Codex},
  title = {{Four-stage shared-labeling exact endpoint}},
  year = {2026},
  url = {https://prove2.me/theorems/2bc2b8ee-797d-4500-9dc8-9b23c457e131},
  note = {Attribution follows the public source; usernames are retained where no verified full name is supplied. Platform verification is not an independent Lean replay by this atlas. Accepted solution downloads require authentication (HTTP 401).; Inspected source: Public primary statement, construction summary and status, inspected 22 October 2026; HTML SHA-256 6bf422d49212e66377e42e53fddba15acf4648fd8a125cfb3e9ed3fdcb4a8cbc}
}

@misc{P2Mrefinedexact26,
  author = {yousofy and Codex},
  title = {{Refined four-stage exact endpoint}},
  year = {2026},
  url = {https://prove2.me/theorems/62961329-4b50-48c7-a1fd-11159da9de26},
  note = {Attribution follows the public source; usernames are retained where no verified full name is supplied. Platform verification is not an independent Lean replay by this atlas. Accepted solution downloads require authentication (HTTP 401).; Inspected source: Public primary statement, construction summary and status, inspected 22 October 2026; HTML SHA-256 0a6b52af68f3c8d9aeb301d910503ea7bc4820fb477ba234303297b86923e2ba}
}

@misc{P2Msharedfamily26,
  author = {yousofy and Codex},
  title = {{Finite Boolean families from shared local-lemma labelings and a four-stage cycle}},
  year = {2026},
  url = {https://prove2.me/theorems/13efa201-cabf-4776-8b79-3e67e73e02a0},
  note = {Attribution follows the public source; usernames are retained where no verified full name is supplied. Platform verification is not an independent Lean replay by this atlas. Accepted solution downloads require authentication (HTTP 401).; Inspected source: Public primary statement, construction summary and status, inspected 22 October 2026; HTML SHA-256 d881729152512e1cd85da802ce3cecf121e3cea08ebd4cf0192a6fa878d9c639}
}

@article{MT10,
  author = {Robin A. Moser and Gábor Tardos},
  title = {{A constructive proof of the general Lovász Local Lemma}},
  year = {2010},
  journal = {Journal of the ACM},
  volume = {57},
  number = {2},
  pages = {1–15},
  doi = {10.1145/1667053.1667060},
  url = {https://arxiv.org/abs/0903.0544v3},
  eprint = {0903.0544},
  archivePrefix = {arXiv},
  note = {Journal bibliographic fields verified against publisher-deposited Crossref record for DOI 10.1145/1667053.1667060 on 22 October 2026. The campaign cites arXiv v3 Theorem 1.1; this atlas has not independently audited the entire Moser–Tardos proof.; Inspected source: arXiv v3 (20 May 2009), Theorem 1.1 cited by the public shared-labeling construction; journal bibliographic metadata verified separately}
}

@misc{LMparallel26,
  author = {Qipeng Liu and Saachi Mutreja},
  title = {{Parallel Quantum Advantage with Limited Adaptivity Requires Structure}},
  year = {2026},
  url = {https://arxiv.org/abs/2608.20297v2},
  eprint = {2608.20297},
  archivePrefix = {arXiv},
  note = {Primary version and selected question/theorem statements and stated scope inspected. This is a literature-status and proof-route check, not an independent verification of every proof in the paper.; Inspected source: arXiv v2, 20 October 2026; Conjecture 1.1, Introduction p.4, Theorems 1.6–1.8 pp.7–8}
}

@misc{BSW22,
  author = {Nikhil Bansal and Makrand Sinha and Ronald de Wolf},
  title = {{Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms}},
  year = {2022},
  url = {https://arxiv.org/abs/2203.00212v1},
  eprint = {2203.00212},
  archivePrefix = {arXiv},
  note = {Primary version and selected question/theorem statements and stated scope inspected. This is a literature-status and proof-route check, not an independent verification of every proof in the paper.; Inspected source: arXiv v1, 1 March 2022; Conjectures 1.1–1.2, Theorem 1.3, Section 4}
}

@misc{Bha26,
  author = {Sreejata Kishor Bhattacharya},
  title = {{Aaronson-Ambainis Conjecture Is True For Random Restrictions}},
  year = {2024},
  url = {https://eccc.weizmann.ac.il/report/2024/035/revision/2/},
  eprint = {2402.13952},
  archivePrefix = {arXiv},
  note = {ECCC TR24-035, revision 2 (4 March 2026); Primary version and selected question/theorem statements and stated scope inspected. This is a literature-status and proof-route check, not an independent verification of every proof in the paper. Bibliographic year is the original 2024 report, not the 2026 revision date. The author name follows the PDF title page.; ITCS 2025, under the title Random Restrictions of Bounded Low Degree Polynomials Are Juntas; separately keyed Bha25. One underlying work for recurrence counts.; Inspected source: ECCC TR24-035, revision 2, 4 March 2026; Conjecture 1.3 and abstract/main result}
}

@misc{BBCLD26,
  author = {Sreejata Kishor Bhattacharya and Farzan Byramji and Arkadev Chattopadhyay and Yogesh Dahiya and Shachar Lovett},
  title = {{Quantum-Classical Equivalence for AND-Functions}},
  year = {2026},
  url = {https://arxiv.org/abs/2606.03249v1},
  eprint = {2606.03249},
  archivePrefix = {arXiv},
  note = {Primary version and selected question/theorem statements and stated scope inspected. This is a literature-status and proof-route check, not an independent verification of every proof in the paper.; Inspected source: arXiv v1, 2 June 2026; Section 1.1 pp.3–5}
}

@misc{FLM26,
  author = {Yuval Filmus and Anqi Li and Dor Minzer},
  title = {{An FKN Theorem for the Binary Grassmann Scheme}},
  year = {2026},
  url = {https://arxiv.org/abs/2608.11320v1},
  eprint = {2608.11320},
  archivePrefix = {arXiv},
  note = {Primary version and selected question/theorem statements and stated scope inspected. This is a literature-status and proof-route check, not an independent verification of every proof in the paper.; Inspected source: arXiv v1, 11 August 2026; Theorems 1.2–1.3 and Introduction}
}

@misc{NPS26,
  author = {Sai Soumya Nalli and Karthikeya Polisetty and Jayalal Sarma},
  title = {{On Condensation of Block Sensitivity, Certificate Complexity and the AND (and OR) Decision Tree Complexity}},
  year = {2026},
  url = {https://arxiv.org/abs/2602.01042v2},
  eprint = {2602.01042},
  archivePrefix = {arXiv},
  note = {Primary version and selected question/theorem statements and stated scope inspected. This is a literature-status and proof-route check, not an independent verification of every proof in the paper.; Inspected source: arXiv v2, 16 March 2026; abstract, Sections 3–4 and Appendix A}
}

@inproceedings{CPS23,
  author = {Rahul Chugh and Supartha Podder and Swagato Sanyal},
  title = {{Decision Tree Complexity versus Block Sensitivity and Degree}},
  year = {2023},
  booktitle = {43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume = {284},
  pages = {27:1--27:23},
  doi = {10.4230/LIPIcs.FSTTCS.2023.27},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.27},
  note = {Primary version and selected question/theorem statements and stated scope inspected. This is a literature-status and proof-route check, not an independent verification of every proof in the paper.; Inspected source: FSTTCS 2023 proceedings, Question 1 and discussion p.27:3, Theorems 4–5 pp.27:4–27:5}
}

@inproceedings{Bha25,
  author = {Sreejata Kishor Bhattacharya},
  title = {{Random Restrictions of Bounded Low Degree Polynomials Are Juntas}},
  year = {2025},
  booktitle = {16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume = {325},
  pages = {17:1--17:21},
  doi = {10.4230/LIPIcs.ITCS.2025.17},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.17},
  note = {Official publisher metadata and selected full-PDF conjecture/theorem statements checked. The latest arXiv page 2402.13952v2 says accepted at ITCS 2025. Full proof not independently re-proved.; Inspected source: Final ITCS 2025 paper; Conjecture 4, Theorems 5 and 30, article pp.17:2–17:3 and 17:19}
}

@misc{ADGG26,
  author = {Ryan Anselm and Michelle Ding and Dar Gilboa and Sabee Grewal},
  title = {{Optimal and Verifiable Quantum Advantages in Communication Complexity}},
  year = {2026},
  doi = {10.48550/arXiv.2610.05585},
  url = {https://arxiv.org/abs/2610.05585v1},
  eprint = {2610.05585},
  archivePrefix = {arXiv},
  note = {Inspected source: arXiv v1, 4 October 2026, 65 pages; Theorems 1.1–1.3, Sections 1.1.1, 4.1–4.2; selected statements and proof route checked, not a full proof audit}
}

@inproceedings{GNSTW16,
  author = {Parikshit Gopalan and Noam Nisan and Rocco A. Servedio and Kunal Talwar and Avi Wigderson},
  title = {{Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions}},
  year = {2016},
  booktitle = {Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS 2016)},
  publisher = {Association for Computing Machinery},
  pages = {59--70},
  doi = {10.1145/2840728.2840738},
  url = {https://www.cs.columbia.edu/~rocco/Public/GNSTW.pdf},
  eprint = {1508.02420},
  archivePrefix = {arXiv},
  note = {Inspected source: 12-page author-hosted proceedings PDF; Theorem 8 and Section 2.1 checked}
}