references.bib

@misc{Acclavio2026,
      title={Choreographic Programming: a Semantic Approach}, 
      author={Matteo Acclavio and Giulia Manara and Fabrizio Montesi and Xueying Qin},
      year={2026},
      eprint={2607.23793},
      archivePrefix={arXiv},
      primaryClass={cs.PL},
      url={https://arxiv.org/abs/2607.23793}, 
}

@inproceedings{Aceto1999,
  author       = {Luca Aceto and
                  Anna Ing{\'{o}}lfsd{\'{o}}ttir},
  editor       = {Wolfgang Thomas},
  title        = {Testing Hennessy-Milner Logic with Recursion},
  booktitle    = {Foundations of Software Science and Computation Structure, Second
                  International Conference, FoSSaCS'99, Held as Part of the European
                  Joint Conferences on the Theory and Practice of Software, ETAPS'99,
                  Amsterdam, The Netherlands, March 22-28, 1999, Proceedings},
  series       = {Lecture Notes in Computer Science},
  volume       = {1578},
  pages        = {41--55},
  publisher    = {Springer},
  year         = {1999},
  url          = {https://doi.org/10.1007/3-540-49019-1\_4},
  doi          = {10.1007/3-540-49019-1\_4},
  timestamp    = {Tue, 14 May 2019 10:00:55 +0200},
  biburl       = {https://dblp.org/rec/conf/fossacs/AcetoI99.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{Adleman1978,
  author    = {Adleman, Leonard},
  title     = {Two Theorems on Random Polynomial Time},
  booktitle = {19th Annual Symposium on Foundations of Computer Science},
  publisher = {IEEE Computer Society},
  year      = {1978},
  pages     = {75--83},
  doi       = {10.1109/SFCS.1978.37}
}

@article{AFvMV2006,
  author  = {Antunes, Lu{\'i}s and Fortnow, Lance and van Melkebeek, Dieter and
             Vinodchandran, N. V.},
  title   = {Computational Depth: Concept and Applications},
  journal = {Theoretical Computer Science},
  volume  = {354},
  pages   = {391--404},
  year    = {2006}
}

@article{Ajtai1983,
  author    = {Ajtai, Mikl{\'o}s},
  title     = {{$\Sigma^1_1$}-Formulae on Finite Structures},
  journal   = {Annals of Pure and Applied Logic},
  volume    = {24},
  number    = {1},
  pages     = {1--48},
  year      = {1983},
  doi       = {10.1016/0168-0072(83)90038-6}
}

@inproceedings{Ajtai1996,
  author    = {Ajtai, Mikl{\'o}s},
  title     = {Generating Hard Instances of Lattice Problems},
  booktitle = {Proceedings of the Twenty-Eighth Annual {ACM} Symposium on Theory of
               Computing ({STOC} '96)},
  pages     = {99--108},
  publisher = {ACM},
  year      = {1996},
  doi       = {10.1145/237814.237838}
}

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

@article{AKS2004,
  author    = {Agrawal, Manindra and Kayal, Neeraj and Saxena, Nitin},
  title     = {{PRIMES} is in {P}},
  journal   = {Annals of Mathematics},
  volume    = {160},
  number    = {2},
  pages     = {781--793},
  year      = {2004},
  doi       = {10.4007/annals.2004.160.781}
}

@misc{Algolean2026,
  author  = {Srinivas, Shreyas and Ermovick, Ethan and Duve, Tanner and Hamade, Bashar and
             Tantow, Johannes and Schlesinger, Samuel},
  title   = {Algolean: Algorithms and Complexity Library using the Lightweight Query Combinator
             Framework Called {Prog}},
  note    = {Lean library, version 1.0.0},
  year    = {2026},
  url     = {https://github.com/Shreyas4991/Algolean}
}

@article{AllenderBuhrmanKouckyVanMelkebeekRonneburger2006,
  author  = {Allender, Eric and Buhrman, Harry and Kouck{\'y}, Michal and van Melkebeek, Dieter and Ronneburger, Detlef},
  title   = {Power from Random Strings},
  journal = {SIAM Journal on Computing},
  volume  = {35},
  number  = {6},
  pages   = {1467--1493},
  year    = {2006},
  doi     = {10.1137/050628994}
}

@article{AllenderRubinstein1988,
  author    = {Allender, Eric W. and Rubinstein, Roy S.},
  title     = {{P}-Printable Sets},
  journal   = {SIAM Journal on Computing},
  volume    = {17},
  number    = {6},
  pages     = {1193--1202},
  year      = {1988},
  doi       = {10.1137/0217075}
}

@article{AlonBoppana1987,
  author    = {Alon, Noga and Boppana, Ravi B.},
  title     = {The Monotone Circuit Complexity of {B}oolean Functions},
  journal   = {Combinatorica},
  volume    = {7},
  number    = {1},
  pages     = {1--22},
  year      = {1987},
  doi       = {10.1007/BF02579196}
}

@article{AlonGoldreichHastadPeralta1992,
  author    = {Alon, Noga and Goldreich, Oded and H{\aa}stad, Johan and Peralta, Ren{\'e}},
  title     = {Simple Constructions of Almost $k$-wise Independent Random Variables},
  journal   = {Random Structures \& Algorithms},
  volume    = {3},
  number    = {3},
  pages     = {289--304},
  year      = {1992},
  doi       = {10.1002/rsa.3240030308}
}

@book{AlonSpencer2016,
  author    = {Alon, Noga and Spencer, Joel H.},
  title     = {The Probabilistic Method},
  edition   = {4},
  publisher = {Wiley},
  year      = {2016},
  isbn      = {978-1-119-06195-3}
}

@article{AlpernSchneider1985,
  author    = {Alpern, Bowen and Schneider, Fred B.},
  title     = {Defining liveness},
  journal   = {Information Processing Letters},
  volume    = {21},
  number    = {4},
  pages     = {181--185},
  year      = {1985},
  issn      = {0020-0190},
  doi       = {10.1016/0020-0190(85)90056-0},
  url       = {https://www.sciencedirect.com/science/article/pii/0020019085900560}
}

@incollection{AmbosSpies1984,
  author    = {Ambos-Spies, Klaus},
  title     = {{$P$}-mitotic sets},
  booktitle = {Logic and Machines: Decision Problems and Complexity},
  series    = {Lecture Notes in Computer Science},
  volume    = {171},
  pages     = {1--23},
  publisher = {Springer},
  year      = {1984},
  doi       = {10.1007/3-540-13331-3_30}
}

@article{AnderssonMiltersenThorup1999,
  author  = {Andersson, Arne and Miltersen, Peter Bro and Thorup, Mikkel},
  title   = {Fusion Trees can be Implemented with {AC$^0$} Instructions Only},
  journal = {Theoretical Computer Science},
  volume  = {215},
  number  = {1--2},
  year    = {1999},
  pages   = {337--344},
  doi     = {10.1016/S0304-3975(98)00172-8}
}

@article{Andreev1987,
  author  = {Andreev, A. E.},
  title   = {On a Method for Obtaining More Than Quadratic Effective Lower Bounds for the
             Complexity of $\pi$-Schemes},
  journal = {Moscow University Mathematics Bulletin},
  volume  = {42},
  number  = {1},
  pages   = {24--29},
  year    = {1987},
  note    = {Russian original: Vestnik Moskovskogo Universiteta, Seriya 1, (1), 70--73}
}

@article{Andreev1989,
  author  = {Andreev, A. E.},
  title   = {On the Complexity of the Realization of Partial {B}oolean Functions by Circuits of
             Functional Elements},
  journal = {Diskretnaya Matematika},
  volume  = {1},
  number  = {4},
  pages   = {36--45},
  year    = {1989},
  note    = {In Russian}
}

@article{Angluin1980,
  author       = {Angluin, Dana},
  title        = {Inductive Inference of Formal Languages from Positive Data},
  journal      = {Information and Control},
  volume       = {45},
  number       = {2},
  pages        = {117--135},
  year         = {1980},
  doi          = {10.1016/S0019-9958(80)90285-5}
}

@article{Angluin1988,
  author    = {Angluin, Dana},
  title     = {Queries and Concept Learning},
  journal   = {Machine Learning},
  volume    = {2},
  number    = {4},
  pages     = {319--342},
  year      = {1988},
  doi       = {10.1007/BF00116828}
}

@article{AngluinLaird1988,
  author       = {Angluin, Dana and Laird, Philip},
  title        = {Learning from Noisy Examples},
  journal      = {Machine Learning},
  volume       = {2},
  number       = {4},
  pages        = {343--370},
  year         = {1988},
  doi          = {10.1007/BF00116829}
}

@book{AroraBarak09,
  author       = {Sanjeev Arora and
                  Boaz Barak},
  title        = {Computational Complexity - {A} Modern Approach},
  publisher    = {Cambridge University Press},
  year         = {2009},
}

@article{AroraLundMotwaniSudanSzegedy1998,
  author    = {Arora, Sanjeev and Lund, Carsten and Motwani, Rajeev and Sudan, Madhu
               and Szegedy, Mario},
  title     = {Proof Verification and the Hardness of Approximation Problems},
  journal   = {Journal of the ACM},
  volume    = {45},
  number    = {3},
  pages     = {501--555},
  year      = {1998},
  doi       = {10.1145/278298.278306}
}

@article{AroraSafra1998,
  author    = {Arora, Sanjeev and Safra, Shmuel},
  title     = {Probabilistic Checking of Proofs: A New Characterization of {NP}},
  journal   = {Journal of the ACM},
  volume    = {45},
  number    = {1},
  pages     = {70--122},
  year      = {1998},
  doi       = {10.1145/273865.273901}
}

@article{AspvallPlassTarjan1979,
  author  = {Aspvall, Bengt and Plass, Michael F. and Tarjan, Robert Endre},
  title   = {A Linear-Time Algorithm for Testing the Truth of Certain Quantified {B}oolean Formulas},
  journal = {Information Processing Letters},
  volume  = {8},
  number  = {3},
  pages   = {121--123},
  year    = {1979},
  doi     = {10.1016/0020-0190(79)90002-4}
}

@book{Baader1998,
author = {Baader, Franz and Nipkow, Tobias},
title = {Term rewriting and all that},
year = {1998},
isbn = {0521455200},
publisher = {Cambridge University Press},
address = {USA}
}

@inproceedings{Babai1985,
  author    = {Babai, L{\'a}szl{\'o}},
  title     = {Trading Group Theory for Randomness},
  booktitle = {Proceedings of the 17th Annual ACM Symposium on Theory of Computing},
  pages     = {421--429},
  year      = {1985},
  doi       = {10.1145/22145.22192}
}

@inproceedings{BabaiFortnowLevinSzegedy1991,
  author    = {Babai, L{\'a}szl{\'o} and Fortnow, Lance and Levin, Leonid A. and Szegedy, Mario},
  title     = {Checking Computations in Polylogarithmic Time},
  booktitle = {Proceedings of the 23rd Annual ACM Symposium on Theory of Computing},
  series    = {STOC 1991},
  pages     = {21--32},
  year      = {1991},
  doi       = {10.1145/103418.103428}
}

@article{BabaiFortnowLund1991,
  author  = {Babai, L{\'a}szl{\'o} and Fortnow, Lance and Lund, Carsten},
  title   = {Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols},
  journal = {Computational Complexity},
  volume  = {1},
  number  = {1},
  pages   = {3--40},
  year    = {1991},
  doi     = {10.1007/BF01200056},
  url     = {https://doi.org/10.1007/BF01200056}
}

@article{BabaiFortnowNisanWigderson1993,
  author    = {Babai, L{\'a}szl{\'o} and Fortnow, Lance and Nisan, Noam and Wigderson, Avi},
  title     = {{BPP} Has Subexponential Time Simulations Unless {EXPTIME} Has Publishable Proofs},
  journal   = {Computational Complexity},
  volume    = {3},
  number    = {4},
  pages     = {307--318},
  year      = {1993},
  doi       = {10.1007/BF01275486}
}

@article{BabaiMoran1988,
  author    = {Babai, L{\'a}szl{\'o} and Moran, Shlomo},
  title     = {{Arthur}--{Merlin} Games: A Randomized Proof System, and a Hierarchy of Complexity
               Classes},
  journal   = {Journal of Computer and System Sciences},
  volume    = {36},
  number    = {2},
  pages     = {254--276},
  year      = {1988},
  doi       = {10.1016/0022-0000(88)90028-1}
}

@article{BakerGillSolovay1975,
  author  = {Baker, Theodore and Gill, John and Solovay, Robert},
  title   = {Relativizations of the {$\mathcal{P} =? \mathcal{NP}$} Question},
  journal = {SIAM Journal on Computing},
  volume  = {4},
  number  = {4},
  pages   = {431--442},
  year    = {1975},
  doi     = {10.1137/0204037}
}

@misc{Barak2016PRG,
  author = {Barak, Boaz},
  title = {{CS 127: Pseudorandomness}},
  year = {2016},
  note = {Length extension for pseudorandom generators},
  url = {https://www.boazbarak.org/cs127spring16/chap03-pseudorandom-generators}
}

@techreport{BarakGoldreich2001,
  author      = {Barak, Boaz and Goldreich, Oded},
  title       = {Universal Arguments and their Applications},
  institution = {Electronic Colloquium on Computational Complexity},
  number      = {TR01-093},
  year        = {2001},
  url         = {https://eccc.weizmann.ac.il/report/2001/093/}
}

@article{         Barendregt1984,
  title={Introduction to Lambda Calculus},
  year={1984}
}

@article{Barrington1989,
  author    = {Barrington, David A.},
  title     = {Bounded-width polynomial-size branching programs recognize exactly those languages
               in {NC}$^1$},
  journal   = {Journal of Computer and System Sciences},
  volume    = {38},
  number    = {1},
  pages     = {150--164},
  year      = {1989}
}

@article{BarringtonImmermanStraubing1990,
  author    = {Barrington, David A. Mix and Immerman, Neil and Straubing, Howard},
  title     = {On Uniformity within {NC}$^1$},
  journal   = {Journal of Computer and System Sciences},
  volume    = {41},
  number    = {3},
  pages     = {274--306},
  year      = {1990},
  doi       = {10.1016/0022-0000(90)90022-D}
}

@article{BarringtonTherien1988,
  author    = {Barrington, David A. Mix and Th{\'e}rien, Denis},
  title     = {Finite Monoids and the Fine Structure of {NC}$^1$},
  journal   = {Journal of the ACM},
  volume    = {35},
  number    = {4},
  pages     = {941--952},
  year      = {1988},
  doi       = {10.1145/48014.63138}
}

@inproceedings{Batcher1968,
  author = {Batcher, Kenneth E.},
  title = {Sorting Networks and Their Applications},
  booktitle = {Proceedings of the Spring Joint Computer Conference},
  series = {AFIPS Conference Proceedings},
  volume = {32},
  pages = {307--314},
  year = {1968},
  doi = {10.1145/1468075.1468121},
  url = {https://doi.org/10.1145/1468075.1468121}
}

@article{BBBV1997,
  author    = {Bennett, Charles H. and Bernstein, Ethan and Brassard, Gilles and Vazirani, Umesh},
  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}
}

@article{BealsBuhrmanCleveMoscaDeWolf2001,
  author    = {Beals, Robert and Buhrman, Harry and Cleve, Richard and Mosca, Michele and
               de Wolf, Ronald},
  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}
}

@article{BeameEtAl1998,
  author = {Beame, Paul and Cook, Stephen and Edmonds, Jeff and Impagliazzo, Russell and Pitassi, Toniann},
  title = {The Relative Complexity of {NP} Search Problems},
  journal = {Journal of Computer and System Sciences},
  volume = {57},
  number = {1},
  pages = {3--19},
  year = {1998},
  doi = {10.1006/jcss.1998.1575},
  url = {https://doi.org/10.1006/jcss.1998.1575}
}

@inproceedings{BeamePitassi1996,
  author    = {Beame, Paul and Pitassi, Toniann},
  title     = {Simplified and Improved Resolution Lower Bounds},
  booktitle = {Proceedings of the 37th Annual Symposium on Foundations of Computer Science},
  pages     = {274--282},
  publisher = {IEEE Computer Society},
  year      = {1996},
  doi       = {10.1109/SFCS.1996.548486},
  url       = {https://doi.org/10.1109/SFCS.1996.548486}
}

@inproceedings{BeigelGillHertrampf1990,
  author    = {Beigel, Richard and Gill, John and Hertrampf, Ulrich},
  title     = {Counting Classes: Thresholds, Parity, Mods, and Fewness},
  booktitle = {STACS 90: 7th Annual Symposium on Theoretical Aspects of Computer Science},
  series    = {Lecture Notes in Computer Science},
  volume    = {415},
  pages     = {49--57},
  publisher = {Springer},
  year      = {1990},
  doi       = {10.1007/3-540-52282-4_31}
}

@article{BeigelReingoldSpielman1995,
  author    = {Beigel, Richard and Reingold, Nick and Spielman, Daniel A.},
  title     = {{PP} Is Closed under Intersection},
  journal   = {Journal of Computer and System Sciences},
  volume    = {50},
  number    = {2},
  pages     = {191--202},
  year      = {1995},
  doi       = {10.1006/jcss.1995.1017}
}

@inproceedings{BellareNeven2006,
  author       = {Mihir Bellare and Gregory Neven},
  title        = {Multi-Signatures in the Plain Public-Key Model and a General Forking Lemma},
  booktitle    = {Proceedings of the 13th ACM Conference on Computer and Communications Security},
  pages        = {390--399},
  publisher    = {ACM},
  year         = {2006},
  doi          = {10.1145/1180405.1180453}
}

@inproceedings{BellareRompel1994,
  author    = {Bellare, Mihir and Rompel, John},
  title     = {Randomness-Efficient Oblivious Sampling},
  booktitle = {Proceedings of the 35th Annual Symposium on Foundations of Computer Science},
  series    = {FOCS 1994},
  pages     = {276--287},
  year      = {1994},
  doi       = {10.1109/SFCS.1994.365687}
}

@inproceedings{BenOrGoldwasserKilianWigderson1988,
  author    = {Ben-Or, Michael and Goldwasser, Shafi and Kilian, Joe and Wigderson, Avi},
  title     = {Multi-prover Interactive Proofs: How to Remove Intractability Assumptions},
  booktitle = {Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing},
  series    = {STOC '88},
  pages     = {113--131},
  publisher = {ACM},
  year      = {1988},
  doi       = {10.1145/62212.62223},
  url       = {https://doi.org/10.1145/62212.62223}
}

@inproceedings{BenSassonChiesaSpooner2016,
  author       = {Eli Ben-Sasson and Alessandro Chiesa and Nicholas Spooner},
  title        = {Interactive Oracle Proofs},
  booktitle    = {Theory of Cryptography -- TCC 2016-B, Part II},
  series       = {Lecture Notes in Computer Science},
  volume       = {9986},
  pages        = {31--60},
  publisher    = {Springer},
  year         = {2016},
  doi          = {10.1007/978-3-662-53644-5_2}
}

@article{BenSassonKopparty2012,
  author  = {Ben-Sasson, Eli and Kopparty, Swastik},
  title   = {Affine Dispersers from Subspace Polynomials},
  journal = {SIAM Journal on Computing},
  volume  = {41},
  number  = {4},
  pages   = {880--914},
  year    = {2012},
  doi     = {10.1137/110826254},
  note    = {Theorem numbers follow the ECCC report TR10-044 (2010)}
}

@article{BenSassonWigderson2001,
  author = {Ben-Sasson, Eli and Wigderson, Avi},
  title = {Short Proofs Are Narrow---Resolution Made Simple},
  journal = {Journal of the ACM},
  volume = {48},
  number = {2},
  pages = {149--169},
  year = {2001},
  doi = {10.1145/375827.375835},
  url = {https://doi.org/10.1145/375827.375835}
}

@article{Berkowitz1984,
  author    = {Berkowitz, Stuart J.},
  title     = {On Computing the Determinant in Small Parallel Time Using a Small Number
               of Processors},
  journal   = {Information Processing Letters},
  volume    = {18},
  number    = {3},
  pages     = {147--150},
  year      = {1984},
  doi       = {10.1016/0020-0190(84)90018-8}
}

@article{BermanHartmanis1977,
  author    = {Berman, Leonard and Hartmanis, Juris},
  title     = {On isomorphisms and density of {NP} and other complete sets},
  journal   = {SIAM Journal on Computing},
  volume    = {6},
  number    = {2},
  pages     = {305--322},
  year      = {1977},
  doi       = {10.1137/0206023}
}

@article{Bird2011,
  author    = {Bird, Richard S.},
  title     = {A Simple Division-Free Algorithm for Computing Determinants},
  journal   = {Information Processing Letters},
  volume    = {111},
  number    = {21--22},
  pages     = {1072--1074},
  year      = {2011},
  doi       = {10.1016/j.ipl.2011.08.006}
}

@book{Blackburn2001,
  place={Cambridge},
  series={Cambridge Tracts in Theoretical Computer Science},
  title={Modal Logic},
  publisher={Cambridge University Press},
  author={Blackburn, Patrick and Rijke, Maarten de and Venema, Yde},
  year={2001},
  collection={Cambridge Tracts in Theoretical Computer Science}
}

@article{BlassGurevich1982,
  author = {Blass, Andreas and Gurevich, Yuri},
  title = {On the Unique Satisfiability Problem},
  journal = {Information and Control},
  volume = {55},
  number = {1--3},
  pages = {80--88},
  year = {1982},
  doi = {10.1016/S0019-9958(82)90439-9}
}

@inproceedings{BlumImpagliazzo1987,
  author    = {Blum, Manuel and Impagliazzo, Russell},
  title     = {Generic oracles and oracle classes},
  booktitle = {28th Annual Symposium on Foundations of Computer Science},
  pages     = {118--126},
  year      = {1987}
}

@article{BlumLubyRubinfeld1993,
  author    = {Blum, Manuel and Luby, Michael and Rubinfeld, Ronitt},
  title     = {Self-Testing/Correcting with Applications to Numerical Problems},
  journal   = {Journal of Computer and System Sciences},
  volume    = {47},
  number    = {3},
  pages     = {549--595},
  year      = {1993},
  doi       = {10.1016/0022-0000(93)90044-W}
}

@article{BoehlerGlasserMeister2006,
  author    = {B{\"o}hler, Elmar and Gla{\ss}er, Christian and Meister, Daniel},
  title     = {Error-bounded probabilistic computations between {MA} and {AM}},
  journal   = {Journal of Computer and System Sciences},
  volume    = {72},
  number    = {6},
  pages     = {1043--1076},
  year      = {2006}
}

@article{Bonami1970,
  author    = {Bonami, Aline},
  title     = {{\'E}tude des coefficients de {Fourier} des fonctions de {$L^p(G)$}},
  journal   = {Annales de l'Institut Fourier},
  volume    = {20},
  number    = {2},
  pages     = {335--402},
  year      = {1970},
  doi       = {10.5802/aif.357}
}

@inproceedings{BonehHaleviHamburgOstrovsky2008,
  author       = {Dan Boneh and Shai Halevi and Mike Hamburg and Rafail Ostrovsky},
  title        = {Circular-Secure Encryption from Decision Diffie-Hellman},
  booktitle    = {Advances in Cryptology -- CRYPTO 2008},
  series       = {Lecture Notes in Computer Science},
  volume       = {5157},
  pages        = {108--125},
  publisher    = {Springer},
  year         = {2008},
  url          = {https://crypto.stanford.edu/~dabo/papers/circular.pdf}
}

@misc{BonehShoup2023,
  author       = {Dan Boneh and Victor Shoup},
  title        = {A Graduate Course in Applied Cryptography},
  year         = {2023},
  note         = {Version 0.6},
  url          = {https://crypto.stanford.edu/~dabo/cryptobook/BonehShoup_0_6.pdf}
}

@article{Book1974,
  author    = {Book, Ronald V.},
  title     = {Comparing Complexity Classes},
  journal   = {Journal of Computer and System Sciences},
  volume    = {9},
  number    = {2},
  pages     = {213--229},
  year      = {1974},
  doi       = {10.1016/S0022-0000(74)80008-5}
}

@article{BoppanaHastadZachos1987,
  author    = {Boppana, Ravi B. and H{\aa}stad, Johan and Zachos, Stathis},
  title     = {Does co-{NP} Have Short Interactive Proofs?},
  journal   = {Information Processing Letters},
  volume    = {25},
  number    = {2},
  pages     = {127--132},
  year      = {1987},
  doi       = {10.1016/0020-0190(87)90232-8}
}

@article{BorchertHemaspaandraRothe2000,
  author    = {Borchert, Bernd and Hemaspaandra, Lane A. and Rothe, J{\"o}rg},
  title     = {Restrictive Acceptance Suffices for Equivalence Problems},
  journal   = {LMS Journal of Computation and Mathematics},
  volume    = {3},
  pages     = {86--95},
  year      = {2000},
  doi       = {10.1112/S146115700000022X},
  url       = {https://arxiv.org/abs/cs/9907041}
}

@book{BorweinErdelyi1995,
  author    = {Borwein, Peter and Erd{\'e}lyi, Tam{\'a}s},
  title     = {Polynomials and Polynomial Inequalities},
  series    = {Graduate Texts in Mathematics},
  volume    = {161},
  publisher = {Springer},
  year      = {1995},
  doi       = {10.1007/978-1-4612-0793-1}
}

@article{Bourgain2007,
  author  = {Bourgain, Jean},
  title   = {On the Construction of Affine Extractors},
  journal = {Geometric and Functional Analysis},
  volume  = {17},
  number  = {1},
  pages   = {33--57},
  year    = {2007},
  doi     = {10.1007/s00039-007-0593-z}
}

@inproceedings{BovaCapelliMengelSlivovsky2016,
  author    = {Bova, Simone and Capelli, Florent and Mengel, Stefan and Slivovsky, Friedrich},
  title     = {Knowledge Compilation Meets Communication Complexity},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on Artificial
               Intelligence (IJCAI 2016)},
  pages     = {1008--1014},
  year      = {2016}
}

@phdthesis{Boyack1985,
  author = {Boyack, Stephen Wayne},
  title = {The Robustness of Combinatorial Measures of {Boolean} Matrix Complexity},
  school = {Massachusetts Institute of Technology},
  year = {1985},
  url = {https://people.csail.mit.edu/rivest/student-theses/phd-1985-boyack.pdf}
}

@article{BuhrmanDeWolf2002,
  author    = {Buhrman, Harry and de Wolf, Ronald},
  title     = {Complexity measures and decision tree complexity: a survey},
  journal   = {Theoretical Computer Science},
  volume    = {288},
  number    = {1},
  pages     = {21--43},
  year      = {2002}
}

@article{BuhrmanFortnowVanMelkebeekTorenvliet2000,
  author    = {Buhrman, Harry and Fortnow, Lance and van Melkebeek, Dieter and Torenvliet, Leen},
  title     = {Separating Complexity Classes Using Autoreducibility},
  journal   = {SIAM Journal on Computing},
  volume    = {29},
  number    = {5},
  pages     = {1497--1520},
  year      = {2000},
  doi       = {10.1137/S0097539798334736}
}

@misc{Burghardt2018,
	title = {Simple {Laws} about {Nonprominent} {Properties} of {Binary} {Relations}},
	url = {https://arxiv.org/abs/1806.05036v2},
	abstract = {We checked each binary relation on a 5-element set for a given set of properties, including usual ones like asymmetry and less known ones like Euclideanness. Using a poor man's Quine-McCluskey algorithm, we computed prime implicants of non-occurring property combinations, like "not irreflexive, but asymmetric". We considered the non-trivial laws obtained this way, and manually proved them true for binary relations on arbitrary sets, thus contributing to the encyclopedic knowledge about less known properties.},
	language = {en},
	urldate = {2026-05-19},
	journal = {arXiv.org},
	author = {Burghardt, Jochen},
	month = jun,
	year = {2018},
}

@book{Burgisser2000,
  author    = {B{\"u}rgisser, Peter},
  title     = {Completeness and Reduction in Algebraic Complexity Theory},
  series    = {Algorithms and Computation in Mathematics},
  volume    = {7},
  publisher = {Springer},
  year      = {2000},
  doi       = {10.1007/978-3-662-04179-6}
}

@book{BurgisserClausenShokrollahi1997,
  author    = {B{\"u}rgisser, Peter and Clausen, Michael and Shokrollahi, M. Amin},
  title     = {Algebraic Complexity Theory},
  series    = {Grundlehren der mathematischen Wissenschaften},
  publisher = {Springer},
  year      = {1997},
  doi       = {10.1007/978-3-662-03338-8}
}

@article{BussGoldsmith1993,
  author  = {Buss, Jonathan F. and Goldsmith, Judy},
  title   = {Nondeterminism within {P}},
  journal = {SIAM Journal on Computing},
  volume  = {22},
  number  = {3},
  pages   = {560--572},
  year    = {1993},
  doi     = {10.1137/0222038}
}

@article{CaiChenDowneyFellows1997,
  author  = {Cai, Liming and Chen, Jianer and Downey, Rodney G. and Fellows, Michael R.},
  title   = {Advice classes of parameterized tractability},
  journal = {Annals of Pure and Applied Logic},
  volume  = {84},
  number  = {1},
  pages   = {119--138},
  year    = {1997},
  doi     = {10.1016/S0168-0072(96)00020-6}
}

@article{CaiEtAl1988,
  author = {Cai, Jin-Yi and Gundermann, Thomas and Hartmanis, Juris and
    Hemachandra, Lane A. and Sewelson, Vivian and Wagner, Klaus and Wechsung, Gerd},
  title = {The Boolean Hierarchy {I}: Structural Properties},
  journal = {SIAM Journal on Computing},
  volume = {17},
  number = {6},
  pages = {1232--1252},
  year = {1988},
  doi = {10.1137/0217078}
}

@article{CaiHemachandra1990,
  author  = {Cai, Jin-Yi and Hemachandra, Lane A.},
  title   = {On the Power of Parity Polynomial Time},
  journal = {Mathematical Systems Theory},
  volume  = {23},
  number  = {1},
  pages   = {95--106},
  year    = {1990},
  doi     = {10.1007/BF02090768}
}

@phdthesis{Calabro2009,
  author    = {Calabro, Chris},
  title     = {The Exponential Complexity of Satisfiability Problems},
  school    = {University of California, San Diego},
  year      = {2009}
}

@inproceedings{CalabroImpagliazzoPaturi2006,
  author    = {Calabro, Chris and Impagliazzo, Russell and Paturi, Ramamohan},
  title     = {A Duality between Clause Width and Clause Density for {SAT}},
  booktitle = {21st Annual IEEE Conference on Computational Complexity (CCC 2006)},
  pages     = {252--260},
  year      = {2006},
  doi       = {10.1109/CCC.2006.6}
}

@mastersthesis{Calisto2022,
  author       = {Calisto, Bruna},
  title        = {Formalization in {Coq} of the {Standardization Theorem} for {$\lambda$}-calculus},
  school       = {Universidade do Minho},
  year         = {2022}
}

@inproceedings{CanettiCHLRRW2019,
  author       = {Ran Canetti and Yilei Chen and Justin Holmgren and Alex Lombardi and
                  Guy N. Rothblum and Ron D. Rothblum and Daniel Wichs},
  title        = {Fiat--Shamir: From Practice to Theory},
  booktitle    = {Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing},
  series       = {STOC 2019},
  pages        = {1082--1090},
  publisher    = {ACM},
  year         = {2019},
  doi          = {10.1145/3313276.3316380}
}

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

@techreport{CavalarOliveira2025,
  author = {Bruno P. Cavalar and Igor C. Oliveira},
  title = {Boolean Circuit Complexity and Two-Dimensional Cover Problems},
  institution = {Electronic Colloquium on Computational Complexity},
  number = {TR25-033},
  year = {2025},
  url = {https://eccc.weizmann.ac.il/report/2025/033/}
}

@article{ChandraKozenStockmeyer1981,
  author    = {Chandra, Ashok K. and Kozen, Dexter C. and Stockmeyer, Larry J.},
  title     = {Alternation},
  journal   = {Journal of the ACM},
  volume    = {28},
  number    = {1},
  pages     = {114--133},
  year      = {1981},
  doi       = {10.1145/322234.322243}
}

@article{ChandraStockmeyerVishkin1984,
  author    = {Chandra, Ashok K. and Stockmeyer, Larry and Vishkin, Uzi},
  title     = {Constant Depth Reducibility},
  journal   = {SIAM Journal on Computing},
  volume    = {13},
  number    = {2},
  pages     = {423--439},
  year      = {1984},
  doi       = {10.1137/0213028}
}

@article{         Chargueraud2012,
	title = {The {Locally} {Nameless} {Representation}},
	volume = {49},
	issn = {1573-0670},
	url = {https://doi.org/10.1007/s10817-011-9225-2},
	doi = {10.1007/s10817-011-9225-2},
	abstract = {This paper provides an introduction to the locally nameless approach to the representation of syntax with variable binding, focusing in particular on the use of this technique in formal proofs. First, we explain the benefits of representing bound variables with de Bruijn indices while retaining names for free variables. Then, we explain how to describe and manipulate syntax in that form, and show how to define and reason about judgments on locally nameless terms.},
	language = {en},
	number = {3},
	urldate = {2025-07-13},
	journal = {Journal of Automated Reasoning},
	author = {Charguéraud, Arthur},
	month = oct,
	year = {2012},
	keywords = {Binders, C++, Cofinite quantification, Convention Theory, Data Structures, Formal proofs, Functions of a Complex Variable, Lisp, Locally nameless, Metatheory, Syntax},
	pages = {363--408},
	file = {Full Text PDF:/home/chenson/mount/Zotero/storage/WBJWAZGI/Charguéraud - 2012 - The Locally Nameless Representation.pdf:application/pdf},
}

@article{Chashkin2024,
  author    = {Chashkin, A. V.},
  title     = {On Computing Partial {B}oolean Functions},
  journal   = {Matematicheskie Voprosy Kibernetiki},
  volume    = {22},
  pages     = {152--222},
  year      = {2024},
  publisher = {Fizmatlit},
  doi       = {10.20948/mvk-2024-152},
  url       = {https://library.keldysh.ru/mvk.asp?id=2024-152},
  note      = {In Russian}
}

@article{Chebyshev1852,
  author    = {Tchebichef, Pafnuty L.},
  title     = {M{\'e}moire sur les nombres premiers},
  journal   = {Journal de Math{\'e}matiques Pures et Appliqu{\'e}es},
  series    = {1},
  volume    = {17},
  pages     = {366--390},
  year      = {1852}
}

@inproceedings{ChenKabanets2015,
  author    = {Chen, Ruiwen and Kabanets, Valentine},
  title     = {Correlation Bounds and {\#SAT} Algorithms for Small Linear-Size Circuits},
  booktitle = {Computing and Combinatorics (COCOON 2015)},
  series    = {Lecture Notes in Computer Science},
  pages     = {211--222},
  publisher = {Springer},
  year      = {2015},
  doi       = {10.1007/978-3-319-21398-9_17}
}

@misc{CHLLTV2026,
  author        = {Chattopadhyay, Eshan and Hatami, Pooya and Lee, Chin Ho and Lovett, Shachar and
                   Tal, Avishay and Viola, Emanuele},
  title         = {Exponential Correlation Bounds for Polynomials},
  year          = {2026},
  eprint        = {2609.28839},
  archivePrefix = {arXiv},
  primaryClass  = {cs.CC},
  url           = {https://arxiv.org/abs/2609.28839}
}

@article{ChorGoldreich1988,
  author    = {Chor, Benny and Goldreich, Oded},
  title     = {Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication
               Complexity},
  journal   = {SIAM Journal on Computing},
  volume    = {17},
  number    = {2},
  pages     = {230--261},
  year      = {1988},
  doi       = {10.1137/0217015}
}

@article{ChungGrahamFranklShearer1986,
  author    = {Chung, Fan R. K. and Graham, Ronald L. and Frankl, Peter and Shearer, James B.},
  title     = {Some Intersection Theorems for Ordered Sets and Graphs},
  journal   = {Journal of Combinatorial Theory, Series A},
  volume    = {43},
  number    = {1},
  pages     = {23--37},
  year      = {1986},
  doi       = {10.1016/0097-3165(86)90019-1}
}

@book{CLRS2009,
  author    = {Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford},
  title     = {Introduction to Algorithms},
  edition   = {Third},
  publisher = {MIT Press},
  year      = {2009},
  isbn      = {978-0-262-03384-8}
}

@article{CMWBS2012,
  author  = {Cook, Stephen and McKenzie, Pierre and Wehr, Dustin and Braverman, Mark and
             Santhanam, Rahul},
  title   = {Pebbles and Branching Programs for Tree Evaluation},
  journal = {ACM Transactions on Computation Theory},
  volume  = {3},
  number  = {2},
  pages   = {4:1--4:43},
  year    = {2012}
}

@techreport{CookMertz2024,
  author      = {Cook, James and Mertz, Ian},
  title       = {Tree Evaluation is in Space {$O(\log n \cdot \log\log n)$}},
  institution = {Electronic Colloquium on Computational Complexity},
  number      = {TR23-174},
  note        = {Conference version in STOC 2024},
  year        = {2023}
}

@article{CookReckhow1973,
  author  = {Cook, Stephen A. and Reckhow, Robert A.},
  title   = {Time Bounded Random Access Machines},
  journal = {Journal of Computer and System Sciences},
  volume  = {7},
  number  = {4},
  year    = {1973},
  pages   = {354--375},
  doi     = {10.1016/S0022-0000(73)80029-7}
}

@article{CookReckhow1979,
  author    = {Cook, Stephen A. and Reckhow, Robert A.},
  title     = {The Relative Efficiency of Propositional Proof Systems},
  journal   = {The Journal of Symbolic Logic},
  volume    = {44},
  number    = {1},
  pages     = {36--50},
  year      = {1979},
  doi       = {10.2307/2273702}
}

@mastersthesis{Copes2018,
  author       = {Copes, Martín},
  title        = {A machine-checked proof of the Standardization Theorem 
                  in Lambda Calculus using multiple substitution},
  school       = {Universidad ORT Uruguay},
  year         = {2018}
}

@article{CoppersmithRivlin1992,
  author    = {Coppersmith, Don and Rivlin, Theodore J.},
  title     = {The Growth of Polynomials Bounded at Equally Spaced Points},
  journal   = {SIAM Journal on Mathematical Analysis},
  volume    = {23},
  number    = {4},
  pages     = {970--983},
  year      = {1992},
  doi       = {10.1137/0523054}
}

@article{CormodeMuthukrishnan2005,
  author    = {Cormode, Graham and Muthukrishnan, S.},
  title     = {An Improved Data Stream Summary: The {Count-Min} Sketch and its Applications},
  journal   = {Journal of Algorithms},
  volume    = {55},
  number    = {1},
  pages     = {58--75},
  year      = {2005},
  doi       = {10.1016/j.jalgor.2003.12.001},
  url       = {https://www.cs.ox.ac.uk/people/graham.cormode/pubs/papers/cm-full.pdf}
}

@article{Cover1973,
  author    = {Cover, Thomas M.},
  title     = {Enumerative Source Encoding},
  journal   = {IEEE Transactions on Information Theory},
  volume    = {19},
  number    = {1},
  pages     = {73--77},
  year      = {1973},
  doi       = {10.1109/TIT.1973.1054929}
}

@book{CoverThomas2006,
  author    = {Cover, Thomas M. and Thomas, Joy A.},
  title     = {Elements of Information Theory},
  edition   = {2},
  publisher = {Wiley-Interscience},
  year      = {2006},
  doi       = {10.1002/047174882X}
}

@inproceedings{CramerDamgardSchoenmakers1994,
  author       = {Ronald Cramer and Ivan Damg{\aa}rd and Berry Schoenmakers},
  title        = {Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols},
  booktitle    = {Advances in Cryptology -- CRYPTO '94},
  series       = {Lecture Notes in Computer Science},
  volume       = {839},
  pages        = {174--187},
  publisher    = {Springer},
  year         = {1994},
  doi          = {10.1007/3-540-48658-5_19}
}

@book{            Cutland1980,
  author       = {Cutland, Nigel J.},
  title        = {Computability: An Introduction to Recursive Function Theory},
  year         = {1980},
  publisher    = {Cambridge University Press},
  address      = {Cambridge},
  isbn         = {978-0-521-29465-2}
}

@book{CyganEtAl2015,
  author    = {Cygan, Marek and Fomin, Fedor V. and Kowalik, {\L}ukasz and Lokshtanov, Daniel and
               Marx, D{\'a}niel and Pilipczuk, Marcin and Pilipczuk, Micha{\l} and Saurabh, Saket},
  title     = {Parameterized Algorithms},
  publisher = {Springer},
  address   = {Cham},
  year      = {2015},
  doi       = {10.1007/978-3-319-21275-3}
}

@inproceedings{Danielsson2008,
author = {Danielsson, Nils Anders},
title = {Lightweight semiformal time complexity analysis for purely functional data structures},
year = {2008},
isbn = {9781595936899},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1328438.1328457},
doi = {10.1145/1328438.1328457},
abstract = {Okasaki and others have demonstrated how purely functional data structures that are efficient even in the presence of persistence can be constructed. To achieve good time bounds essential use is often made of laziness. The associated complexity analysis is frequently subtle, requiring careful attention to detail, and hence formalising it is valuable. This paper describes a simple library which can be used to make the analysis of a class of purely functional data structures and algorithms almost fully formal. The basic idea is to use the type system to annotate every function with the time required to compute its result. An annotated monad is used to combine time complexity annotations. The library has been used to analyse some existing data structures, for instance the deque operations of Hinze and Paterson's finger trees.},
booktitle = {Proceedings of the 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages},
pages = {133–144},
numpages = {12},
keywords = {purely functional data structures, lazy evaluation, dependent types, amortised time complexity},
location = {San Francisco, California, USA},
series = {POPL '08}
}

@article{Darwiche2001,
  author  = {Darwiche, Adnan},
  title   = {Decomposable Negation Normal Form},
  journal = {Journal of the ACM},
  volume  = {48},
  number  = {4},
  pages   = {608--647},
  year    = {2001},
  doi     = {10.1145/502090.502091}
}

@article{DavisLogemannLoveland1962,
  author = {Davis, Martin and Logemann, George and Loveland, Donald},
  title = {A Machine Program for Theorem-Proving},
  journal = {Communications of the ACM},
  volume = {5},
  number = {7},
  pages = {394--397},
  year = {1962},
  doi = {10.1145/368273.368557},
  url = {https://doi.org/10.1145/368273.368557}
}

@article{DavisPutnam1960,
  author    = {Davis, Martin and Putnam, Hilary},
  title     = {A Computing Procedure for Quantification Theory},
  journal   = {Journal of the ACM},
  volume    = {7},
  number    = {3},
  pages     = {201--215},
  year      = {1960},
  doi       = {10.1145/321033.321034}
}

@misc{Demaine2015VanEmdeBoas,
  author       = {Demaine, Erik},
  title        = {Lecture 4: Divide and Conquer: van {Emde Boas} Trees},
  howpublished = {MIT OpenCourseWare, 6.046J Design and Analysis of Algorithms},
  note         = {Lecture notes acknowledge personal communication with Michael Bender, 2001},
  year         = {2015},
  url          = {https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/49c8fa24dffce58052c90d46ac800387_MIT6_046JS15_lec04.pdf}
}

@article{DietzfelbingerHagerupKatajainenPenttonen1997,
  author    = {Dietzfelbinger, Martin and Hagerup, Torben and Katajainen, Jyrki and
               Penttonen, Martti},
  title     = {A Reliable Randomized Algorithm for the Closest-Pair Problem},
  journal   = {Journal of Algorithms},
  volume    = {25},
  number    = {1},
  pages     = {19--51},
  year      = {1997},
  doi       = {10.1006/jagm.1997.0873}
}

@article{Dijkstra1959,
  author  = {Dijkstra, Edsger W.},
  title   = {A Note on Two Problems in Connexion with Graphs},
  journal = {Numerische Mathematik},
  volume  = {1},
  pages   = {269--271},
  year    = {1959},
  doi     = {10.1007/BF01386390}
}

@article{DIL2007,
  author  = {Demaine, Erik D. and Iacono, John and Langerman, Stefan},
  title   = {Retroactive Data Structures},
  journal = {ACM Transactions on Algorithms},
  volume  = {3},
  number  = {2},
  year    = {2007},
  pages   = {13},
  url     = {https://erikdemaine.org/papers/Retroactive_TALG/}
}

@techreport{Dinur2005,
  author      = {Dinur, Irit},
  title       = {The {PCP} Theorem by Gap Amplification},
  institution = {Electronic Colloquium on Computational Complexity},
  number      = {TR05-046},
  note        = {Revision 1, 26 September 2005},
  year        = {2005}
}

@article{Dinur2007,
  author    = {Dinur, Irit},
  title     = {The {PCP} Theorem by Gap Amplification},
  journal   = {Journal of the ACM},
  volume    = {54},
  number    = {3},
  pages     = {12},
  year      = {2007},
  doi       = {10.1145/1236457.1236459}
}

@book{DowneyFellows1999,
  author    = {Downey, Rodney G. and Fellows, Michael R.},
  title     = {Parameterized Complexity},
  series    = {Monographs in Computer Science},
  publisher = {Springer},
  address   = {New York},
  year      = {1999},
  doi       = {10.1007/978-1-4612-0515-9}
}

@article{DucasEtAl2018,
  author    = {Ducas, L{\'e}o and Kiltz, Eike and Lepoint, Tancr{\`e}de and Lyubashevsky, Vadim
               and Schwabe, Peter and Seiler, Gregor and Stehl{\'e}, Damien},
  title     = {{CRYSTALS-Dilithium}: A Lattice-Based Digital Signature Scheme},
  journal   = {IACR Transactions on Cryptographic Hardware and Embedded Systems},
  volume    = {2018},
  number    = {1},
  pages     = {238--268},
  year      = {2018},
  doi       = {10.13154/tches.v2018.i1.238-268}
}

@inproceedings{DunkelmanKellerShamir2012,
  author    = {Dunkelman, Orr and Keller, Nathan and Shamir, Adi},
  title     = {Minimalism in Cryptography: The {E}ven--{M}ansour Scheme Revisited},
  booktitle = {Advances in Cryptology -- EUROCRYPT 2012},
  series    = {Lecture Notes in Computer Science},
  volume    = {7237},
  pages     = {336--354},
  publisher = {Springer},
  year      = {2012},
  doi       = {10.1007/978-3-642-29011-4_21}
}

@article{EHKV1989,
  author       = {Ehrenfeucht, Andrzej and Haussler, David and Kearns, Michael and Valiant, Leslie},
  title        = {A General Lower Bound on the Number of Examples Needed for Learning},
  journal      = {Information and Computation},
  volume       = {82},
  number       = {3},
  pages        = {247--261},
  year         = {1989},
  issn         = {0890-5401},
  url          = {https://doi.org/10.1016/0890-5401(89)90002-3},
  doi          = {10.1016/0890-5401(89)90002-3},
  publisher    = {Academic Press}
}

@article{EhlichZeller1964,
  author    = {Ehlich, Hartmut and Zeller, Karl},
  title     = {Schwankung von {Polynomen} zwischen {Gitterpunkten}},
  journal   = {Mathematische Zeitschrift},
  volume    = {86},
  number    = {1},
  pages     = {41--44},
  year      = {1964},
  doi       = {10.1007/BF01111276}
}

@incollection{ErdosLovasz1975,
  author    = {Erd{\H{o}}s, Paul and Lov{\'a}sz, L{\'a}szl{\'o}},
  title     = {Problems and Results on 3-Chromatic Hypergraphs and Some Related Questions},
  booktitle = {Infinite and Finite Sets},
  series    = {Colloquia Mathematica Societatis J{\'a}nos Bolyai},
  volume    = {10},
  publisher = {North-Holland},
  pages     = {609--627},
  year      = {1975}
}

@article{ErdosRado1960,
  author    = {Erd{\H{o}}s, Paul and Rado, Richard},
  title     = {Intersection Theorems for Systems of Sets},
  journal   = {Journal of the London Mathematical Society},
  volume    = {s1-35},
  number    = {1},
  pages     = {85--90},
  year      = {1960},
  doi       = {10.1112/jlms/s1-35.1.85}
}

@article{ErdosSpencer1991,
  author    = {Erd{\H{o}}s, Paul and Spencer, Joel},
  title     = {Lopsided {Lov{\'a}sz} Local Lemma and {Latin} Transversals},
  journal   = {Discrete Applied Mathematics},
  volume    = {30},
  number    = {2--3},
  pages     = {151--154},
  year      = {1991},
  doi       = {10.1016/0166-218X(91)90040-4}
}

@article{EricksonVanDerHoogMiltzow2024,
  author  = {Erickson, Jeff and van der Hoog, Ivor and Miltzow, Tillmann},
  title   = {Smoothing the Gap Between {NP} and {$\exists\mathbb{R}$}},
  journal = {SIAM Journal on Computing},
  volume  = {53},
  number  = {6},
  year    = {2024},
  pages   = {FOCS20-102--FOCS20-138},
  doi     = {10.1137/20M1385287},
  eprint  = {1912.02278},
  archivePrefix = {arXiv}
}

@article{EvenMansour1997,
  author    = {Even, Shimon and Mansour, Yishay},
  title     = {A Construction of a Cipher from a Single Pseudorandom Permutation},
  journal   = {Journal of Cryptology},
  volume    = {10},
  number    = {3},
  pages     = {151--161},
  year      = {1997},
  doi       = {10.1007/s001459900025}
}

@article{EvenSelmanYacobi1984,
  author    = {Even, Shimon and Selman, Alan L. and Yacobi, Yacov},
  title     = {The Complexity of Promise Problems with Applications to Public-Key Cryptography},
  journal   = {Information and Control},
  volume    = {61},
  number    = {2},
  pages     = {159--173},
  year      = {1984},
  doi       = {10.1016/S0019-9958(84)80056-X}
}

@incollection{Fagin1974,
  author    = {Fagin, Ronald},
  title     = {Generalized First-Order Spectra and Polynomial-Time Recognizable Sets},
  booktitle = {Complexity of Computation},
  editor    = {Karp, Richard M.},
  series    = {SIAM-AMS Proceedings},
  volume    = {7},
  pages     = {43--73},
  year      = {1974}
}

@article{FeigeGoldwasserLovaszSafraSzegedy1996,
  author    = {Feige, Uriel and Goldwasser, Shafi and Lov{\'a}sz, L{\'a}szl{\'o} and Safra, Shmuel
               and Szegedy, Mario},
  title     = {Interactive Proofs and the Hardness of Approximating Cliques},
  journal   = {Journal of the ACM},
  volume    = {43},
  number    = {2},
  pages     = {268--292},
  year      = {1996},
  doi       = {10.1145/226643.226652}
}

@article{Fenner2003,
  author    = {Fenner, Stephen A.},
  title     = {{PP}-Lowness and a Simple Definition of {AWPP}},
  journal   = {Theory of Computing Systems},
  volume    = {36},
  number    = {2},
  pages     = {199--212},
  year      = {2003},
  doi       = {10.1007/s00224-002-1089-8},
  url       = {https://eccc.weizmann.ac.il/report/2002/036/}
}

@article{FennerEtAl2003,
  author  = {Fenner, Stephen A. and Fortnow, Lance J. and Kurtz, Stuart A. and Li, Lide},
  title   = {An Oracle Builder's Toolkit},
  journal = {Information and Computation},
  volume  = {182},
  number  = {2},
  pages   = {95--136},
  year    = {2003},
  doi     = {10.1016/S0890-5401(03)00018-X},
  url     = {https://lance.fortnow.com/papers/files/obt.pdf}
}

@article{FennerFortnowKurtz1994,
  author    = {Fenner, Stephen A. and Fortnow, Lance J. and Kurtz, Stuart A.},
  title     = {Gap-Definable Counting Classes},
  journal   = {Journal of Computer and System Sciences},
  volume    = {48},
  number    = {1},
  pages     = {116--148},
  year      = {1994},
  doi       = {10.1016/S0022-0000(05)80024-8}
}

@inproceedings{FiatShamir1986,
  author       = {Amos Fiat and Adi Shamir},
  title        = {How to Prove Yourself: Practical Solutions to Identification and Signature
                  Problems},
  booktitle    = {Advances in Cryptology -- CRYPTO '86},
  series       = {Lecture Notes in Computer Science},
  volume       = {263},
  pages        = {186--194},
  publisher    = {Springer},
  year         = {1987},
  doi          = {10.1007/3-540-47721-7_12}
}

@inproceedings{FindGolovnevHirschKulikov2016,
  author    = {Find, Magnus Gausdal and Golovnev, Alexander and Hirsch, Edward A. and
               Kulikov, Alexander S.},
  title     = {A Better-than-{$3n$} Lower Bound for the Circuit Complexity of an Explicit
               Function},
  booktitle = {IEEE 57th Annual Symposium on Foundations of Computer Science},
  series    = {FOCS 2016},
  pages     = {89--98},
  year      = {2016},
  doi       = {10.1109/FOCS.2016.19}
}

@article{ FLP1985,
  author    = {Fischer, Michael J. and Lynch, Nancy A. and Paterson, Michael S.},
  title     = {Impossibility of Distributed Consensus with One Faulty Process},
  year      = {1985},
  issue_date = {April 1985},
  publisher = {Association for Computing Machinery},
  address   = {New York, NY, USA},
  volume    = {32},
  number    = {2},
  issn      = {0004-5411},
  url       = {https://doi.org/10.1145/3149.214121},
  doi       = {10.1145/3149.214121},
  journal   = {J. ACM},
  month     = {apr},
  pages     = {374–382},
  numpages  = {9}
}

@book{FlumGrohe2006,
  author    = {Flum, J{\"o}rg and Grohe, Martin},
  title     = {Parameterized Complexity Theory},
  series    = {Texts in Theoretical Computer Science. An EATCS Series},
  publisher = {Springer},
  address   = {Berlin, Heidelberg},
  year      = {2006},
  doi       = {10.1007/3-540-29953-X}
}

@book{Forney1966,
  author    = {Forney, Jr., G. David},
  title     = {Concatenated Codes},
  publisher = {MIT Press},
  year      = {1966}
}

@incollection{Fortnow1997,
  author    = {Fortnow, Lance},
  title     = {Counting Complexity},
  booktitle = {Complexity Theory Retrospective II},
  editor    = {Hemaspaandra, Lane A. and Selman, Alan L.},
  publisher = {Springer},
  pages     = {81--107},
  year      = {1997},
  doi       = {10.1007/978-1-4612-1872-2_4},
  url       = {https://lance.fortnow.com/papers/files/counting.pdf}
}

@article{FortnowReingold1996,
  author    = {Fortnow, Lance and Reingold, Nick},
  title     = {{PP} Is Closed under Truth-Table Reductions},
  journal   = {Information and Computation},
  volume    = {124},
  number    = {1},
  pages     = {1--6},
  year      = {1996},
  doi       = {10.1006/inco.1996.0001}
}

@article{FredmanWillard1993,
  author  = {Fredman, Michael L. and Willard, Dan E.},
  title   = {Surpassing the Information Theoretic Bound with Fusion Trees},
  journal = {Journal of Computer and System Sciences},
  volume  = {47},
  number  = {3},
  year    = {1993},
  pages   = {424--436},
  doi     = {10.1016/0022-0000(93)90040-4}
}

@article{Friedgut1998,
  author    = {Friedgut, Ehud},
  title     = {{Boolean} Functions With Low Average Sensitivity Depend On Few Coordinates},
  journal   = {Combinatorica},
  volume    = {18},
  number    = {1},
  pages     = {27--35},
  year      = {1998},
  doi       = {10.1007/PL00009809}
}

@article{FurstSaxeSipser1984,
  author    = {Furst, Merrick and Saxe, James B. and Sipser, Michael},
  title     = {Parity, Circuits, and the Polynomial-Time Hierarchy},
  journal   = {Mathematical Systems Theory},
  volume    = {17},
  number    = {1},
  pages     = {13--27},
  year      = {1984},
  doi       = {10.1007/BF01744431}
}

@article{Gabbay2002,
author = {Gabbay, Murdoch J. and Pitts, Andrew M.},
title = {A New Approach to Abstract Syntax with Variable Binding},
year = {2002},
issue_date = {Jul 2002},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
volume = {13},
number = {3–5},
issn = {0934-5043},
url = {https://doi.org/10.1007/s001650200016},
doi = {10.1007/s001650200016},
abstract = {The permutation model of set theory with atoms (FM-sets), devised by Fraenkel and Mostowski in the 1930s, supports notions of ‘name-abstraction’ and ‘fresh name’ that provide a new way to represent, compute with, and reason about the syntax of formal systems involving variable-binding operations. Inductively defined FM-sets involving the name-abstraction set former (together with Cartesian product and disjoint union) can correctly encode syntax modulo renaming of bound variables. In this way, the standard theory of algebraic data types can be extended to encompass signatures involving binding operators. In particular, there is an associated notion of structural recursion for defining syntax-manipulating functions (such as capture avoiding substitution, set of free variables, etc.) and a notion of proof by structural induction, both of which remain pleasingly close to informal practice in computer science.},
journal = {Form. Asp. Comput.},
month = jul,
pages = {341–363},
numpages = {23},
keywords = {Keywords: Abstract syntax; Alpha-conversion; Permutation actions; Set theory; Structural induction}
}

@book{GareyJohnson1979,
  author    = {Garey, Michael R. and Johnson, David S.},
  title     = {Computers and Intractability: A Guide to the Theory of {NP}-Completeness},
  publisher = {W. H. Freeman},
  address   = {San Francisco},
  year      = {1979}
}

@inproceedings{Gentry2009,
  author    = {Gentry, Craig},
  title     = {Fully Homomorphic Encryption Using Ideal Lattices},
  booktitle = {Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing},
  series    = {STOC '09},
  pages     = {169--178},
  publisher = {ACM},
  year      = {2009},
  doi       = {10.1145/1536414.1536440},
  url       = {https://doi.org/10.1145/1536414.1536440}
}

@inproceedings{GentryHaleviVaikuntanathan2010,
  author    = {Gentry, Craig and Halevi, Shai and Vaikuntanathan, Vinod},
  title     = {{$i$}-Hop Homomorphic Encryption and Rerandomizable {Yao} Circuits},
  booktitle = {Advances in Cryptology -- CRYPTO 2010},
  series    = {Lecture Notes in Computer Science},
  volume    = {6223},
  pages     = {155--172},
  publisher = {Springer},
  year      = {2010},
  doi       = {10.1007/978-3-642-14623-7_9},
  url       = {https://doi.org/10.1007/978-3-642-14623-7_9}
}

@inproceedings{GentrySahaiWaters2013,
  author    = {Gentry, Craig and Sahai, Amit and Waters, Brent},
  title     = {Homomorphic Encryption from Learning with Errors:
               Conceptually-Simpler, Asymptotically-Faster, Attribute-Based},
  booktitle = {Advances in Cryptology -- CRYPTO 2013},
  series    = {Lecture Notes in Computer Science},
  volume    = {8042},
  pages     = {75--92},
  publisher = {Springer},
  year      = {2013},
  doi       = {10.1007/978-3-642-40041-4_5},
  url       = {https://eprint.iacr.org/2013/340}
}

@article{GGM1986,
  author    = {Goldreich, Oded and Goldwasser, Shafi and Micali, Silvio},
  title     = {How to Construct Random Functions},
  journal   = {Journal of the ACM},
  volume    = {33},
  number    = {4},
  pages     = {792--807},
  year      = {1986},
  url       = {https://www.wisdom.weizmann.ac.il/~oded/X/ggm-jacm.pdf}
}

@article{Gilbert1952,
  author    = {Gilbert, E. N.},
  title     = {A Comparison of Signalling Alphabets},
  journal   = {Bell System Technical Journal},
  volume    = {31},
  number    = {3},
  pages     = {504--522},
  year      = {1952},
  doi       = {10.1002/j.1538-7305.1952.tb01393.x}
}

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

@article{        Girard1987,
  title={Linear logic},
  author={Girard, Jean-Yves},
  journal={Theoretical Computer Science},
  volume={50},
  number={1},
  year={1987},
  pages={1--101},
  issn={0304-3975},
  doi={10.1016/0304-3975(87)90045-4},
  url={https://www.sciencedirect.com/science/article/pii/0304397587900454},
  abstract={The familiar connective of negation is broken into two operations: linear negation which is the purely negative part of negation and the modality "of course" which has the meaning of a reaffirmation. Following this basic discovery, a completely new approach to the whole area between constructive logics and programmation is initiated.}
}

@inbook{          Girard1995,
  place={Cambridge},
  series={London Mathematical Society Lecture Note Series},
  title={Linear Logic: its syntax and semantics},
  booktitle={Advances in Linear Logic},
  publisher={Cambridge University Press},
  author={Girard, J.-Y.},
  editor={Girard, Jean-Yves and Lafont, Yves and Regnier, LaurentEditors},
  year={1995},
  pages={1–42},
  collection={London Mathematical Society Lecture Note Series}
}

@inproceedings{GKST2016,
  author    = {Golovnev, Alexander and Kulikov, Alexander S. and Smal, Alexander V. and
               Tamaki, Suguru},
  title     = {Circuit Size Lower Bounds and {\#SAT} Upper Bounds Through a General Framework},
  booktitle = {41st International Symposium on Mathematical Foundations of Computer Science
               (MFCS 2016)},
  series    = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume    = {58},
  pages     = {45:1--45:16},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  year      = {2016},
  doi       = {10.4230/LIPIcs.MFCS.2016.45}
}

@article{GlasserPavanSelmanZhang2008,
  author    = {Gla{\ss}er, Christian and Pavan, A. and Selman, Alan L. and Zhang, Liyu},
  title     = {Splitting {NP}-Complete Sets},
  journal   = {SIAM Journal on Computing},
  volume    = {37},
  number    = {5},
  pages     = {1517--1535},
  year      = {2008},
  doi       = {10.1137/060673886}
}

@book{Goldreich2001,
  author    = {Goldreich, Oded},
  title     = {Foundations of Cryptography, Volume 1: Basic Tools},
  publisher = {Cambridge University Press},
  year      = {2001},
  doi       = {10.1017/CBO9780511546891}
}

@incollection{Goldreich2006,
  author    = {Goldreich, Oded},
  title     = {On Promise Problems: A Survey},
  booktitle = {Theoretical Computer Science: Essays in Memory of {S}himon {E}ven},
  series    = {Lecture Notes in Computer Science},
  volume    = {3895},
  pages     = {254--290},
  publisher = {Springer},
  year      = {2006},
  doi       = {10.1007/11685654_12}
}

@techreport{Goldreich2024TreeEval,
  author      = {Goldreich, Oded},
  title       = {On the {Cook}--{Mertz} Tree Evaluation procedure},
  institution = {Electronic Colloquium on Computational Complexity},
  number      = {TR24-109},
  note        = {Revision 2, 27 December 2024},
  year        = {2024}
}

@inproceedings{GoldreichLevin1989,
  author    = {Goldreich, Oded and Levin, Leonid A.},
  title     = {A Hard-Core Predicate for All One-Way Functions},
  booktitle = {Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing},
  pages     = {25--32},
  year      = {1989},
  doi       = {10.1145/73007.73010},
  url       = {https://www.wisdom.weizmann.ac.il/~oded/X/gl.pdf}
}

@article{GoldreichMicaliWigderson1991,
  author  = {Goldreich, Oded and Micali, Silvio and Wigderson, Avi},
  title   = {Proofs that Yield Nothing but Their Validity or All Languages in {NP} Have
             Zero-Knowledge Proof Systems},
  journal = {Journal of the ACM},
  volume  = {38},
  number  = {3},
  pages   = {690--728},
  year    = {1991},
  doi     = {10.1145/116825.116852}
}

@article{Goldschlager1977,
  author    = {Goldschlager, Leslie M.},
  title     = {The Monotone and Planar Circuit Value Problems Are Log Space Complete for {$P$}},
  journal   = {ACM SIGACT News},
  volume    = {9},
  number    = {2},
  pages     = {25--29},
  year      = {1977},
  doi       = {10.1145/1008354.1008356}
}

@article{GoldwasserKalaiRothblum2015,
  author  = {Goldwasser, Shafi and Kalai, Yael Tauman and Rothblum, Guy N.},
  title   = {Delegating Computation: Interactive Proofs for Muggles},
  journal = {Journal of the ACM},
  volume  = {62},
  number  = {4},
  pages   = {27:1--27:64},
  year    = {2015},
  doi     = {10.1145/2699436}
}

@article{GoldwasserMicaliRackoff1989,
  author  = {Goldwasser, Shafi and Micali, Silvio and Rackoff, Charles},
  title   = {The Knowledge Complexity of Interactive Proof Systems},
  journal = {SIAM Journal on Computing},
  volume  = {18},
  number  = {1},
  pages   = {186--208},
  year    = {1989},
  doi     = {10.1137/0218012}
}

@article{GoldwasserMicaliRivest1988,
  author  = {Goldwasser, Shafi and Micali, Silvio and Rivest, Ronald L.},
  title   = {A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks},
  journal = {SIAM Journal on Computing},
  volume  = {17},
  number  = {2},
  pages   = {281--308},
  year    = {1988},
  doi     = {10.1137/0217017},
  url     = {https://doi.org/10.1137/0217017}
}

@inproceedings{GoldwasserSipser1986,
  author    = {Goldwasser, Shafi and Sipser, Michael},
  title     = {Private Coins versus Public Coins in Interactive Proof Systems},
  booktitle = {Proceedings of the 18th Annual ACM Symposium on Theory of Computing},
  pages     = {59--68},
  year      = {1986},
  doi       = {10.1145/12130.12137}
}

@inproceedings{GoosPitassiWatson2017,
  author    = {G{\"o}{\"o}s, Mika and Pitassi, Toniann and Watson, Thomas},
  title     = {Query-to-Communication Lifting for {BPP}},
  booktitle = {58th Annual Symposium on Foundations of Computer Science (FOCS)},
  pages     = {132--143},
  year      = {2017},
  doi       = {10.1109/FOCS.2017.21}
}

@article{GoosPitassiWatson2018,
  author    = {G{\"o}{\"o}s, Mika and Pitassi, Toniann and Watson, Thomas},
  title     = {Deterministic Communication vs. Partition Number},
  journal   = {SIAM Journal on Computing},
  volume    = {47},
  number    = {6},
  pages     = {2435--2450},
  year      = {2018},
  doi       = {10.1137/16M1059369}
}

@article{GotsmanLinial1992,
  author    = {Gotsman, Craig and Linial, Nathan},
  title     = {The Equivalence of Two Problems on the Cube},
  journal   = {Journal of Combinatorial Theory, Series A},
  volume    = {61},
  number    = {1},
  pages     = {142--146},
  year      = {1992},
  doi       = {10.1016/0097-3165(92)90060-8}
}

@inproceedings{Grover1996,
  author    = {Grover, Lov K.},
  title     = {A Fast Quantum Mechanical Algorithm for Database Search},
  booktitle = {Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC)},
  pages     = {212--219},
  year      = {1996},
  doi       = {10.1145/237814.237866}
}

@inproceedings{GuoKoppartySudan2013,
  author = {Guo, Alan and Kopparty, Swastik and Sudan, Madhu},
  title = {New affine-invariant codes from lifting},
  booktitle = {Proceedings of the 4th Innovations in Theoretical Computer Science Conference},
  series = {ITCS '13},
  pages = {529--540},
  year = {2013},
  url = {https://people.csail.mit.edu/madhu/papers/2012/lifts-conf.pdf}
}

@misc{GuruswamiRudraSudan2019,
  author    = {Guruswami, Venkatesan and Rudra, Atri and Sudan, Madhu},
  title     = {Essential Coding Theory},
  note      = {Draft book, 2019},
  year      = {2019},
  url       = {https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/}
}

@inproceedings{Hagerup1998,
  author    = {Hagerup, Torben},
  title     = {Sorting and Searching on the Word {RAM}},
  booktitle = {STACS 98},
  series    = {Lecture Notes in Computer Science},
  volume    = {1373},
  pages     = {366--398},
  publisher = {Springer},
  year      = {1998},
  doi       = {10.1007/BFb0028575}
}

@techreport{HaitnerVadhan2017,
  author      = {Haitner, Iftach and Vadhan, Salil},
  title       = {The Many Entropies in One-Way Functions},
  institution = {Electronic Colloquium on Computational Complexity},
  number      = {TR17-084},
  year        = {2017},
  url         = {https://eccc.weizmann.ac.il/report/2017/084/}
}

@article{Haken1985,
  author  = {Haken, Armin},
  title   = {The Intractability of Resolution},
  journal = {Theoretical Computer Science},
  volume  = {39},
  pages   = {297--308},
  year    = {1985},
  doi     = {10.1016/0304-3975(85)90144-6},
  url     = {https://doi.org/10.1016/0304-3975(85)90144-6}
}

@article{Hamming1950,
  author    = {Hamming, R. W.},
  title     = {Error Detecting and Error Correcting Codes},
  journal   = {The Bell System Technical Journal},
  volume    = {29},
  number    = {2},
  pages     = {147--160},
  year      = {1950},
  doi       = {10.1002/j.1538-7305.1950.tb00463.x}
}

@article{HanHemaspaandraThierauf1997,
  author    = {Han, Yenjo and Hemaspaandra, Lane A. and Thierauf, Thomas},
  title     = {Threshold computation and cryptographic security},
  journal   = {SIAM Journal on Computing},
  volume    = {26},
  number    = {1},
  pages     = {59--78},
  year      = {1997},
  doi       = {10.1137/S0097539792240467}
}

@inproceedings{HartmanisSimon1974,
  author    = {Hartmanis, Juris and Simon, Janos},
  title     = {On the Power of Multiplication in Random Access Machines},
  booktitle = {15th Annual Symposium on Switching and Automata Theory (SWAT 1974)},
  year      = {1974},
  pages     = {13--23},
  publisher = {IEEE},
  doi       = {10.1109/SWAT.1974.20}
}

@inproceedings{Hastad1986,
  author    = {H{\aa}stad, Johan},
  title     = {Almost Optimal Lower Bounds for Small Depth Circuits},
  booktitle = {Proceedings of the 18th Annual ACM Symposium on Theory of Computing},
  pages     = {6--20},
  year      = {1986},
  doi       = {10.1145/12130.12132}
}

@article{Hastad2001,
  author  = {H{\aa}stad, Johan},
  title   = {Some Optimal Inapproximability Results},
  journal = {Journal of the ACM},
  volume  = {48},
  number  = {4},
  pages   = {798--859},
  year    = {2001},
  doi     = {10.1145/502090.502098}
}

@article{Haussler1992,
  author       = {Haussler, David},
  title        = {Decision Theoretic Generalizations of the {PAC} Model for Neural Net and Other Learning Applications},
  journal      = {Information and Computation},
  volume       = {100},
  number       = {1},
  pages        = {78--150},
  year         = {1992},
  issn         = {0890-5401},
  doi          = {10.1016/0890-5401(92)90010-D}
}

@inproceedings{HemaspaandraEtAl2018,
  author = {Hemaspaandra, Edith and Hemaspaandra, Lane A. and Spakowski, Holger and
    Watanabe, Osamu},
  title = {The Robustness of {LWPP} and {WPP}, with an Application to Graph Reconstruction},
  booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science},
  series = {Leibniz International Proceedings in Informatics},
  volume = {117},
  pages = {51:1--51:14},
  year = {2018},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  doi = {10.4230/LIPIcs.MFCS.2018.51}
}

@article{         Hennessy1985,
  author       = {Matthew Hennessy and
                  Robin Milner},
  title        = {Algebraic Laws for Nondeterminism and Concurrency},
  journal      = {J. {ACM}},
  volume       = {32},
  number       = {1},
  pages        = {137--161},
  year         = {1985},
  url          = {https://doi.org/10.1145/2455.2460},
  doi          = {10.1145/2455.2460},
  timestamp    = {Tue, 06 Nov 2018 12:51:45 +0100},
  biburl       = {https://dblp.org/rec/journals/jacm/HennessyM85.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@article{HILL1999,
  author    = {Håstad, Johan and Impagliazzo, Russell and Levin, Leonid A. and Luby, Michael},
  title     = {A Pseudorandom Generator from Any One-Way Function},
  journal   = {SIAM Journal on Computing},
  volume    = {28},
  number    = {4},
  pages     = {1364--1396},
  year      = {1999},
  doi       = {10.1137/S0097539793244708},
  url       = {https://doi.org/10.1137/S0097539793244708}
}

@inproceedings{Hirahara2018,
  author    = {Hirahara, Shuichi},
  title     = {Non-Black-Box Worst-Case to Average-Case Reductions within {NP}},
  booktitle = {2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)},
  publisher = {IEEE Computer Society},
  year      = {2018},
  pages     = {247--258},
  doi       = {10.1109/FOCS.2018.00032},
  note      = {Full version in Electronic Colloquium on Computational Complexity (ECCC), TR18-138; definition numbers follow ECCC TR18-138}
}

@inproceedings{Hirahara2022,
  author    = {Hirahara, Shuichi},
  title     = {{NP}-Hardness of Learning Programs and Partial {MCSP}},
  booktitle = {2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)},
  pages     = {968--979},
  publisher = {IEEE},
  year      = {2022},
  doi       = {10.1109/FOCS54457.2022.00095},
  url       = {https://eccc.weizmann.ac.il/report/2022/119/download},
  note      = {Full version in Electronic Colloquium on Computational Complexity (ECCC), TR22-119}
}

@article{HMPST1993,
  author    = {Hajnal, Andr{\'a}s and Maass, Wolfgang and Pudl{\'a}k, Pavel and
               Szegedy, M{\'a}ri{\'o} and Tur{\'a}n, Gy{\"o}rgy},
  title     = {Threshold Circuits of Bounded Depth},
  journal   = {Journal of Computer and System Sciences},
  volume    = {46},
  number    = {2},
  pages     = {129--154},
  year      = {1993},
  doi       = {10.1016/0022-0000(93)90001-D}
}

@article{Hoeffding1963,
  author    = {Hoeffding, Wassily},
  title     = {Probability Inequalities for Sums of Bounded Random Variables},
  journal   = {Journal of the American Statistical Association},
  volume    = {58},
  number    = {301},
  pages     = {13--30},
  year      = {1963},
  doi       = {10.1080/01621459.1963.10500830}
}

@book{Holcombe1982,
  title={Algebraic automata theory},
  author={Holcombe, W. M. L.},
  volume={1},
  series={Cambridge Studies in Advanced Mathematics},
  year={1982},
  publisher={Cambridge University Press},
  isbn={0-521-60492-3}
}

@inproceedings{Holenstein2005,
  author    = {Holenstein, Thomas},
  title     = {Key Agreement from Weak Bit Agreement},
  booktitle = {Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing},
  year      = {2005},
  url       = {https://crypto.ethz.ch/publications/files/Holens05.pdf}
}

@inproceedings{Holenstein2006,
  author    = {Holenstein, Thomas},
  title     = {Pseudorandom Generators from One-Way Functions: A Simple Construction for
               Any Hardness},
  booktitle = {Theory of Cryptography (TCC 2006)},
  year      = {2006},
  url       = {https://crypto.ethz.ch/publications/files/Holens06.pdf}
}

@article{Holenstein2009,
  author  = {Holenstein, Thomas},
  title   = {Parallel Repetition: Simplifications and the No-Signaling Case},
  journal = {Theory of Computing},
  volume  = {5},
  number  = {8},
  pages   = {141--172},
  year    = {2009},
  doi     = {10.4086/toc.2009.v005a008}
}

@article{HooryLinialWigderson2006,
  author    = {Hoory, Shlomo and Linial, Nathan and Wigderson, Avi},
  title     = {Expander Graphs and Their Applications},
  journal   = {Bulletin of the American Mathematical Society},
  volume    = {43},
  number    = {4},
  pages     = {439--561},
  year      = {2006},
  doi       = {10.1090/S0273-0979-06-01126-8}
}

@book{            Hopcroft2006,
author = {Hopcroft, John E. and Motwani, Rajeev and Ullman, Jeffrey D.},
title = {Introduction to Automata Theory, Languages, and Computation (3rd Edition)},
year = {2006},
isbn = {0321455363},
publisher = {Addison-Wesley Longman Publishing Co., Inc.},
address = {USA}
}

@article{Huang2019,
  author    = {Huang, Hao},
  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}
}

@article{HuntMaratheRadhakrishnanStearns1998,
  author    = {Hunt III, Harry B. and Marathe, Madhav V. and Radhakrishnan, Venkatesh and Stearns, Richard E.},
  title     = {The Complexity of Planar Counting Problems},
  journal   = {SIAM Journal on Computing},
  volume    = {27},
  number    = {4},
  pages     = {1142--1167},
  year      = {1998},
  doi       = {10.1137/S0097539793304601}
}

@inproceedings{Ilango2020,
  author    = {Ilango, Rahul},
  title     = {Approaching {MCSP} from Above and Below: Hardness for a Conditional Variant and {$\mathsf{AC}^0[p]$}},
  booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  series    = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume    = {151},
  pages     = {34:1--34:26},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  year      = {2020},
  doi       = {10.4230/LIPIcs.ITCS.2020.34}
}

@inproceedings{Ilango2020FOCS,
  author    = {Ilango, Rahul},
  title     = {Constant Depth Formula and Partial Function Versions of {MCSP} are Hard},
  booktitle = {2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)},
  pages     = {424--433},
  publisher = {IEEE},
  year      = {2020},
  doi       = {10.1109/FOCS46700.2020.00047},
  url       = {https://eccc.weizmann.ac.il/report/2020/183/download},
  note      = {Full version in Electronic Colloquium on Computational Complexity (ECCC), TR20-183}
}

@inproceedings{IlangoLoffOliveira2020,
  author    = {Ilango, Rahul and Loff, Bruno and Oliveira, Igor Carboni},
  title     = {{NP}-Hardness of Circuit Minimization for Multi-Output Functions},
  booktitle = {35th Computational Complexity Conference (CCC 2020)},
  series    = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume    = {169},
  pages     = {22:1--22:36},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  year      = {2020},
  doi       = {10.4230/LIPIcs.CCC.2020.22}
}

@article{Immerman1988,
  author  = {Immerman, Neil},
  title   = {Nondeterministic Space Is Closed under Complementation},
  journal = {SIAM Journal on Computing},
  volume  = {17},
  number  = {5},
  pages   = {935--938},
  year    = {1988},
  doi     = {10.1137/0217058},
  url     = {https://people.cs.umass.edu/~immerman/pub/space.pdf}
}

@book{Immerman1999,
  author    = {Immerman, Neil},
  title     = {Descriptive Complexity},
  series    = {Graduate Texts in Computer Science},
  publisher = {Springer},
  year      = {1999},
  doi       = {10.1007/978-1-4612-0539-5}
}

@article{ImmermanLandau1995,
  author  = {Immerman, Neil and Landau, Susan},
  title   = {The Complexity of Iterated Multiplication},
  journal = {Information and Computation},
  volume  = {116},
  number  = {1},
  pages   = {103--116},
  year    = {1995},
  url     = {https://people.cs.umass.edu/~immerman/pub/mult.pdf}
}

@inproceedings{Impagliazzo1995,
  author    = {Impagliazzo, Russell},
  title     = {Hard-Core Distributions for Somewhat Hard Problems},
  booktitle = {Proceedings of the 36th Annual Symposium on Foundations of Computer Science},
  series    = {FOCS 1995},
  pages     = {538--545},
  year      = {1995},
  doi       = {10.1109/SFCS.1995.492584}
}

@article{ImpagliazzoPaturi2001,
  author    = {Impagliazzo, Russell and Paturi, Ramamohan},
  title     = {On the Complexity of {$k$-SAT}},
  journal   = {Journal of Computer and System Sciences},
  volume    = {62},
  number    = {2},
  pages     = {367--375},
  year      = {2001},
  doi       = {10.1006/jcss.2000.1727}
}

@article{ImpagliazzoPaturiZane2001,
  author    = {Impagliazzo, Russell and Paturi, Ramamohan and Zane, Francis},
  title     = {Which Problems Have Strongly Exponential Complexity?},
  journal   = {Journal of Computer and System Sciences},
  volume    = {63},
  number    = {4},
  pages     = {512--530},
  year      = {2001},
  doi       = {10.1006/jcss.2001.1774}
}

@inproceedings{ImpagliazzoWigderson1997,
  author    = {Impagliazzo, Russell and Wigderson, Avi},
  title     = {{P} = {BPP} if {E} Requires Exponential Circuits: Derandomizing the {XOR} Lemma},
  booktitle = {Proceedings of the 29th Annual ACM Symposium on Theory of Computing},
  series    = {STOC 1997},
  pages     = {220--229},
  year      = {1997},
  doi       = {10.1145/258533.258590}
}

@article{Johnson1962,
  author    = {Johnson, Selmer M.},
  title     = {A New Upper Bound for Error-Correcting Codes},
  journal   = {IRE Transactions on Information Theory},
  volume    = {8},
  number    = {3},
  pages     = {203--207},
  year      = {1962},
  doi       = {10.1109/TIT.1962.1057714}
}

@article{JohnsonPapadimitriouYannakakis1988,
  author = {Johnson, David S. and Papadimitriou, Christos H. and Yannakakis, Mihalis},
  title = {How Easy Is Local Search?},
  journal = {Journal of Computer and System Sciences},
  volume = {37},
  number = {1},
  pages = {79--100},
  year = {1988},
  doi = {10.1016/0022-0000(88)90046-3},
  url = {https://doi.org/10.1016/0022-0000(88)90046-3}
}

@book{Jukna2011,
  author    = {Jukna, Stasys},
  title     = {Extremal Combinatorics: With Applications in Computer Science},
  edition   = {2},
  series    = {Texts in Theoretical Computer Science. An EATCS Series},
  publisher = {Springer},
  year      = {2011},
  doi       = {10.1007/978-3-642-17364-6}
}

@book{Jukna2012,
  author    = {Stasys Jukna},
  title     = {Boolean Function Complexity: Advances and Frontiers},
  series    = {Algorithms and Combinatorics},
  volume    = {27},
  publisher = {Springer},
  year      = {2012},
  doi       = {10.1007/978-3-642-24508-4},
  url       = {https://web.vu.lt/mif/s.jukna/boolean/index.html}
}

@article{Justesen1972,
  author    = {Justesen, J{\o}rn},
  title     = {Class of Constructive Asymptotically Good Algebraic Codes},
  journal   = {IEEE Transactions on Information Theory},
  volume    = {18},
  number    = {5},
  pages     = {652--656},
  year      = {1972},
  doi       = {10.1109/TIT.1972.1054893}
}

@inproceedings{KabanetsCai2000,
  author    = {Kabanets, Valentine and Cai, Jin-Yi},
  title     = {Circuit Minimization Problem},
  booktitle = {Proceedings of the Thirty-Second Annual {ACM} Symposium on Theory of Computing (STOC 2000)},
  pages     = {73--79},
  year      = {2000},
  doi       = {10.1145/335305.335314}
}

@article{Kadin1988,
  author = {Kadin, Jim},
  title = {The Polynomial Time Hierarchy Collapses if the {Boolean} Hierarchy Collapses},
  journal = {SIAM Journal on Computing},
  volume = {17},
  number = {6},
  pages = {1263--1282},
  year = {1988},
  doi = {10.1137/0217080}
}

@article{Kahale1995,
  author = {Kahale, Nabil},
  title = {Eigenvalues and Expansion of Regular Graphs},
  journal = {Journal of the ACM},
  volume = {42},
  number = {5},
  pages = {1091--1106},
  year = {1995},
  doi = {10.1145/210118.210136},
  url = {https://doi.org/10.1145/210118.210136}
}

@inproceedings{KahnKalaiLinial1988,
  author    = {Kahn, Jeff and Kalai, Gil and Linial, Nathan},
  title     = {The Influence of Variables on {Boolean} Functions},
  booktitle = {29th Annual Symposium on Foundations of Computer Science},
  publisher = {IEEE Computer Society},
  year      = {1988},
  pages     = {68--80},
  doi       = {10.1109/SFCS.1988.21923}
}

@article{KalyanasundaramSchnitger1992,
  author    = {Kalyanasundaram, Bala and Schnitger, Georg},
  title     = {The Probabilistic Communication Complexity of Set Intersection},
  journal   = {SIAM Journal on Discrete Mathematics},
  volume    = {5},
  number    = {4},
  pages     = {545--557},
  year      = {1992},
  doi       = {10.1137/0405044}
}

@article{Kannan1982,
  author    = {Kannan, Ravi},
  title     = {Circuit-Size Lower Bounds and Non-Reducibility to Sparse Sets},
  journal   = {Information and Control},
  volume    = {55},
  number    = {1--3},
  pages     = {40--56},
  year      = {1982},
  doi       = {10.1016/S0019-9958(82)90382-5}
}

@article{KarchmerWigderson1990,
  author    = {Karchmer, Mauricio and Wigderson, Avi},
  title     = {Monotone circuits for connectivity require super-logarithmic depth},
  journal   = {SIAM Journal on Discrete Mathematics},
  volume    = {3},
  number    = {2},
  pages     = {255--265},
  year      = {1990}
}

@incollection{Karp1972,
  author    = {Karp, Richard M.},
  title     = {Reducibility among Combinatorial Problems},
  booktitle = {Complexity of Computer Computations},
  editor    = {Miller, Raymond E. and Thatcher, James W.},
  publisher = {Plenum Press},
  year      = {1972},
  pages     = {85--103},
  doi       = {10.1007/978-1-4684-2001-2_9}
}

@inproceedings{KarpLipton1980,
  author    = {Karp, Richard M. and Lipton, Richard J.},
  title     = {Some Connections between Nonuniform and Uniform Complexity Classes},
  booktitle = {Proceedings of the 12th Annual ACM Symposium on Theory of Computing},
  series    = {STOC 1980},
  pages     = {302--309},
  year      = {1980},
  doi       = {10.1145/800141.804678}
}

@book{             KatzLindell2020,
  author       = {Jonathan Katz and
                  Yehuda Lindell},
  title        = {Introduction to Modern Cryptography},
  edition      = {3rd},
  publisher    = {CRC Press},
  year         = {2020},
  isbn         = {9780815354369}
}

@book{KearnsVazirani1994,
  author       = {Kearns, Michael J. and Vazirani, Umesh V.},
  title        = {An Introduction to Computational Learning Theory},
  year         = {1994},
  isbn         = {978-0-262-11193-5},
  publisher    = {MIT Press},
  address      = {Cambridge, MA, USA}
}

@inproceedings{Khot2002,
  author    = {Khot, Subhash},
  title     = {On the Power of Unique 2-Prover 1-Round Games},
  booktitle = {Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing},
  series    = {STOC '02},
  pages     = {767--775},
  publisher = {ACM},
  year      = {2002},
  doi       = {10.1145/509907.510017}
}

@article{Khrapchenko1971,
  author    = {Khrapchenko, V. M.},
  title     = {Complexity of the realization of a linear function in the class of $\Pi$-circuits},
  journal   = {Mathematical Notes of the Academy of Sciences of the USSR},
  volume    = {9},
  pages     = {21--23},
  year      = {1971},
  note      = {Russian original: Matematicheskie Zametki 9(1), 35--40}
}

@article{Khrapchenko1971b,
  author    = {Khrapchenko, V. M.},
  title     = {Method of determining lower bounds for the complexity of $\Pi$-schemes},
  journal   = {Mathematical Notes of the Academy of Sciences of the USSR},
  volume    = {10},
  pages     = {474--479},
  year      = {1971},
  doi       = {10.1007/BF01747074},
  note      = {Russian original: Matematicheskie Zametki 10(1), 83--92}
}

@inproceedings{   Kiselyov2015,
  author    = {Kiselyov, Oleg and Ishii, Hiromi},
  title     = {Freer Monads, More Extensible Effects},
  booktitle = {Proceedings of the 2015 ACM SIGPLAN Symposium on Haskell},
  series    = {Haskell 2015},
  year      = {2015},
  pages     = {94--105},
  publisher = {ACM},
  address   = {New York, NY, USA},
  url       = {https://doi.org/10.1145/2804302.2804319},
  doi       = {10.1145/2804302.2804319},
  isbn      = {978-1-4503-3808-0}
}

@article{Ko1986,
  author  = {Ko, Ker-I},
  title   = {On the Notion of Infinite Pseudorandom Sequences},
  journal = {Theoretical Computer Science},
  volume  = {48},
  pages   = {9--33},
  year    = {1986},
  doi     = {10.1016/0304-3975(86)90081-2}
}

@article{Ko1991,
  author  = {Ko, Ker-I},
  title   = {On the Complexity of Learning Minimum Time-Bounded {Turing} Machines},
  journal = {SIAM Journal on Computing},
  volume  = {20},
  number  = {5},
  pages   = {962--986},
  year    = {1991},
  doi     = {10.1137/0220059}
}

@article{KoeblerSchoeningTodaToran1992,
  author  = {K{\"o}bler, Johannes and Sch{\"o}ning, Uwe and Toda, Seinosuke and
             Tor{\'a}n, Jacobo},
  title   = {Turing Machines with Few Accepting Computations and Low Sets for {PP}},
  journal = {Journal of Computer and System Sciences},
  volume  = {44},
  number  = {2},
  pages   = {272--286},
  year    = {1992},
  doi     = {10.1016/0022-0000(92)90022-B}
}

@techreport{Korten2026,
  author      = {Korten, Oliver},
  title       = {Top-Down Lower Bounds for All Depths},
  institution = {Electronic Colloquium on Computational Complexity},
  number      = {TR26-221},
  year        = {2026}
}

@article{KushilevitzMansour1993,
  author    = {Kushilevitz, Eyal and Mansour, Yishay},
  title     = {Learning Decision Trees Using the {F}ourier Spectrum},
  journal   = {SIAM Journal on Computing},
  volume    = {22},
  number    = {6},
  pages     = {1331--1348},
  year      = {1993},
  doi       = {10.1137/0222080}
}

@book{KushilevitzNisan1997,
  author    = {Kushilevitz, Eyal and Nisan, Noam},
  title     = {Communication Complexity},
  publisher = {Cambridge University Press},
  year      = {1997}
}

@article{Ladner1975,
  author    = {Ladner, Richard E.},
  title     = {The Circuit Value Problem Is Log Space Complete for {$P$}},
  journal   = {ACM SIGACT News},
  volume    = {7},
  number    = {1},
  pages     = {18--20},
  year      = {1975},
  doi       = {10.1145/990518.990519}
}

@article{LadnerFischer1980,
  author = {Ladner, Richard E. and Fischer, Michael J.},
  title = {Parallel Prefix Computation},
  journal = {Journal of the ACM},
  volume = {27},
  number = {4},
  pages = {831--838},
  year = {1980},
  doi = {10.1145/322217.322232},
  url = {https://doi.org/10.1145/322217.322232}
}

@article{LadnerLynchSelman1975,
  author    = {Ladner, Richard E. and Lynch, Nancy A. and Selman, Alan L.},
  title     = {A comparison of polynomial time reducibilities},
  journal   = {Theoretical Computer Science},
  volume    = {1},
  number    = {2},
  pages     = {103--123},
  year      = {1975}
}

@techreport{Lamport1979,
  author      = {Lamport, Leslie},
  title       = {Constructing Digital Signatures from a One-Way Function},
  institution = {SRI International},
  number      = {CSL-98},
  year        = {1979},
  month       = oct,
  url         = {https://www.microsoft.com/en-us/research/publication/constructing-digital-signatures-one-way-function/}
}

@misc{LandsbergTeitler2009,
  author = {Landsberg, J. M. and Teitler, Zach},
  title = {On the ranks and border ranks of symmetric tensors},
  year = {2009},
  eprint = {0901.0487},
  archivePrefix = {arXiv},
  primaryClass = {math.AG},
  note = {Equation (1) and Remark 6.5; version 3},
  url = {https://arxiv.org/abs/0901.0487v3}
}

@article{Lautemann1983,
  author    = {Lautemann, Clemens},
  title     = {{BPP} and the Polynomial Hierarchy},
  journal   = {Information Processing Letters},
  volume    = {17},
  number    = {4},
  pages     = {215--217},
  year      = {1983},
  doi       = {10.1016/0020-0190(83)90044-3}
}

@misc{LeanCanny2026,
  author = {{lean-canny contributors}},
  title = {lean-canny},
  year = {2026},
  url = {https://github.com/SamuelSchlesinger/lean-canny/tree/2a50a2ee00ae0699cc3f0c2bff5100c4687d2d8e},
  note = {Source revision 2a50a2ee00ae0699cc3f0c2bff5100c4687d2d8e}
}

@misc{LecomteRamakrishnan2026,
  author        = {Lecomte, Victor and Ramakrishnan, Prasanna},
  title         = {Optimal Shallow Circuits for Majority},
  year          = {2026},
  eprint        = {2609.34029},
  archivePrefix = {arXiv}
}

@article{Levin1973,
  author  = {Levin, Leonid A.},
  title   = {Universal Sequential Search Problems},
  journal = {Problems of Information Transmission},
  volume  = {9},
  number  = {3},
  pages   = {265--266},
  year    = {1973}
}

@article{Levin1984,
  author  = {Levin, Leonid A.},
  title   = {Randomness Conservation Inequalities; Information and Independence in Mathematical Theories},
  journal = {Information and Control},
  volume  = {61},
  number  = {1},
  pages   = {15--37},
  year    = {1984},
  doi     = {10.1016/S0019-9958(84)80060-1}
}

@article{LewisPapadimitriou1982,
  author    = {Lewis, Harry R. and Papadimitriou, Christos H.},
  title     = {Symmetric Space-Bounded Computation},
  journal   = {Theoretical Computer Science},
  volume    = {19},
  number    = {2},
  pages     = {161--187},
  year      = {1982},
  doi       = {10.1016/0304-3975(82)90058-5}
}

@inproceedings{Li2023,
  author    = {Li, Xin},
  title     = {Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More},
  booktitle = {Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science},
  series    = {FOCS 2023},
  pages     = {1271--1281},
  year      = {2023},
  doi       = {10.1109/FOCS57990.2023.00075}
}

@article{Lichtenstein1982,
  author  = {Lichtenstein, David},
  title   = {Planar Formulae and Their Uses},
  journal = {SIAM Journal on Computing},
  volume  = {11},
  number  = {2},
  pages   = {329--343},
  year    = {1982},
  doi     = {10.1137/0211025}
}

@article{LichtensteinSipser1980,
  author    = {Lichtenstein, David and Sipser, Michael},
  title     = {{GO} Is Polynomial-Space Hard},
  journal   = {Journal of the ACM},
  volume    = {27},
  number    = {2},
  pages     = {393--401},
  year      = {1980},
  doi       = {10.1145/322186.322201}
}

@book{LidlNiederreiter1997,
  author    = {Lidl, Rudolf and Niederreiter, Harald},
  title     = {Finite Fields},
  edition   = {2},
  series    = {Encyclopedia of Mathematics and its Applications},
  volume    = {20},
  publisher = {Cambridge University Press},
  year      = {1997},
  doi       = {10.1017/CBO9780511525926}
}

@article{LinialMansourNisan1993,
  author    = {Linial, Nathan and Mansour, Yishay and Nisan, Noam},
  title     = {Constant Depth Circuits, {F}ourier Transform, and Learnability},
  journal   = {Journal of the ACM},
  volume    = {40},
  number    = {3},
  pages     = {607--620},
  year      = {1993},
  doi       = {10.1145/174130.174138}
}

@inproceedings{LiptonYoung1994,
  author    = {Lipton, Richard J. and Young, Neal E.},
  title     = {Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory},
  booktitle = {Proceedings of the Twenty-Sixth Annual {ACM} Symposium on Theory of Computing (STOC 1994)},
  pages     = {734--740},
  year      = {1994},
  doi       = {10.1145/195058.195447}
}

@inproceedings{LiuPass2020,
  author    = {Liu, Yanyi and Pass, Rafael},
  title     = {On One-way Functions and {Kolmogorov} Complexity},
  booktitle = {2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)},
  pages     = {1243--1254},
  publisher = {IEEE},
  year      = {2020},
  doi       = {10.1109/FOCS46700.2020.00118},
  url       = {https://arxiv.org/abs/2009.11514v1},
  note      = {Full version on arXiv:2009.11514v1 (and ECCC TR20-052); section, theorem, definition, and lemma numbers follow arXiv:2009.11514v1}
}

@inproceedings{LiuPass2021Crypto,
  author    = {Liu, Yanyi and Pass, Rafael},
  title     = {On the Possibility of Basing Cryptography on {$\mathsf{EXP} \neq \mathsf{BPP}$}},
  booktitle = {Advances in Cryptology -- CRYPTO 2021},
  series    = {Lecture Notes in Computer Science},
  volume    = {12825},
  pages     = {11--40},
  publisher = {Springer},
  year      = {2021},
  doi       = {10.1007/978-3-030-84242-0_2},
  note      = {Full version in Electronic Colloquium on Computational Complexity (ECCC), TR21-056; section, fact, and page numbers follow ECCC TR21-056}
}

@book{LiVitanyi2019,
  author    = {Li, Ming and Vit{\'a}nyi, Paul},
  title     = {An Introduction to {K}olmogorov Complexity and Its Applications},
  edition   = {4th},
  series    = {Texts in Computer Science},
  publisher = {Springer},
  address   = {Cham},
  year      = {2019},
  doi       = {10.1007/978-3-030-11298-1}
}

@inproceedings{LiYang2022,
  author    = {Li, Jiatu and Yang, Tianqi},
  title     = {{$3.1n - o(n)$} Circuit Lower Bounds for Explicit Functions},
  booktitle = {Proceedings of the 54th Annual ACM Symposium on Theory of Computing},
  series    = {STOC 2022},
  pages     = {1180--1193},
  year      = {2022},
  doi       = {10.1145/3519935.3519976}
}

@article{LokshtanovMarxSaurabh2011,
  author  = {Lokshtanov, Daniel and Marx, D{\'a}niel and Saurabh, Saket},
  title   = {Lower bounds based on the {Exponential Time Hypothesis}},
  journal = {Bulletin of the EATCS},
  volume  = {105},
  pages   = {41--72},
  year    = {2011}
}

@article{LokshtanovMarxSaurabh2018,
  author    = {Lokshtanov, Daniel and Marx, D{\'a}niel and Saurabh, Saket},
  title     = {Slightly Superexponential Parameterized Problems},
  journal   = {SIAM Journal on Computing},
  volume    = {47},
  number    = {3},
  pages     = {675--702},
  year      = {2018},
  doi       = {10.1137/16M1104834}
}

@article{LoomisWhitney1949,
  author    = {Loomis, Lynn H. and Whitney, Hassler},
  title     = {An Inequality Related to the Isoperimetric Inequality},
  journal   = {Bulletin of the American Mathematical Society},
  volume    = {55},
  number    = {10},
  pages     = {961--962},
  year      = {1949},
  doi       = {10.1090/S0002-9904-1949-09320-5}
}

@inproceedings{LovaszSaks1988,
  author    = {Lov{\'a}sz, L{\'a}szl{\'o} and Saks, Michael},
  title     = {Lattices, {M{\"o}bius} Functions and Communication Complexity},
  booktitle = {Proceedings of the 29th Annual Symposium on Foundations of Computer Science},
  series    = {FOCS 1988},
  pages     = {81--90},
  year      = {1988},
  doi       = {10.1109/SFCS.1988.21924}
}

@article{LubyRackoff1988,
  author       = {Michael Luby and Charles Rackoff},
  title        = {How to Construct Pseudorandom Permutations from Pseudorandom Functions},
  journal      = {SIAM Journal on Computing},
  volume       = {17},
  number       = {2},
  pages        = {373--386},
  year         = {1988},
  doi          = {10.1137/0217022}
}

@article{LundFortnowKarloffNisan1992,
  author  = {Lund, Carsten and Fortnow, Lance and Karloff, Howard and Nisan, Noam},
  title   = {Algebraic Methods for Interactive Proof Systems},
  journal = {Journal of the ACM},
  volume  = {39},
  number  = {4},
  pages   = {859--868},
  year    = {1992},
  doi     = {10.1145/146585.146605}
}

@article{Lupanov1958,
  author  = {Oleg B. Lupanov},
  title   = {On a Method of Circuit Synthesis},
  journal = {Izvestiya Vysshikh Uchebnykh Zavedenii. Radiofizika},
  volume  = {1},
  number  = {1},
  pages   = {120--140},
  year    = {1958},
  note    = {In Russian},
  url     = {https://radiophysics.unn.ru/sites/default/files/papers/1958_1_120.pdf}
}

@article{Lupanov1965,
  author  = {Lupanov, O. B.},
  title   = {On an Approach to the Synthesis of Control Systems: the Principle of Local Coding},
  journal = {Problemy Kibernetiki},
  volume  = {14},
  pages   = {31--110},
  year    = {1965},
  note    = {In Russian}
}

@inproceedings{Lyubashevsky2009,
  author    = {Lyubashevsky, Vadim},
  title     = {Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based
               Signatures},
  booktitle = {Advances in Cryptology -- ASIACRYPT 2009},
  series    = {Lecture Notes in Computer Science},
  volume    = {5912},
  pages     = {598--616},
  publisher = {Springer},
  year      = {2009},
  doi       = {10.1007/978-3-642-10366-7_35}
}

@inproceedings{Lyubashevsky2012,
  author    = {Lyubashevsky, Vadim},
  title     = {Lattice Signatures without Trapdoors},
  booktitle = {Advances in Cryptology -- EUROCRYPT 2012},
  series    = {Lecture Notes in Computer Science},
  volume    = {7237},
  pages     = {738--755},
  publisher = {Springer},
  year      = {2012},
  doi       = {10.1007/978-3-642-29011-4_43}
}

@book{MacWilliamsSloane1977,
  author    = {MacWilliams, F. J. and Sloane, N. J. A.},
  title     = {The Theory of Error-Correcting Codes},
  series    = {North-Holland Mathematical Library},
  volume    = {16},
  publisher = {North-Holland},
  year      = {1977}
}

@misc{         Malkin2024,
  author       = {Tal Malkin},
  title        = {{COMS W3261: Computer Science Theory, Handout 3: The Myhill-Nerode Theorem and Implications}},
  howpublished = {Columbia University Course Handout},
  year         = {2024},
  month        = {September},
  url          = {https://www.cs.columbia.edu/~tal/3261/fall24/Handouts/3_Myhill_Nerode.pdf}
}

@incollection{McDiarmid1989,
  author    = {McDiarmid, Colin},
  title     = {On the Method of Bounded Differences},
  booktitle = {Surveys in Combinatorics, 1989},
  editor    = {Siemons, J.},
  series    = {London Mathematical Society Lecture Note Series},
  volume    = {141},
  pages     = {148--188},
  publisher = {Cambridge University Press},
  year      = {1989},
  doi       = {10.1017/CBO9781107359949.008}
}

@inproceedings{McKayMurrayWilliams2019,
  author    = {McKay, Dylan and Murray, Cody D. and Williams, R. Ryan},
  title     = {Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes},
  booktitle = {Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019)},
  pages     = {1215--1225},
  publisher = {ACM},
  year      = {2019},
  doi       = {10.1145/3313276.3316396}
}

@article{MegiddoPapadimitriou1991,
  author = {Megiddo, Nimrod and Papadimitriou, Christos H.},
  title = {On Total Functions, Existence Theorems and Computational Complexity},
  journal = {Theoretical Computer Science},
  volume = {81},
  number = {2},
  pages = {317--324},
  year = {1991},
  doi = {10.1016/0304-3975(91)90200-L},
  url = {https://doi.org/10.1016/0304-3975(91)90200-L}
}

@inproceedings{MehlhornSchmidt1982,
  author    = {Mehlhorn, Kurt and Schmidt, Erik M.},
  title     = {{Las Vegas} Is Better than Determinism in {VLSI} and Distributed Computing},
  booktitle = {Proceedings of the 14th Annual ACM Symposium on Theory of Computing},
  series    = {STOC 1982},
  pages     = {330--337},
  year      = {1982},
  doi       = {10.1145/800070.802208}
}

@inproceedings{Merkle1989,
  author    = {Merkle, Ralph C.},
  title     = {A Certified Digital Signature},
  booktitle = {Advances in Cryptology -- CRYPTO '89},
  series    = {Lecture Notes in Computer Science},
  volume    = {435},
  pages     = {218--238},
  publisher = {Springer},
  year      = {1990},
  doi       = {10.1007/0-387-34805-0_21}
}

@techreport{MertzPitassi2020,
  author      = {Mertz, Ian and Pitassi, Toniann},
  title       = {Lifting: As Easy As 1, 2, 3},
  institution = {Electronic Colloquium on Computational Complexity},
  number      = {TR20-111},
  year        = {2020},
  url         = {https://eccc.weizmann.ac.il/report/2020/111/}
}

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

@book{            MilewskiDao,
  author    = {Milewski, Bartosz},
  title     = {The Dao of Functional Programming},
  publisher = {Self-published},
  year      = {2018},
  note      = {Available online at \url{https://bartoszmilewski.com}},
}

@book{            Milner80,
  author       = {Robin Milner},
  title        = {A Calculus of Communicating Systems},
  series       = {Lecture Notes in Computer Science},
  volume       = {92},
  publisher    = {Springer},
  year         = {1980},
  url          = {https://doi.org/10.1007/3-540-10235-3},
  doi          = {10.1007/3-540-10235-3},
  isbn         = {3-540-10235-3},
  timestamp    = {Tue, 14 May 2019 10:00:35 +0200},
  biburl       = {https://dblp.org/rec/books/sp/Milner80.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@book{MinskyPapert1969,
  author    = {Minsky, Marvin and Papert, Seymour},
  title     = {Perceptrons: An Introduction to Computational Geometry},
  publisher = {MIT Press},
  year      = {1969}
}

@techreport{MishraSanthanam2026,
  author      = {Mishra, Om Swostik and Santhanam, Rahul},
  title       = {An Explicit {$3.5n - o(n)$} Size Lower Bound against General {Boolean} Circuits},
  institution = {Electronic Colloquium on Computational Complexity},
  number      = {TR26-260},
  year        = {2026},
  url         = {https://eccc.weizmann.ac.il/report/2026/260/}
}

@inproceedings{Mitchell1977,
  author       = {Mitchell, Tom M.},
  title        = {Version Spaces: A Candidate Elimination Approach to Rule Learning},
  booktitle    = {Proceedings of the 5th International Joint Conference on Artificial Intelligence},
  volume       = {1},
  pages        = {305--310},
  year         = {1977}
}

@article{Mitchell1982,
  author       = {Mitchell, Tom M.},
  title        = {Generalization as Search},
  journal      = {Artificial Intelligence},
  volume       = {18},
  number       = {2},
  pages        = {203--226},
  year         = {1982},
  doi          = {10.1016/0004-3702(82)90040-6}
}

@book{Mitchell1997,
  author       = {Mitchell, Tom M.},
  title        = {Machine Learning},
  year         = {1997},
  publisher    = {McGraw-Hill},
  isbn         = {0070428077}
}

@book{MitzenmacherUpfal2017,
  author    = {Mitzenmacher, Michael and Upfal, Eli},
  title     = {Probability and Computing: Randomization and Probabilistic Techniques in
               Algorithms and Data Analysis},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2017}
}

@Book{            Montesi2023,
  title         = {Introduction to {Choreographies}},
  author        = {Montesi, Fabrizio},
  year          = {2023},
  publisher     = {Cambridge University Press},
  address       = {Cambridge},
  url           = {https://www.cambridge.org/core/books/introduction-to-choreographies/65D3DA3CFF11AB835452CBC97FAE4830},
  urldate       = {2023-02-02},
  doi           = {10.1017/9781108981491},
  abstract      = {In concurrent and distributed systems, processes can
                  complete tasks together by playing their parts in a joint
                  plan. The plan, or protocol, can be written as a
                  choreography: a formal description of overall behaviour
                  that processes should collaborate to implement, like
                  authenticating a user or purchasing an item online.
                  Formality brings clarity, but not only that: choreographies
                  can contribute to important safety and liveness properties.
                  This book is an ideal introduction to theory of
                  choreographies for students, researchers, and professionals
                  in computer science and applied mathematics. It covers
                  languages for writing choreographies, their semantics, and
                  principles for implementing choreographies correctly. The
                  text treats the study of choreographies as a discipline in
                  its own right, following a systematic approach that starts
                  from simple foundations and proceeds to more advanced
                  features in incremental steps. Each chapter includes
                  examples and exercises aimed at helping with understanding
                  the theory and its relation to practice.},
  isbn          = {978-1-108-83376-9},
  keywords      = {choreographic-programming,choreographic-language,choreography,concurrency-theory}
}

@article{MorenoRivera2016,
  author = {Moreno, Rutilo and Rivera, Luis Manuel},
  title = {Blocks in Cycles and {$k$}-Commuting Permutations},
  journal = {SpringerPlus},
  volume = {5},
  pages = {1949},
  year = {2016},
  doi = {10.1186/s40064-016-3638-7},
  url = {https://doi.org/10.1186/s40064-016-3638-7},
  note = {Article 1949}
}

@article{MoserTardos2010,
  author    = {Moser, Robin A. and Tardos, G{\'a}bor},
  title     = {A Constructive Proof of the General {Lov{\'a}sz} Local Lemma},
  journal   = {Journal of the ACM},
  volume    = {57},
  number    = {2},
  pages     = {11:1--11:15},
  year      = {2010},
  doi       = {10.1145/1667053.1667060}
}

@article{Muller1954,
  author    = {Muller, David E.},
  title     = {Application of {Boolean} Algebra to Switching Circuit Design and to Error Detection},
  journal   = {Transactions of the I.R.E. Professional Group on Electronic Computers},
  volume    = {EC-3},
  number    = {3},
  pages     = {6--12},
  year      = {1954},
  doi       = {10.1109/IREPGELC.1954.6499441}
}

@article{MulmuleyVaziraniVazirani1987,
  author    = {Mulmuley, Ketan and Vazirani, Umesh V. and Vazirani, Vijay V.},
  title     = {Matching Is as Easy as Matrix Inversion},
  journal   = {Combinatorica},
  volume    = {7},
  number    = {1},
  pages     = {105--113},
  year      = {1987},
  doi       = {10.1007/BF02579206}
}

@article{MurrayWilliams2017,
  author    = {Murray, Cody D. and Williams, R. Ryan},
  title     = {On the (Non) {NP}-Hardness of Computing Circuit Complexity},
  journal   = {Theory of Computing},
  volume    = {13},
  number    = {4},
  pages     = {1--22},
  year      = {2017},
  doi       = {10.4086/toc.2017.v013a004}
}

@article{Naor1991,
  author  = {Naor, Moni},
  title   = {Bit Commitment Using Pseudorandomness},
  journal = {Journal of Cryptology},
  volume  = {4},
  number  = {2},
  pages   = {151--158},
  year    = {1991},
  doi     = {10.1007/BF00196774},
  url     = {https://doi.org/10.1007/BF00196774}
}

@article{NaorNaor1993,
  author    = {Naor, Joseph and Naor, Moni},
  title     = {Small-Bias Probability Spaces: Efficient Constructions and Applications},
  journal   = {SIAM Journal on Computing},
  volume    = {22},
  number    = {4},
  pages     = {838--856},
  year      = {1993},
  doi       = {10.1137/0222053}
}

@article{NaorReingold2004,
  author    = {Naor, Moni and Reingold, Omer},
  title     = {Number-Theoretic Constructions of Efficient Pseudo-Random Functions},
  journal   = {Journal of the ACM},
  volume    = {51},
  number    = {2},
  pages     = {231--262},
  year      = {2004},
  doi       = {10.1145/972639.972643}
}

@article{Nechiporuk1965,
  author  = {Nechiporuk, E. I.},
  title   = {On the Complexity of Gating Circuits Realizing {B}oolean Matrices with Undefined
             Elements},
  journal = {Doklady Akademii Nauk SSSR},
  volume  = {163},
  number  = {1},
  pages   = {40--42},
  year    = {1965},
  note    = {In Russian}
}

@article{Nechiporuk1966,
  author    = {Nechiporuk, E. I.},
  title     = {On a {B}oolean function},
  journal   = {Soviet Mathematics Doklady},
  volume    = {7},
  number    = {4},
  pages     = {999--1000},
  year      = {1966}
}

@article{Newman1964,
  author    = {Newman, Donald J.},
  title     = {Rational Approximation to $|x|$},
  journal   = {Michigan Mathematical Journal},
  volume    = {11},
  number    = {1},
  pages     = {11--14},
  year      = {1964},
  doi       = {10.1307/mmj/1028999029}
}

@article{Newman1991,
  author    = {Newman, Ilan},
  title     = {Private vs. Common Random Bits in Communication Complexity},
  journal   = {Information Processing Letters},
  volume    = {39},
  number    = {2},
  pages     = {67--71},
  year      = {1991},
  doi       = {10.1016/0020-0190(91)90157-D}
}

@article{         Nipkow2001,
  title        = {More {Church-Rosser} Proofs (in {Isabelle/HOL})},
  author       = {Nipkow, Tobias},
  journal      = {Journal of Automated Reasoning},
  volume       = {26},
  pages        = {51--66},
  year         = {2001},
  publisher    = {Kluwer Academic Publishers}
}

@article{Nisan1991,
  author    = {Nisan, Noam},
  title     = {{CREW} {PRAM}s and decision trees},
  journal   = {SIAM Journal on Computing},
  volume    = {20},
  number    = {6},
  pages     = {999--1007},
  year      = {1991}
}

@article{NisanSzegedy1994,
  author    = {Nisan, Noam and Szegedy, Mario},
  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{NisanWigderson1994,
  author    = {Nisan, Noam and Wigderson, Avi},
  title     = {Hardness vs Randomness},
  journal   = {Journal of Computer and System Sciences},
  volume    = {49},
  number    = {2},
  pages     = {149--167},
  year      = {1994},
  doi       = {10.1016/S0022-0000(05)80043-1}
}

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

@techreport{NISTFIPS203,
  author      = {{National Institute of Standards and Technology}},
  title       = {Module-Lattice-Based Key-Encapsulation Mechanism Standard},
  institution = {National Institute of Standards and Technology},
  type        = {Federal Information Processing Standards Publication},
  number      = {203},
  year        = {2024},
  doi         = {10.6028/NIST.FIPS.203},
  url         = {https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.pdf}
}

@book{ODonnell2014,
  author    = {O'Donnell, Ryan},
  title     = {Analysis of {B}oolean Functions},
  publisher = {Cambridge University Press},
  year      = {2014},
  doi       = {10.1017/CBO9781139814782}
}

@misc{Oliveira2018Approximation,
  author    = {Oliveira, Igor Carboni},
  title     = {Notes on the Method of Approximations and the Emergence of the Fusion Method},
  year      = {2018},
  month     = aug,
  note      = {Expository notes dated August 31, 2018},
  url       = {https://www.dcs.warwick.ac.uk/~igorcarb/documents/papers/approximation-method-fusion-note.pdf}
}

@inproceedings{OliveiraPichSanthanam2019,
  author    = {Oliveira, Igor Carboni and Pich, J{\'a}n and Santhanam, Rahul},
  title     = {Hardness Magnification near State-Of-The-Art Lower Bounds},
  booktitle = {34th Computational Complexity Conference (CCC 2019)},
  series    = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume    = {137},
  pages     = {27:1--27:29},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  year      = {2019},
  doi       = {10.4230/LIPIcs.CCC.2019.27}
}

@inproceedings{OliveiraSanthanam2018,
  author    = {Igor Carboni Oliveira and Rahul Santhanam},
  title     = {Hardness Magnification for Natural Problems},
  booktitle = {59th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2018)},
  pages     = {65--76},
  year      = {2018},
  doi       = {10.1109/FOCS.2018.00016},
  note      = {Full version: ECCC TR18-139}
}

@misc{OpenAI2026ETH,
  author       = {{OpenAI}},
  title        = {The Exponential Time Hypothesis is False},
  year         = {2026},
  howpublished = {Manuscript},
  note         = {Dated 17 October 2026, revised 25 October 2026; source revision 7ef5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a},
  url          = {https://github.com/openai/math/blob/7ef5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf}
}

@misc{OpenAI2026RationalHitting,
  author = {{OpenAI}},
  title = {{Rational} matrix hitting lists for noncommutative rational formulas},
  year = {2026},
  note = {Lean formalization, revision adc7f1241b42e322a6451854ab7e4b4c146bf78a},
  url = {https://github.com/openai/math/tree/adc7f1241b42e322a6451854ab7e4b4c146bf78a/lean/OAI/Computability/RationalHitting}
}

@misc{OpenAI2026Sensitivity,
  author = {{OpenAI}},
  title = {{Sensitivity} versus block sensitivity: a superquadratic separation},
  year = {2026},
  note = {Lean formalization, revision adc7f1241b42e322a6451854ab7e4b4c146bf78a},
  url = {https://github.com/openai/math/tree/adc7f1241b42e322a6451854ab7e4b4c146bf78a/lean/OAI/Combinatorics/Sensitivity}
}

@article{Ore1933,
  author  = {Ore, Oystein},
  title   = {On a Special Class of Polynomials},
  journal = {Transactions of the American Mathematical Society},
  volume  = {35},
  number  = {3},
  pages   = {559--584},
  year    = {1933},
  doi     = {10.1090/S0002-9947-1933-1501703-0}
}

@article{Oum2005,
  author    = {Oum, Sang-il},
  title     = {Rank-width and Vertex-minors},
  journal   = {Journal of Combinatorial Theory, Series B},
  volume    = {95},
  number    = {1},
  pages     = {79--100},
  year      = {2005},
  doi       = {10.1016/j.jctb.2005.03.003}
}

@article{Papadimitriou1994PPAD,
  author = {Papadimitriou, Christos H.},
  title = {On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence},
  journal = {Journal of Computer and System Sciences},
  volume = {48},
  number = {3},
  pages = {498--532},
  year = {1994},
  doi = {10.1016/S0022-0000(05)80063-7},
  url = {https://doi.org/10.1016/S0022-0000(05)80063-7}
}

@book{Papadimitriou94,
  title={Computational Complexity},
  author={Papadimitriou, Christos H.},
  year={1994},
  publisher={Addison-Wesley},
  address={Reading, Massachusetts}
}

@inproceedings{PapadimitriouZachos1983,
  author = {Papadimitriou, Christos H. and Zachos, Stathis K.},
  title = {Two Remarks on the Power of Counting},
  booktitle = {Theoretical Computer Science: 6th GI-Conference, Dortmund, January 5--7, 1983},
  editor = {Cremers, Armin B. and Kriegel, Hans-Peter},
  series = {Lecture Notes in Computer Science},
  volume = {145},
  pages = {269--275},
  publisher = {Springer-Verlag},
  year = {1982},
  note = {Proceedings published in December 1982 for the January 1983 conference},
  doi = {10.1007/BFb0009651},
  url = {https://doi.org/10.1007/BFb0009651}
}

@article{PaturiPudlakZane1999,
  author    = {Paturi, Ramamohan and Pudl{\'a}k, Pavel and Zane, Francis},
  title     = {Satisfiability Coding Lemma},
  journal   = {Chicago Journal of Theoretical Computer Science},
  volume    = {1999},
  number    = {11},
  year      = {1999}
}

@inproceedings{Pedersen1991,
  author    = {Pedersen, Torben Pryds},
  title     = {Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing},
  booktitle = {Advances in Cryptology --- {CRYPTO} '91},
  series    = {Lecture Notes in Computer Science},
  volume    = {576},
  pages     = {129--140},
  publisher = {Springer},
  year      = {1992},
  doi       = {10.1007/3-540-46766-1_9}
}

@book{            Pierce2002,
  author       = {Benjamin C. Pierce},
  title        = {Types and programming languages},
  publisher    = {{MIT} Press},
  year         = {2002},
  isbn         = {978-0-262-16209-8}
}

@inproceedings{PPZ1997,
  author    = {Paturi, Ramamohan and Pudl{\'a}k, Pavel and Zane, Francis},
  title     = {Satisfiability Coding Lemma},
  booktitle = {38th Annual Symposium on Foundations of Computer Science (FOCS)},
  pages     = {566--574},
  year      = {1997},
  doi       = {10.1109/SFCS.1997.646146}
}

@inproceedings{Radhakrishnan2006,
  author    = {Radhakrishnan, Jaikumar},
  title     = {Gap Amplification in {PCP}s Using Lazy Random Walks},
  booktitle = {Automata, Languages and Programming (ICALP 2006)},
  series    = {Lecture Notes in Computer Science},
  pages     = {96--107},
  year      = {2006},
  doi       = {10.1007/11786986_10}
}

@article{Raz1998,
  author  = {Raz, Ran},
  title   = {A Parallel Repetition Theorem},
  journal = {SIAM Journal on Computing},
  volume  = {27},
  number  = {3},
  pages   = {763--803},
  year    = {1998},
  doi     = {10.1137/S0097539795280895}
}

@article{Razborov1985,
  author    = {Razborov, Alexander A.},
  title     = {Lower Bounds on the Monotone Complexity of Some {B}oolean Functions},
  journal   = {Soviet Mathematics Doklady},
  volume    = {31},
  pages     = {354--357},
  year      = {1985},
  note      = {Russian original: Doklady Akademii Nauk SSSR 281(4), 798--801}
}

@article{Razborov1987,
  author    = {Razborov, Alexander A.},
  title     = {Lower Bounds on the Size of Bounded Depth Circuits over a Complete Basis with
               Logical Addition},
  journal   = {Mathematical Notes of the Academy of Sciences of the USSR},
  volume    = {41},
  number    = {4},
  pages     = {333--338},
  year      = {1987},
  doi       = {10.1007/BF01137685}
}

@inproceedings{Razborov1989,
  author    = {Razborov, Alexander A.},
  title     = {On the Method of Approximations},
  booktitle = {Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing},
  pages     = {167--176},
  year      = {1989}
}

@article{Razborov1992,
  author    = {Razborov, Alexander A.},
  title     = {On the Distributional Complexity of Disjointness},
  journal   = {Theoretical Computer Science},
  volume    = {106},
  number    = {2},
  pages     = {385--390},
  year      = {1992},
  doi       = {10.1016/0304-3975(92)90260-M}
}

@incollection{Razborov1995,
  author    = {Razborov, Alexander A.},
  title     = {Bounded Arithmetic and Lower Bounds in {B}oolean Complexity},
  booktitle = {Feasible Mathematics {II}},
  series    = {Progress in Computer Science and Applied Logic},
  volume    = {13},
  publisher = {Birkh{\"a}user},
  pages     = {344--386},
  year      = {1995},
  doi       = {10.1007/978-1-4612-2566-9_12}
}

@article{RazborovRudich1997,
  author    = {Razborov, Alexander A. and Rudich, Steven},
  title     = {Natural Proofs},
  journal   = {Journal of Computer and System Sciences},
  volume    = {55},
  number    = {1},
  pages     = {24--35},
  year      = {1997},
  doi       = {10.1006/jcss.1997.1494}
}

@article{RazMcKenzie1999,
  author    = {Raz, Ran and McKenzie, Pierre},
  title     = {Separation of the Monotone {NC} Hierarchy},
  journal   = {Combinatorica},
  volume    = {19},
  number    = {3},
  pages     = {403--435},
  year      = {1999},
  doi       = {10.1007/s004930050062}
}

@article{RazWigderson1992,
  author    = {Raz, Ran and Wigderson, Avi},
  title     = {Monotone Circuits for Matching Require Linear Depth},
  journal   = {Journal of the ACM},
  volume    = {39},
  number    = {3},
  pages     = {736--744},
  year      = {1992},
  doi       = {10.1145/146637.146684}
}

@article{Reed1954,
  author    = {Reed, Irving S.},
  title     = {A Class of Multiple-Error-Correcting Codes and the Decoding Scheme},
  journal   = {Transactions of the IRE Professional Group on Information Theory},
  volume    = {4},
  number    = {4},
  pages     = {38--49},
  year      = {1954},
  doi       = {10.1109/TIT.1954.1057465}
}

@article{ReedSolomon1960,
  author    = {Reed, Irving S. and Solomon, Gustave},
  title     = {Polynomial Codes Over Certain Finite Fields},
  journal   = {Journal of the Society for Industrial and Applied Mathematics},
  volume    = {8},
  number    = {2},
  pages     = {300--304},
  year      = {1960},
  doi       = {10.1137/0108018}
}

@article{Reingold2008,
  author    = {Reingold, Omer},
  title     = {Undirected Connectivity in Log-Space},
  journal   = {Journal of the ACM},
  volume    = {55},
  number    = {4},
  pages     = {17:1--17:24},
  year      = {2008},
  doi       = {10.1145/1391289.1391291}
}

@article{ReingoldVadhanWigderson2002,
  author    = {Reingold, Omer and Vadhan, Salil and Wigderson, Avi},
  title     = {Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders},
  journal   = {Annals of Mathematics},
  volume    = {155},
  number    = {1},
  pages     = {157--187},
  year      = {2002},
  doi       = {10.2307/3062153}
}

@inproceedings{Reynolds2002,
  author    = {Reynolds, John C.},
  title     = {Separation Logic: A Logic for Shared Mutable Data Structures},
  booktitle = {Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science},
  pages     = {55--74},
  year      = {2002},
  doi       = {10.1109/LICS.2002.1029817}
}

@article{Rice1953,
  author    = {Rice, Henry Gordon},
  title     = {Classes of Recursively Enumerable Sets and Their Decision Problems},
  journal   = {Transactions of the American Mathematical Society},
  volume    = {74},
  number    = {2},
  pages     = {358--366},
  year      = {1953},
  doi       = {10.1090/S0002-9947-1953-0053041-6}
}

@book{Rivlin1990,
  author    = {Rivlin, Theodore J.},
  title     = {Chebyshev Polynomials: From Approximation Theory to Algebra and Number Theory},
  edition   = {2},
  publisher = {Wiley},
  year      = {1990}
}

@article{Robinson1965,
  author    = {Robinson, J. A.},
  title     = {A Machine-Oriented Logic Based on the Resolution Principle},
  journal   = {Journal of the ACM},
  volume    = {12},
  number    = {1},
  pages     = {23--41},
  year      = {1965},
  doi       = {10.1145/321250.321253}
}

@inproceedings{Rompel1990,
  author    = {Rompel, John},
  title     = {One-Way Functions are Necessary and Sufficient for Secure Signatures},
  booktitle = {Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing},
  series    = {STOC '90},
  pages     = {387--394},
  publisher = {ACM},
  year      = {1990},
  doi       = {10.1145/100216.100269},
  url       = {https://doi.org/10.1145/100216.100269}
}

@article{Rubinstein1995,
  author    = {Rubinstein, David},
  title     = {Sensitivity vs. Block Sensitivity of {Boolean} Functions},
  journal   = {Combinatorica},
  volume    = {15},
  number    = {2},
  pages     = {297--299},
  year      = {1995},
  doi       = {10.1007/BF01200762}
}

@Book{            Sangiorgi2011,
  location      = {Cambridge},
  title         = {Introduction to Bisimulation and Coinduction},
  isbn          = {978-1-107-00363-7},
  url           = {https://www.cambridge.org/core/books/introduction-to-bisimulation-and-coinduction/8B54001CB763BAE9C4BA602C0A341D60},
  abstract      = {Induction is a pervasive tool in computer science and
                  mathematics for defining objects and reasoning on them.
                  Coinduction is the dual of induction and as such it brings
                  in quite different tools. Today, it is widely used in
                  computer science, but also in other fields, including
                  artificial intelligence, cognitive science, mathematics,
                  modal logics, philosophy and physics. The best known
                  instance of coinduction is bisimulation, mainly employed to
                  define and prove equalities among potentially infinite
                  objects: processes, streams, non-well-founded sets, etc.
                  This book presents bisimulation and coinduction: the
                  fundamental concepts and techniques and the duality with
                  induction. Each chapter contains exercises and selected
                  solutions, enabling students to connect theory with
                  practice. A special emphasis is placed on bisimulation as a
                  behavioural equivalence for processes. Thus the book serves
                  as an introduction to models for expressing processes (such
                  as process calculi) and to the associated techniques of
                  operational and algebraic analysis.},
  publisher     = {Cambridge University Press},
  author        = {Sangiorgi, Davide},
  urldate       = {2025-06-16},
  date          = {2011},
  doi           = {10.1017/CBO9780511777110}
}

@article{Schaefer1978,
  author    = {Schaefer, Thomas J.},
  title     = {On the Complexity of Some Two-Person Perfect-Information Games},
  journal   = {Journal of Computer and System Sciences},
  volume    = {16},
  number    = {2},
  pages     = {185--225},
  year      = {1978},
  doi       = {10.1016/0022-0000(78)90045-4}
}

@misc{Schlesinger2026Algebraic,
  author = {Schlesinger, Samuel},
  title = {{Algebraic} circuit formalizations in {Complexitylib}},
  year = {2026},
  note = {Source of ported Lean proofs, revision 2ad6cb481b70ee6e65e078dffb76b9856be199d3},
  url = {https://github.com/SamuelSchlesinger/complexitylib-v1/tree/2ad6cb481b70ee6e65e078dffb76b9856be199d3/Complexitylib/Algebraic}
}

@misc{Schlesinger2026IteratedFunctions,
  author = {Schlesinger, Samuel},
  title = {Square-root circuit bounds for iterated functions},
  year = {2026},
  note = {Source of ported Lean proofs, revision c4cfa198a241b3d2cc3bfa5f744a68a66f49be8b},
  url = {https://github.com/SamuelSchlesinger/iterating-functions/tree/c4cfa198a241b3d2cc3bfa5f744a68a66f49be8b/lean}
}

@misc{Schlesinger2026MassProduction,
  author = {Schlesinger, Samuel},
  title = {{Boolean} circuit mass production formalization},
  year = {2026},
  note = {Source of ported Lean proofs, revision 3998dc48823f7d2798aa814f2cbfbf3ceba146fa},
  url = {https://github.com/SamuelSchlesinger/algebraic-circuits/tree/3998dc48823f7d2798aa814f2cbfbf3ceba146fa/Algebraic}
}

@misc{Schlesinger2026Numerical,
  author = {Schlesinger, Samuel},
  title = {Canonical numerical predicates in {Complexitylib}},
  year = {2026},
  note = {Earlier canonical-expansion interfaces; revision e5ca965688f1b57f6df15482e895b66452955a40},
  url = {https://github.com/SamuelSchlesinger/complexitylib-v1/blob/e5ca965688f1b57f6df15482e895b66452955a40/Complexitylib/DescriptiveComplexity/Numerical.lean}
}

@misc{Schlesinger2026RationalHitting,
  author = {Schlesinger, Samuel},
  title = {{Rational} hitting lists in {Complexitylib}},
  year = {2026},
  note = {Source of ported Lean proofs, revision add0aca8ee0d71e68969f2cb45cf91554a50f787},
  url = {https://github.com/SamuelSchlesinger/complexitylib-v1/tree/add0aca8ee0d71e68969f2cb45cf91554a50f787/Complexitylib/RationalHitting}
}

@misc{Schlesinger2026Sensitivity,
  author = {Schlesinger, Samuel},
  title = {{Sensitivity} separation in {Complexitylib}},
  year = {2026},
  note = {Source of ported Lean proofs, revision add0aca8ee0d71e68969f2cb45cf91554a50f787},
  url = {https://github.com/SamuelSchlesinger/complexitylib-v1/tree/add0aca8ee0d71e68969f2cb45cf91554a50f787/Complexitylib/BooleanAnalysis/Sensitivity}
}

@article{Schnorr1974,
  author    = {Schnorr, Claus-Peter},
  title     = {Zwei lineare untere {S}chranken f{\"u}r die {K}omplexit{\"a}t {B}oolescher {F}unktionen},
  journal   = {Computing},
  volume    = {13},
  pages     = {155--171},
  year      = {1974}
}

@article{Schnorr1991,
  author    = {Schnorr, Claus-Peter},
  title     = {Efficient Signature Generation by Smart Cards},
  journal   = {Journal of Cryptology},
  volume    = {4},
  number    = {3},
  pages     = {161--174},
  year      = {1991},
  doi       = {10.1007/BF00196725}
}

@article{Schoening1989,
  author = {Sch{\"o}ning, Uwe},
  title = {Probabilistic Complexity Classes and Lowness},
  journal = {Journal of Computer and System Sciences},
  volume = {39},
  number = {1},
  pages = {84--100},
  year = {1989},
  doi = {10.1016/0022-0000(89)90020-2},
  url = {https://doi.org/10.1016/0022-0000(89)90020-2}
}

@inproceedings{Schoening1999,
  author    = {Sch{\"o}ning, Uwe},
  title     = {A Probabilistic Algorithm for k-{SAT} and Constraint Satisfaction Problems},
  booktitle = {40th Annual Symposium on Foundations of Computer Science (FOCS)},
  pages     = {410--414},
  year      = {1999},
  doi       = {10.1109/SFFCS.1999.814612}
}

@misc{SenellartGnatenko2026,
  author        = {Senellart, Pierre and Gnatenko, Anton},
  title         = {Descriptive Complexity in {Lean}: Completeness by First-Order Reductions},
  year          = {2026},
  eprint        = {2609.18261},
  archivePrefix = {arXiv},
  primaryClass  = {cs.LO},
  url           = {https://arxiv.org/abs/2609.18261},
  note          = {Companion repository:
                   \url{https://github.com/PierreSenellart/descriptive-complexity}}
}

@article{         Shamir1979,
  author       = {Adi Shamir},
  title        = {How to Share a Secret},
  journal      = {Communications of the ACM},
  volume       = {22},
  number       = {11},
  pages        = {612--613},
  year         = {1979},
  month        = nov,
  url          = {https://doi.org/10.1145/359168.359176},
  doi          = {10.1145/359168.359176}
}

@article{Shamir1992,
  author  = {Shamir, Adi},
  title   = {{IP} = {PSPACE}},
  journal = {Journal of the ACM},
  volume  = {39},
  number  = {4},
  pages   = {869--877},
  year    = {1992},
  doi     = {10.1145/146585.146609}
}

@article{Shannon1949,
  author  = {Claude E. Shannon},
  title   = {The Synthesis of Two-Terminal Switching Circuits},
  journal = {Bell System Technical Journal},
  volume  = {28},
  number  = {1},
  pages   = {59--98},
  year    = {1949},
  doi     = {10.1002/j.1538-7305.1949.tb03624.x},
  url     = {https://deeplearning.cs.cmu.edu/F24/document/readings/Shannon49.pdf}
}

@article{Shen1992,
  author  = {Shen, A.},
  title   = {{IP} = {SPACE}: Simplified Proof},
  journal = {Journal of the ACM},
  volume  = {39},
  number  = {4},
  pages   = {878--880},
  year    = {1992},
  doi     = {10.1145/146585.146613}
}

@article{         ShepherdsonSturgis1963,
  author       = {Shepherdson, J. C. and Sturgis, H. E.},
  title        = {Computability of Recursive Functions},
  journal      = {Journal of the ACM},
  volume       = {10},
  number       = {2},
  year         = {1963},
  pages        = {217--255},
  doi          = {10.1145/321160.321170},
  publisher    = {Association for Computing Machinery},
  address      = {New York, NY, USA}
}

@article{Sheppard1899,
  author  = {Sheppard, W. F.},
  title   = {On the Application of the Theory of Error to Cases of Normal Distribution and Normal
             Correlation},
  journal = {Philosophical Transactions of the Royal Society of London. Series A},
  volume  = {192},
  year    = {1899},
  pages   = {101--167},
  doi     = {10.1098/rsta.1899.0003}
}

@article{Shi2003,
  author        = {Shi, Yaoyun},
  title         = {Both {T}offoli and Controlled-{NOT} Need Little Help to Universal Quantum
                   Computing},
  journal       = {Quantum Information and Computation},
  volume        = {3},
  number        = {1},
  pages         = {84--92},
  year          = {2003},
  doi           = {10.26421/QIC3.1-7},
  eprint        = {quant-ph/0205115},
  archivePrefix = {arXiv},
  note          = {Title as published; arXiv v2 is titled ``Both {T}offoli and Controlled-{NOT}
                   need little help to do universal quantum computation''}
}

@article{Sholomov1969,
  author  = {Sholomov, L. A.},
  title   = {On the Realization of Incompletely Defined {B}oolean Functions by Circuits of
             Functional Elements},
  journal = {Problemy Kibernetiki},
  volume  = {21},
  pages   = {215--226},
  year    = {1969},
  note    = {In Russian}
}

@phdthesis{Simon1975,
  author = {Simon, Janos},
  title  = {On Some Central Problems in Computational Complexity},
  school = {Cornell University},
  year   = {1975}
}

@article{Singleton1964,
  author    = {Singleton, Richard C.},
  title     = {Maximum Distance $q$-Nary Codes},
  journal   = {IEEE Transactions on Information Theory},
  volume    = {10},
  number    = {2},
  pages     = {116--118},
  year      = {1964},
  doi       = {10.1109/TIT.1964.1053661}
}

@article{Sion1958,
  author    = {Sion, Maurice},
  title     = {On General Minimax Theorems},
  journal   = {Pacific Journal of Mathematics},
  volume    = {8},
  number    = {1},
  pages     = {171--176},
  year      = {1958},
  doi       = {10.2140/pjm.1958.8.171}
}

@inproceedings{Sipser1983,
  author    = {Sipser, Michael},
  title     = {A Complexity Theoretic Approach to Randomness},
  booktitle = {Proceedings of the 15th Annual ACM Symposium on Theory of Computing},
  pages     = {330--335},
  year      = {1983},
  doi       = {10.1145/800061.808762},
  url       = {https://doi.org/10.1145/800061.808762}
}

@book{Sipser2013,
  author    = {Sipser, Michael},
  title     = {Introduction to the Theory of Computation},
  edition   = {3rd},
  publisher = {Cengage Learning},
  year      = {2013}
}

@article{SkyumValiant1985,
  author    = {Skyum, Sven and Valiant, Leslie G.},
  title     = {A Complexity Theory Based on {B}oolean Algebra},
  journal   = {Journal of the ACM},
  volume    = {32},
  number    = {2},
  pages     = {484--502},
  year      = {1985},
  doi       = {10.1145/3149.3158}
}

@inproceedings{Smolensky1987,
  author    = {Smolensky, Roman},
  title     = {Algebraic Methods in the Theory of Lower Bounds for {B}oolean Circuit Complexity},
  booktitle = {Proceedings of the 19th Annual ACM Symposium on Theory of Computing},
  pages     = {77--82},
  year      = {1987},
  doi       = {10.1145/28395.28404}
}

@article{SpakowskiThakurTripathi2005,
  author    = {Spakowski, Holger and Thakur, Mayur and Tripathi, Rahul},
  title     = {Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties},
  journal   = {Information and Computation},
  volume    = {200},
  number    = {1},
  pages     = {1--34},
  year      = {2005},
  doi       = {10.1016/j.ic.2004.10.009},
  url       = {https://urresearch.rochester.edu/institutionalPublicationPublicView.action?institutionalItemVersionId=374},
  note      = {Author report TR 801, revised October 2004; Theorems 5.6(a) and 5.9}
}

@inproceedings{Spira1971,
  author    = {Spira, Philip M.},
  title     = {On Time-Hardware Complexity Tradeoffs for {B}oolean Functions},
  booktitle = {Proceedings of the Fourth Hawaii International Symposium on System Sciences},
  pages     = {525--527},
  year      = {1971}
}

@inproceedings{StearnsHartmanisLewis1965,
  author    = {Stearns, Richard E. and Hartmanis, Juris and Lewis, II, Philip M.},
  title     = {Hierarchies of Memory Limited Computations},
  booktitle = {Proceedings of the 6th Annual Symposium on Switching Circuit Theory and Logical
               Design},
  series    = {SWCT 1965},
  pages     = {179--190},
  year      = {1965},
  doi       = {10.1109/FOCS.1965.11}
}

@article{Stockmeyer1976,
  author    = {Stockmeyer, Larry J.},
  title     = {The Polynomial-Time Hierarchy},
  journal   = {Theoretical Computer Science},
  volume    = {3},
  number    = {1},
  pages     = {1--22},
  year      = {1976},
  doi       = {10.1016/0304-3975(76)90061-X}
}

@inproceedings{Stockmeyer1983,
  author    = {Stockmeyer, Larry J.},
  title     = {The Complexity of Approximate Counting},
  booktitle = {Proceedings of the 15th Annual ACM Symposium on Theory of Computing},
  pages     = {118--126},
  year      = {1983}
}

@inproceedings{StockmeyerMeyer1973,
  author    = {Stockmeyer, Larry J. and Meyer, Albert R.},
  title     = {Word Problems Requiring Exponential Time (Preliminary Report)},
  booktitle = {Proceedings of the Fifth Annual {ACM} Symposium on Theory of Computing (STOC 1973)},
  pages     = {1--9},
  year      = {1973},
  doi       = {10.1145/800125.804029}
}

@article{Subbotovskaya1961,
  author  = {Subbotovskaya, B. A.},
  title   = {Realizations of Linear Functions by Formulas Using $\lor$, $\&$, $-$},
  journal = {Soviet Mathematics Doklady},
  volume  = {2},
  pages   = {110--112},
  year    = {1961},
  note    = {Russian original: Doklady Akademii Nauk SSSR 136(3), 553--555}
}

@article{Sudan1997,
  author    = {Sudan, Madhu},
  title     = {Decoding of {Reed Solomon} Codes beyond the Error-Correction Bound},
  journal   = {Journal of Complexity},
  volume    = {13},
  number    = {1},
  pages     = {180--193},
  year      = {1997},
  doi       = {10.1006/jcom.1997.0439}
}

@article{SudanTrevisanVadhan2001,
  author    = {Sudan, Madhu and Trevisan, Luca and Vadhan, Salil},
  title     = {Pseudorandom Generators without the {XOR} Lemma},
  journal   = {Journal of Computer and System Sciences},
  volume    = {62},
  number    = {2},
  pages     = {236--266},
  year      = {2001},
  doi       = {10.1006/jcss.2000.1730}
}

@article{Szelepcsenyi1987,
  author  = {Szelepcs{\'e}nyi, R{\'o}bert},
  title   = {The Method of Forcing for Nondeterministic Automata},
  journal = {Bulletin of the European Association for Theoretical Computer Science},
  volume  = {33},
  pages   = {96--100},
  year    = {1987}
}

@article{Talagrand1994,
  author    = {Talagrand, Michel},
  title     = {On {Russo}'s Approximate Zero-One Law},
  journal   = {The Annals of Probability},
  volume    = {22},
  number    = {3},
  pages     = {1576--1587},
  year      = {1994},
  doi       = {10.1214/aop/1176988612}
}

@article{Tanner1981,
  author  = {Tanner, R. Michael},
  title   = {A Recursive Approach to Low Complexity Codes},
  journal = {IEEE Transactions on Information Theory},
  volume  = {27},
  number  = {5},
  pages   = {533--547},
  year    = {1981},
  doi     = {10.1109/TIT.1981.1056404}
}

@article{Tardos1989,
  author    = {Tardos, G{\'a}bor},
  title     = {Query complexity, or why is it difficult to separate {NP}$^A \cap$ co{NP}$^A$ from
               {P}$^A$ by random oracles {A}?},
  journal   = {Combinatorica},
  volume    = {9},
  number    = {4},
  pages     = {385--392},
  year      = {1989}
}

@article{Thaler2022,
  author  = {Thaler, Justin},
  title   = {Proofs, Arguments, and Zero-Knowledge},
  journal = {Foundations and Trends in Privacy and Security},
  volume  = {4},
  number  = {2--4},
  pages   = {117--660},
  year    = {2022},
  doi     = {10.1561/3300000030}
}

@incollection{ Thomas1990,
  author       = {Wolfgang Thomas},
  editor       = {Jan van Leeuwen},
  title        = {Automata on Infinite Objects},
  booktitle    = {Handbook of Theoretical Computer Science, Volume {B:} Formal Models and Semantics},
  pages        = {133--191},
  publisher    = {Elsevier and {MIT} Press},
  year         = {1990}
}

@misc{ThresholdCircuitRepresentations2026,
  title        = {Threshold Circuits as Decision Trees and Finite-State Programs},
  year         = {2026},
  howpublished = {Research draft, second pass},
  note         = {October 18, 2026; repository revision
                  791fa2749317fbcc7b5c5b030a1e6fadd28cc44c},
  url          = {https://github.com/SamuelSchlesinger/threshold-circuits/blob/791fa2749317fbcc7b5c5b030a1e6fadd28cc44c/threshold_circuit_representations.tex}
}

@article{Toda1991,
  author = {Toda, Seinosuke},
  title = {{PP} Is as Hard as the Polynomial-Time Hierarchy},
  journal = {SIAM Journal on Computing},
  volume = {20},
  number = {5},
  pages = {865--877},
  year = {1991},
  doi = {10.1137/0220053},
  url = {https://doi.org/10.1137/0220053}
}

@misc{Trevisan2009GL,
  author = {Trevisan, Luca},
  title  = {{CS276} Lecture 12: {Goldreich--Levin}},
  year   = {2009},
  note   = {Scribed by Jonah Sherman},
  url    = {https://lucatrevisan.wordpress.com/2009/03/09/cs276-lecture-12-goldreich-levin/}
}

@misc{Trevisan2009PRG,
  author = {Trevisan, Luca},
  title = {{CS276 Lecture 13: Pseudorandom Generators}},
  year = {2009},
  month = mar,
  note = {Scribed by Siu-On Chan},
  url = {https://lucatrevisan.wordpress.com/2009/03/16/cs276-lecture-13-pseudorandom-generators/}
}

@misc{Tromino2025,
  author        = {{MIT--ULB CompGeom Group} and Abel, Zachary and Akitaya, Hugo and Chung, Lily and
                   Demaine, Erik D. and Diomidova, Jenny and Hendrickson, Della and
                   Langerman, Stefan and Lynch, Jayson},
  title         = {Undecidability of Tiling with a Tromino},
  year          = {2025},
  eprint        = {2509.07906},
  archivePrefix = {arXiv},
  primaryClass  = {cs.CG},
  doi           = {10.48550/arXiv.2509.07906},
  url           = {https://arxiv.org/abs/2509.07906},
  note          = {Lean formalization: \url{https://github.com/edemaine/lean-trominoes}}
}

@incollection{Tseitin1983,
  author = {Tseitin, G. S.},
  title = {On the Complexity of Derivation in Propositional Calculus},
  booktitle = {Automation of Reasoning: 2: Classical Papers on Computational Logic 1967--1970},
  editor = {Siekmann, J{\"o}rg H. and Wrightson, Graham},
  pages = {466--483},
  publisher = {Springer},
  year = {1983},
  note = {Originally published in Russian in 1968},
  doi = {10.1007/978-3-642-81955-1_28},
  url = {https://doi.org/10.1007/978-3-642-81955-1_28}
}

@article{Turing1936,
  author    = {Turing, Alan M.},
  title     = {On Computable Numbers, with an Application to the {Entscheidungsproblem}},
  journal   = {Proceedings of the London Mathematical Society},
  volume    = {s2-42},
  number    = {1},
  pages     = {230--265},
  year      = {1936},
  doi       = {10.1112/plms/s2-42.1.230}
}

@incollection{Uhlig1992,
  author = {Uhlig, Dietmar},
  title = {Networks Computing {Boolean} Functions for Multiple Input Values},
  booktitle = {Boolean Function Complexity},
  editor = {Paterson, Michael S.},
  series = {London Mathematical Society Lecture Note Series},
  volume = {169},
  pages = {165--173},
  publisher = {Cambridge University Press},
  year = {1992},
  doi = {10.1017/CBO9780511526633.013},
  url = {https://doi.org/10.1017/CBO9780511526633.013}
}

@article{Urquhart1987,
  author = {Urquhart, Alasdair},
  title = {Hard Examples for Resolution},
  journal = {Journal of the ACM},
  volume = {34},
  number = {1},
  pages = {209--219},
  year = {1987},
  doi = {10.1145/7531.8928},
  url = {https://doi.org/10.1145/7531.8928}
}

@article{Vadhan2012,
  author    = {Vadhan, Salil P.},
  title     = {Pseudorandomness},
  journal   = {Foundations and Trends in Theoretical Computer Science},
  volume    = {7},
  number    = {1--3},
  pages     = {1--336},
  year      = {2012},
  doi       = {10.1561/0400000010}
}

@inproceedings{Valiant1977,
  author    = {Valiant, Leslie G.},
  title     = {Graph-Theoretic Arguments in Low-Level Complexity},
  booktitle = {Mathematical Foundations of Computer Science 1977},
  series    = {Lecture Notes in Computer Science},
  volume    = {53},
  pages     = {162--176},
  publisher = {Springer},
  year      = {1977},
  doi       = {10.1007/3-540-08353-7_135}
}

@article{Valiant1979,
  author    = {Valiant, Leslie G.},
  title     = {The Complexity of Computing the Permanent},
  journal   = {Theoretical Computer Science},
  volume    = {8},
  number    = {2},
  pages     = {189--201},
  year      = {1979},
  doi       = {10.1016/0304-3975(79)90044-6}
}

@inproceedings{Valiant1979Algebra,
  author    = {Valiant, Leslie G.},
  title     = {Completeness Classes in Algebra},
  booktitle = {Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing},
  series    = {STOC '79},
  pages     = {249--261},
  publisher = {ACM},
  year      = {1979},
  doi       = {10.1145/800135.804419}
}

@inproceedings{Valiant1984,
  author       = {Valiant, L. G.},
  title        = {A Theory of the Learnable},
  year         = {1984},
  isbn         = {0-89791-133-4},
  publisher    = {Association for Computing Machinery},
  address      = {New York, NY, USA},
  url          = {https://doi.org/10.1145/800057.808710},
  doi          = {10.1145/800057.808710},
  booktitle    = {Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing},
  pages        = {436--445},
  series       = {STOC '84}
}

@article{ValiantVazirani1986,
  author    = {Valiant, Leslie G. and Vazirani, Vijay V.},
  title     = {{NP} is as Easy as Detecting Unique Solutions},
  journal   = {Theoretical Computer Science},
  volume    = {47},
  pages     = {85--93},
  year      = {1986},
  doi       = {10.1016/0304-3975(86)90135-0}
}

@article{VanEmdeBoasKaasZijlstra1977,
  author  = {van Emde Boas, Peter and Kaas, R. and Zijlstra, E.},
  title   = {Design and Implementation of an Efficient Priority Queue},
  journal = {Mathematical Systems Theory},
  volume  = {10},
  pages   = {99--127},
  year    = {1977},
  doi     = {10.1007/BF01683268},
  url     = {https://ir.cwi.nl/pub/6885/6885D.pdf}
}

@article{Vardi1989,
  author       = {Moshe Y. Vardi},
  title        = {A Note on the Reduction of Two-Way Automata to One-Way Automata},
  journal      = {Information Processing Letters},
  volume       = {30},
  number       = {5},
  pages        = {261--264},
  year         = {1989}
}

@article{Varshamov1957,
  author    = {Varshamov, R. R.},
  title     = {Estimate of the Number of Signals in Error Correcting Codes},
  journal   = {Doklady Akademii Nauk SSSR},
  volume    = {117},
  pages     = {739--741},
  year      = {1957}
}

@article{VassilevskaWilliamsWilliams2013,
  author  = {Vassilevska Williams, Virginia and Williams, Ryan},
  title   = {Finding, Minimizing, and Counting Weighted Subgraphs},
  journal = {SIAM Journal on Computing},
  volume  = {42},
  number  = {3},
  pages   = {831--854},
  year    = {2013},
  doi     = {10.1137/09076619X}
}

@phdthesis{Vazirani1986,
  author    = {Vazirani, Umesh V.},
  title     = {Randomness, Adversaries and Computation},
  school    = {University of California, Berkeley},
  year      = {1986}
}

@book{Vollmer1999,
  author    = {Vollmer, Heribert},
  title     = {Introduction to Circuit Complexity: A Uniform Approach},
  series    = {Texts in Theoretical Computer Science. An EATCS Series},
  publisher = {Springer},
  year      = {1999},
  doi       = {10.1007/978-3-662-03927-4}
}

@article{ Volzer2004,
  title     = {A constructive proof for {FLP}},
  author    = {V{\"o}lzer, Hagen},
  journal   = {Information Processing Letters},
  volume    = {92},
  number    = {2},
  pages     = {83--87},
  year      = {2004},
  publisher = {Elsevier},
  doi       = {10.1016/j.ipl.2004.06.008},
  url       = {https://doi.org/10.1016/j.ipl.2004.06.008}
}

@article{vonNeumann1928,
  author    = {von Neumann, John},
  title     = {Zur {Theorie} der {Gesellschaftsspiele}},
  journal   = {Mathematische Annalen},
  volume    = {100},
  number    = {1},
  pages     = {295--320},
  year      = {1928},
  doi       = {10.1007/BF01448847}
}

@article{Wagner1986,
  author  = {Wagner, Klaus W.},
  title   = {The Complexity of Combinatorial Problems with Succinct Input Representation},
  journal = {Acta Informatica},
  volume  = {23},
  number  = {3},
  pages   = {325--356},
  year    = {1986},
  doi     = {10.1007/BF00289117}
}

@techreport{Watson2012,
  author      = {Watson, Thomas},
  title       = {The Complexity of Estimating Min-Entropy},
  institution = {Electronic Colloquium on Computational Complexity},
  number      = {TR12-070},
  year        = {2012},
  url         = {https://eccc.weizmann.ac.il/report/2012/070/}
}

@book{Wegener1987,
  author = {Wegener, Ingo},
  title = {The Complexity of {Boolean} Functions},
  publisher = {Wiley-Teubner},
  year = {1987},
  url = {https://eccc.weizmann.ac.il/static/books/The_Complexity_of_Boolean_Functions/}
}

@article{WegmanCarter1981,
  author    = {Wegman, Mark N. and Carter, J. Lawrence},
  title     = {New Hash Functions and Their Use in Authentication and Set Equality},
  journal   = {Journal of Computer and System Sciences},
  volume    = {22},
  number    = {3},
  pages     = {265--279},
  year      = {1981},
  doi       = {10.1016/0022-0000(81)90033-7}
}

@misc{WelchBerlekamp1986,
  author    = {Welch, Lloyd R. and Berlekamp, Elwyn R.},
  title     = {Error Correction for Algebraic Block Codes},
  note      = {U.S. Patent 4,633,470},
  year      = {1986}
}

@misc{         WikipediaMyhillNerode2026,
  author       = {{Wikipedia contributors}},
  title        = {{Myhill--Nerode theorem}},
  howpublished = {Wikipedia, The Free Encyclopedia},
  year         = {2026},
  url          = {https://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem},
  note         = {[Online; accessed 9-April-2026]}
}

@article{Williams2005,
  author    = {Williams, Ryan},
  title     = {A New Algorithm for Optimal 2-Constraint Satisfaction and Its Implications},
  journal   = {Theoretical Computer Science},
  volume    = {348},
  number    = {2--3},
  pages     = {357--365},
  year      = {2005},
  doi       = {10.1016/j.tcs.2005.09.023}
}

@article{Williams2014,
  author    = {Williams, Ryan},
  title     = {Nonuniform {ACC} Circuit Lower Bounds},
  journal   = {Journal of the ACM},
  volume    = {61},
  number    = {1},
  pages     = {2:1--2:32},
  year      = {2014},
  doi       = {10.1145/2559903},
  url       = {https://doi.org/10.1145/2559903}
}

@article{Wilson1985,
  author = {Christopher B. Wilson},
  title = {Relativized circuit complexity},
  journal = {Journal of Computer and System Sciences},
  volume = {31},
  number = {2},
  pages = {169--181},
  year = {1985},
  doi = {10.1016/0022-0000(85)90040-6}
}

@incollection{WinskelNielsen1995,
  author       = {Winskel, Glynn and Nielsen, Mogens},
  isbn         = {9780198537809},
  title        = {Models for concurrency},
  booktitle    = {Handbook of Logic in Computer Science},
  publisher    = {Oxford University Press},
  year         = {1995},
  month        = {05},
  doi          = {10.1093/oso/9780198537809.003.0001},
  url          = {https://doi.org/10.1093/oso/9780198537809.003.0001},
  eprint       = {https://academic.oup.com/book/0/chapter/421962123/chapter-pdf/52352653/isbn-9780198537809-book-part-1.pdf},
}

@article{Wrathall1976,
  author    = {Wrathall, Celia},
  title     = {Complete Sets and the Polynomial-Time Hierarchy},
  journal   = {Theoretical Computer Science},
  volume    = {3},
  number    = {1},
  pages     = {23--33},
  year      = {1976},
  doi       = {10.1016/0304-3975(76)90062-1}
}

@article{Yablonskii1954,
  author    = {Yablonskii, S. V.},
  title     = {Realization of a linear function in the class of $\pi$-schemes},
  journal   = {Doklady Akademii Nauk SSSR},
  volume    = {94},
  number    = {5},
  pages     = {805--806},
  year      = {1954},
  note      = {In Russian}
}

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

@inproceedings{Yao1982,
  author    = {Yao, Andrew C.},
  title     = {Theory and Application of Trapdoor Functions},
  booktitle = {Proceedings of the 23rd Annual Symposium on Foundations of Computer Science},
  series    = {FOCS 1982},
  pages     = {80--91},
  year      = {1982},
  doi       = {10.1109/SFCS.1982.45}
}

@misc{Zhao2023,
  author       = {Zhao, Yufei},
  title        = {Probabilistic Methods in Combinatorics},
  howpublished = {Lecture notes, MIT 18.226},
  year         = {2023}
}