[AI99] Luca Aceto, Anna Ingólfsdóttir.
Testing Hennessy-Milner Logic with Recursion.
In Wolfgang Thomas, editor, 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, volume 1578 of Lecture Notes in Computer Science, 41–55. Springer, 1999.
doi:10.1007/3-540-49019-1\_4, URL: https://doi.org/10.1007/3-540-49019-1\_4.
[Adl78] Leonard Adleman.
Two Theorems on Random Polynomial Time.
In 19th Annual Symposium on Foundations of Computer Science, 75–83. IEEE Computer Society, 1978.
doi:10.1109/SFCS.1978.37. [1][2][3][4][5]
[Ajt96] Miklós Ajtai.
Generating Hard Instances of Lattice Problems.
In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC '96), 99–108. ACM, 1996.
doi:10.1145/237814.237838. [1][2]
[ABK+06] Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger.
Power from Random Strings.
SIAM Journal on Computing, 35(6):1467–1493, 2006.
doi:10.1137/050628994. [1][2][3][4][5][6][7][8]
[AB87] Noga Alon, Ravi B. Boppana.
The Monotone Circuit Complexity of Boolean Functions.
Combinatorica, 7(1):1–22, 1987.
doi:10.1007/BF02579196. [1]
[AGHP92] Noga Alon, Oded Goldreich, Johan Håstad, René Peralta.
Simple Constructions of Almost $k$-wise Independent Random Variables.
Random Structures & Algorithms, 3(3):289–304, 1992.
doi:10.1002/rsa.3240030308. [1][2][3][4][5][6][7][8]
[AMT99] Arne Andersson, Peter Bro Miltersen, Mikkel Thorup.
Fusion Trees can be Implemented with AC$^0$ Instructions Only.
Theoretical Computer Science, 215(1–2):337–344, 1999.
doi:10.1016/S0304-3975(98)00172-8. [1][2]
[And87] A. E. Andreev.
On a Method for Obtaining More Than Quadratic Effective Lower Bounds for the Complexity of $\pi$-Schemes.
Moscow University Mathematics Bulletin, 42(1):24–29, 1987.
Russian original: Vestnik Moskovskogo Universiteta, Seriya 1, (1), 70–73. [1][2][3][4]
[And89] A. E. Andreev.
On the Complexity of the Realization of Partial Boolean Functions by Circuits of Functional Elements.
Diskretnaya Matematika, 1(4):36–45, 1989.
In Russian. [1][2]
[Ang80] Dana Angluin.
Inductive Inference of Formal Languages from Positive Data.
Information and Control, 45(2):117–135, 1980.
doi:10.1016/S0019-9958(80)90285-5.
[AS98] Sanjeev Arora, Shmuel Safra.
Probabilistic Checking of Proofs: A New Characterization of NP.
Journal of the ACM, 45(1):70–122, 1998.
doi:10.1145/273865.273901. [1][2][3]
[BFLS91] László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy.
Checking Computations in Polylogarithmic Time.
In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC 1991, 21–32. 1991.
doi:10.1145/103418.103428. [1][2]
[BFNW93] László Babai, Lance Fortnow, Noam Nisan, Avi Wigderson.
BPP Has Subexponential Time Simulations Unless EXPTIME Has Publishable Proofs.
Computational Complexity, 3(4):307–318, 1993.
doi:10.1007/BF01275486. [1]
[BM88] László Babai, Shlomo Moran.
Arthur–Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes.
Journal of Computer and System Sciences, 36(2):254–276, 1988.
doi:10.1016/0022-0000(88)90028-1. [1][2][3][4][5][6][7]
[BGS75] Theodore Baker, John Gill, Robert Solovay.
Relativizations of the $\mathcal{P} =? \mathcal{NP}$ Question.
SIAM Journal on Computing, 4(4):431–442, 1975.
doi:10.1137/0204037. [1][2][3][4][5][6][7]
[BGH90] Richard Beigel, John Gill, Ulrich Hertrampf.
Counting Classes: Thresholds, Parity, Mods, and Fewness.
In STACS 90: 7th Annual Symposium on Theoretical Aspects of Computer Science, volume 415 of Lecture Notes in Computer Science, 49–57. Springer, 1990.
doi:10.1007/3-540-52282-4_31. [1][2]
[BRS95] Richard Beigel, Nick Reingold, Daniel A. Spielman.
PP Is Closed under Intersection.
Journal of Computer and System Sciences, 50(2):191–202, 1995.
doi:10.1006/jcss.1995.1017. [1][2][3][4][5]
[BN06] Mihir Bellare, Gregory Neven.
Multi-Signatures in the Plain Public-Key Model and a General Forking Lemma.
In Proceedings of the 13th ACM Conference on Computer and Communications Security, 390–399. ACM, 2006.
doi:10.1145/1180405.1180453. [1][2][3][4][5][6][7][8][9]
[BR94] Mihir Bellare, John Rompel.
Randomness-Efficient Oblivious Sampling.
In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, FOCS 1994, 276–287. 1994.
doi:10.1109/SFCS.1994.365687. [1][2]
[BOGKW88] Michael Ben-Or, Shafi Goldwasser, Joe Kilian, Avi Wigderson.
Multi-prover Interactive Proofs: How to Remove Intractability Assumptions.
In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC '88, 113–131. ACM, 1988.
doi:10.1145/62212.62223, URL: https://doi.org/10.1145/62212.62223. [1][2][3][4]
[BSCS16] Eli Ben-Sasson, Alessandro Chiesa, Nicholas Spooner.
Interactive Oracle Proofs.
In Theory of Cryptography – TCC 2016-B, Part II, volume 9986 of Lecture Notes in Computer Science, 31–60. Springer, 2016.
doi:10.1007/978-3-662-53644-5_2. [1][2]
[BBBV97] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani.
Strengths and Weaknesses of Quantum Computing.
SIAM Journal on Computing, 26(5):1510–1523, 1997.
doi:10.1137/S0097539796300933. [1][2][3][4]
[Ber84] Stuart J. Berkowitz.
On Computing the Determinant in Small Parallel Time Using a Small Number of Processors.
Information Processing Letters, 18(3):147–150, 1984.
doi:10.1016/0020-0190(84)90018-8. [1][2]
[BRV01] Patrick Blackburn, Maarten de Rijke, Yde Venema.
Modal Logic.
Cambridge Tracts in Theoretical Computer Science.
Cambridge University Press, 2001.
[BI87] Manuel Blum, Russell Impagliazzo.
Generic oracles and oracle classes.
In 28th Annual Symposium on Foundations of Computer Science, 118–126. 1987. [1][2]
[BLR93] Manuel Blum, Michael Luby, Ronitt Rubinfeld.
Self-Testing/Correcting with Applications to Numerical Problems.
Journal of Computer and System Sciences, 47(3):549–595, 1993.
doi:10.1016/0022-0000(93)90044-W. [1][2][3][4]
[BGM06] Elmar Böhler, Christian Glaßer, Daniel Meister.
Error-bounded probabilistic computations between MA and AM.
Journal of Computer and System Sciences, 72(6):1043–1076, 2006. [1][2][3][4][5][6][7][8][9][10][11][12]
[BHHO08] Dan Boneh, Shai Halevi, Mike Hamburg, Rafail Ostrovsky.
Circular-Secure Encryption from Decision Diffie-Hellman.
In Advances in Cryptology – CRYPTO 2008, volume 5157 of Lecture Notes in Computer Science, 108–125. Springer, 2008.
URL: https://crypto.stanford.edu/~dabo/papers/circular.pdf. [1][2][3][4][5]
[BE95] Peter Borwein, Tamás Erdélyi.
Polynomials and Polynomial Inequalities.
Volume 161 of Graduate Texts in Mathematics.
Springer, 1995.
doi:10.1007/978-1-4612-0793-1. [1][2]
[BCMS16] Simone Bova, Florent Capelli, Stefan Mengel, Friedrich Slivovsky.
Knowledge Compilation Meets Communication Complexity.
In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI 2016), 1008–1014. 2016. [1][2]
[BFvMT00] Harry Buhrman, Lance Fortnow, Dieter van Melkebeek, Leen Torenvliet.
Separating Complexity Classes Using Autoreducibility.
SIAM Journal on Computing, 29(5):1497–1520, 2000.
doi:10.1137/S0097539798334736. [1][2]
[CH90] Jin-Yi Cai, Lane A. Hemachandra.
On the Power of Parity Polynomial Time.
Mathematical Systems Theory, 23(1):95–106, 1990.
doi:10.1007/BF02090768. [1][2]
[CCDF97] Liming Cai, Jianer Chen, Rodney G. Downey, Michael R. Fellows.
Advice classes of parameterized tractability.
Annals of Pure and Applied Logic, 84(1):119–138, 1997.
doi:10.1016/S0168-0072(96)00020-6. [1][2][3][4]
[Cal09] Chris Calabro.
The Exponential Complexity of Satisfiability Problems.
PhD thesis, University of California, San Diego, 2009. [1][2][3][4][5][6][7][8]
[Cal22] Bruna Calisto.
Formalization in Coq of the Standardization Theorem for $\lambda$-calculus.
Master's thesis, Universidade do Minho, 2022.
[CCH+19] Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, Daniel Wichs.
Fiat–Shamir: From Practice to Theory.
In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, 1082–1090. ACM, 2019.
doi:10.1145/3313276.3316380. [1][2]
[CK15] Ruiwen Chen, Valentine Kabanets.
Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits.
In Computing and Combinatorics (COCOON 2015), Lecture Notes in Computer Science, 211–222. Springer, 2015.
doi:10.1007/978-3-319-21398-9_17. [1][2]
[CGFS86] Fan R. K. Chung, Ronald L. Graham, Peter Frankl, James B. Shearer.
Some Intersection Theorems for Ordered Sets and Graphs.
Journal of Combinatorial Theory, Series A, 43(1):23–37, 1986.
doi:10.1016/0097-3165(86)90019-1. [1][2]
[CM23] James Cook, Ian Mertz.
Tree Evaluation is in Space $O(\log n \cdot \log\log n)$.
Technical Report TR23-174, Electronic Colloquium on Computational Complexity, 2023.
Conference version in STOC 2024. [1][2][3][4][5][6][7][8][9][10]
[CMcKW+12] Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam.
Pebbles and Branching Programs for Tree Evaluation.
ACM Transactions on Computation Theory, 3(2):4:1–4:43, 2012. [1][2][3]
[Cop18] Martín Copes.
A machine-checked proof of the Standardization Theorem in Lambda Calculus using multiple substitution.
Master's thesis, Universidad ORT Uruguay, 2018.
[CR92] Don Coppersmith, Theodore J. Rivlin.
The Growth of Polynomials Bounded at Equally Spaced Points.
SIAM Journal on Mathematical Analysis, 23(4):970–983, 1992.
doi:10.1137/0523054. [1][2][3]
[CDS94] Ronald Cramer, Ivan Damgård, Berry Schoenmakers.
Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols.
In Advances in Cryptology – CRYPTO '94, volume 839 of Lecture Notes in Computer Science, 174–187. Springer, 1994.
doi:10.1007/3-540-48658-5_19. [1]
[Cut80] Nigel J. Cutland.
Computability: An Introduction to Recursive Function Theory.
Cambridge University Press, Cambridge, 1980.
ISBN 978-0-521-29465-2. [1][2]
[Dan08] Nils Anders Danielsson.
Lightweight semiformal time complexity analysis for purely functional data structures.
In Proceedings of the 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '08, 133–144. New York, NY, USA, 2008. Association for Computing Machinery.
doi:10.1145/1328438.1328457, URL: https://doi.org/10.1145/1328438.1328457.
[DP60] Martin Davis, Hilary Putnam.
A Computing Procedure for Quantification Theory.
Journal of the ACM, 7(3):201–215, 1960.
doi:10.1145/321033.321034. [1][2]
[DHKP97] Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, Martti Penttonen.
A Reliable Randomized Algorithm for the Closest-Pair Problem.
Journal of Algorithms, 25(1):19–51, 1997.
doi:10.1006/jagm.1997.0873. [1][2][3][4][5]
[DKL+18] Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, Damien Stehlé.
CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme.
IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(1):238–268, 2018.
doi:10.13154/tches.v2018.i1.238-268. [1][2][3][4]
[DKS12] Orr Dunkelman, Nathan Keller, Adi Shamir.
Minimalism in Cryptography: The Even–Mansour Scheme Revisited.
In Advances in Cryptology – EUROCRYPT 2012, volume 7237 of Lecture Notes in Computer Science, 336–354. Springer, 2012.
doi:10.1007/978-3-642-29011-4_21. [1][2][3][4][5][6][7][8]
[EZ64] Hartmut Ehlich, Karl Zeller.
Schwankung von Polynomen zwischen Gitterpunkten.
Mathematische Zeitschrift, 86(1):41–44, 1964.
doi:10.1007/BF01111276. [1][2][3]
[EL75] Paul Erdős, László Lovász.
Problems and Results on 3-Chromatic Hypergraphs and Some Related Questions.
In Infinite and Finite Sets, volume 10 of Colloquia Mathematica Societatis János Bolyai, pages 609–627.
North-Holland, 1975. [1][2][3]
[EvdHM24] Jeff Erickson, Ivor van der Hoog, Tillmann Miltzow.
Smoothing the Gap Between NP and $\exists\mathbb{R}$.
SIAM Journal on Computing, 53(6):FOCS20-102–FOCS20-138, 2024.
doi:10.1137/20M1385287, arXiv:1912.02278. [1][2]
[EM97] Shimon Even, Yishay Mansour.
A Construction of a Cipher from a Single Pseudorandom Permutation.
Journal of Cryptology, 10(3):151–161, 1997.
doi:10.1007/s001459900025. [1][2][3][4]
[ESY84] Shimon Even, Alan L. Selman, Yacov Yacobi.
The Complexity of Promise Problems with Applications to Public-Key Cryptography.
Information and Control, 61(2):159–173, 1984.
doi:10.1016/S0019-9958(84)80056-X. [1][2][3]
[FGL+96] Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy.
Interactive Proofs and the Hardness of Approximating Cliques.
Journal of the ACM, 43(2):268–292, 1996.
doi:10.1145/226643.226652. [1][2]
[FS87] Amos Fiat, Adi Shamir.
How to Prove Yourself: Practical Solutions to Identification and Signature Problems.
In Advances in Cryptology – CRYPTO '86, volume 263 of Lecture Notes in Computer Science, 186–194. Springer, 1987.
doi:10.1007/3-540-47721-7_12. [1]
[FGHK16] Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov.
A Better-than-$3n$ Lower Bound for the Circuit Complexity of an Explicit Function.
In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 89–98. 2016.
doi:10.1109/FOCS.2016.19. [1][2][3][4][5]
[For24] Michael A. Forbes.
Low-Depth Algebraic Circuit Lower Bounds over Any Field.
In Rahul Santhanam, editor, 39th Computational Complexity Conference (CCC 2024), volume 300 of Leibniz International Proceedings in Informatics (LIPIcs), 31:1–31:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024.
doi:10.4230/LIPIcs.CCC.2024.31. [1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16]
[For66] Jr. , G. David Forney.
Concatenated Codes.
MIT Press, 1966. [1][2][3]
[Fri98] Ehud Friedgut.
Boolean Functions With Low Average Sensitivity Depend On Few Coordinates.
Combinatorica, 18(1):27–35, 1998.
doi:10.1007/PL00009809. [1][2][3][4]
[Gir95] J.-Y. Girard.
Linear Logic: its syntax and semantics, pages 1–42.
London Mathematical Society Lecture Note Series.
Cambridge University Press, 1995.
[GPSZ08] Christian Glaßer, A. Pavan, Alan L. Selman, Liyu Zhang.
Splitting NP-Complete Sets.
SIAM Journal on Computing, 37(5):1517–1535, 2008.
doi:10.1137/060673886. [1][2]
[Gol24] Oded Goldreich.
On the Cook–Mertz Tree Evaluation procedure.
Technical Report TR24-109, Electronic Colloquium on Computational Complexity, 2024.
Revision 2, 27 December 2024. [1][2][3][4][5][6][7][8][9][10][11]
[GKR15] Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum.
Delegating Computation: Interactive Proofs for Muggles.
Journal of the ACM, 62(4):27:1–27:64, 2015.
doi:10.1145/2699436. [1][2][3][4][5]
[GMR89] Shafi Goldwasser, Silvio Micali, Charles Rackoff.
The Knowledge Complexity of Interactive Proof Systems.
SIAM Journal on Computing, 18(1):186–208, 1989.
doi:10.1137/0218012. [1][2][3]
[GS86] Shafi Goldwasser, Michael Sipser.
Private Coins versus Public Coins in Interactive Proof Systems.
In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 59–68. 1986.
doi:10.1145/12130.12137. [1][2][3][4][5][6][7][8][9][10]
[GKST16] Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki.
Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework.
In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), volume 58 of Leibniz International Proceedings in Informatics (LIPIcs), 45:1–45:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016.
doi:10.4230/LIPIcs.MFCS.2016.45. [1][2]
[GPW17] Mika Göös, Toniann Pitassi, Thomas Watson.
Query-to-Communication Lifting for BPP.
In 58th Annual Symposium on Foundations of Computer Science (FOCS), 132–143. 2017.
doi:10.1109/FOCS.2017.21. [1][2][3][4]
[GL92] Craig Gotsman, Nathan Linial.
The Equivalence of Two Problems on the Cube.
Journal of Combinatorial Theory, Series A, 61(1):142–146, 1992.
doi:10.1016/0097-3165(92)90060-8. [1][2]
[Gro96] Lov K. Grover.
A Fast Quantum Mechanical Algorithm for Database Search.
In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), 212–219. 1996.
doi:10.1145/237814.237866. [1][2][3]
[HHT97] Yenjo Han, Lane A. Hemaspaandra, Thomas Thierauf.
Threshold computation and cryptographic security.
SIAM Journal on Computing, 26(1):59–78, 1997.
doi:10.1137/S0097539792240467. [1][2][3][4]
[HS74] Juris Hartmanis, Janos Simon.
On the Power of Multiplication in Random Access Machines.
In 15th Annual Symposium on Switching and Automata Theory (SWAT 1974), 13–23. IEEE, 1974.
doi:10.1109/SWAT.1974.20. [1][2]
[Hau92] David Haussler.
Decision Theoretic Generalizations of the PAC Model for Neural Net and Other Learning Applications.
Information and Computation, 100(1):78–150, 1992.
doi:10.1016/0890-5401(92)90010-D. [1][2]
[HHSW18] Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, Osamu Watanabe.
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction.
In 43rd International Symposium on Mathematical Foundations of Computer Science, volume 117 of Leibniz International Proceedings in Informatics, 51:1–51:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018.
doi:10.4230/LIPIcs.MFCS.2018.51. [1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16][17][18]
[Hol82] W. M. L. Holcombe.
Algebraic automata theory.
Volume 1 of Cambridge Studies in Advanced Mathematics.
Cambridge University Press, 1982.
ISBN 0-521-60492-3.
[HMU06] John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman.
Introduction to Automata Theory, Languages, and Computation (3rd Edition).
Addison-Wesley Longman Publishing Co., Inc., USA, 2006.
ISBN 0321455363. [1][2][3]
[Ila20a] Rahul Ilango.
Approaching MCSP from Above and Below: Hardness for a Conditional Variant and $\mathsf{AC}^0[p]$.
In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), 34:1–34:26. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.
doi:10.4230/LIPIcs.ITCS.2020.34. [1][2][3][4][5][6][7][8]
[ILO20] Rahul Ilango, Bruno Loff, Igor Carboni Oliveira.
NP-Hardness of Circuit Minimization for Multi-Output Functions.
In 35th Computational Complexity Conference (CCC 2020), volume 169 of Leibniz International Proceedings in Informatics (LIPIcs), 22:1–22:36. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.
doi:10.4230/LIPIcs.CCC.2020.22. [1][2][3]
[Imp95] Russell Impagliazzo.
Hard-Core Distributions for Somewhat Hard Problems.
In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, FOCS 1995, 538–545. 1995.
doi:10.1109/SFCS.1995.492584. [1][2][3][4][5][6][7][8]
[IW97] Russell Impagliazzo, Avi Wigderson.
P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma.
In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, STOC 1997, 220–229. 1997.
doi:10.1145/258533.258590. [1][2][3][4][5][6][7][8]
[Juk11] Stasys Jukna.
Extremal Combinatorics: With Applications in Computer Science.
Second edition.
Texts in Theoretical Computer Science. An EATCS Series.
Springer, 2011.
doi:10.1007/978-3-642-17364-6. [1][2][3][4][5][6]
[KKL88] Jeff Kahn, Gil Kalai, Nathan Linial.
The Influence of Variables on Boolean Functions.
In 29th Annual Symposium on Foundations of Computer Science, 68–80. IEEE Computer Society, 1988.
doi:10.1109/SFCS.1988.21923. [1][2][3][4]
[KS92] Bala Kalyanasundaram, Georg Schnitger.
The Probabilistic Communication Complexity of Set Intersection.
SIAM Journal on Discrete Mathematics, 5(4):545–557, 1992.
doi:10.1137/0405044. [1][2][3][4][5]
[KW90] Mauricio Karchmer, Avi Wigderson.
Monotone circuits for connectivity require super-logarithmic depth.
SIAM Journal on Discrete Mathematics, 3(2):255–265, 1990. [1][2][3][4][5][6]
[Kar93] David R. Karger.
Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm.
In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1993, 21–30. 1993. [1][2][3][4]
[KL80] Richard M. Karp, Richard J. Lipton.
Some Connections between Nonuniform and Uniform Complexity Classes.
In Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980, 302–309. 1980.
doi:10.1145/800141.804678. [1][2][3][4][5][6][7][8][9][10]
[KV94] Michael J. Kearns, Umesh V. Vazirani.
An Introduction to Computational Learning Theory.
MIT Press, Cambridge, MA, USA, 1994.
ISBN 978-0-262-11193-5. [1]
[Kho02] Subhash Khot.
On the Power of Unique 2-Prover 1-Round Games.
In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, STOC '02, 767–775. ACM, 2002.
doi:10.1145/509907.510017. [1][2][3][4]
[Khr71a] V. M. Khrapchenko.
Complexity of the realization of a linear function in the class of $\Pi$-circuits.
Mathematical Notes of the Academy of Sciences of the USSR, 9:21–23, 1971.
Russian original: Matematicheskie Zametki 9(1), 35–40. [1][2][3][4]
[Khr71b] V. M. Khrapchenko.
Method of determining lower bounds for the complexity of $\Pi$-schemes.
Mathematical Notes of the Academy of Sciences of the USSR, 10:474–479, 1971.
Russian original: Matematicheskie Zametki 10(1), 83–92.
doi:10.1007/BF01747074. [1][2][3][4][5]
[KSTT92] Johannes Köbler, Uwe Schöning, Seinosuke Toda, Jacobo Torán.
Turing Machines with Few Accepting Computations and Low Sets for PP.
Journal of Computer and System Sciences, 44(2):272–286, 1992.
doi:10.1016/0022-0000(92)90022-B. [1][2][3][4][5][6][7][8]
[LLS75] Richard E. Ladner, Nancy A. Lynch, Alan L. Selman.
A comparison of polynomial time reducibilities.
Theoretical Computer Science, 1(2):103–123, 1975. [1][2][3][4][5][6][7][8][9][10][11][12]
[Lev73] Leonid A. Levin.
Universal Sequential Search Problems.
Problems of Information Transmission, 9(3):265–266, 1973. [1][2][3]
[Lev84] Leonid A. Levin.
Randomness Conservation Inequalities; Information and Independence in Mathematical Theories.
Information and Control, 61(1):15–37, 1984.
doi:10.1016/S0019-9958(84)80060-1. [1][2][3]
[LY22] Jiatu Li, Tianqi Yang.
$3.1n - o(n)$ Circuit Lower Bounds for Explicit Functions.
In Proceedings of the 54th Annual ACM Symposium on Theory of Computing, STOC 2022, 1180–1193. 2022.
doi:10.1145/3519935.3519976. [1][2]
[Li23] Xin Li.
Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More.
In Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2023, 1271–1281. 2023.
doi:10.1109/FOCS57990.2023.00075. [1][2][3][4]
[LY94] Richard J. Lipton, Neal E. Young.
Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory.
In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing (STOC 1994), 734–740. 1994.
doi:10.1145/195058.195447. [1][2]
[LP21] Yanyi Liu, Rafael Pass.
On the Possibility of Basing Cryptography on $\mathsf{EXP} \neq \mathsf{BPP}$.
In Advances in Cryptology – CRYPTO 2021, volume 12825 of Lecture Notes in Computer Science, 11–40. Springer, 2021.
Full version in Electronic Colloquium on Computational Complexity (ECCC), TR21-056; section, fact, and page numbers follow ECCC TR21-056.
doi:10.1007/978-3-030-84242-0_2. [1][2][3][4][5][6][7][8][9][10][11][12][13][14]
[LMS11] Daniel Lokshtanov, Dániel Marx, Saket Saurabh.
Lower bounds based on the Exponential Time Hypothesis.
Bulletin of the EATCS, 105:41–72, 2011. [1][2][3]
[LMS18] Daniel Lokshtanov, Dániel Marx, Saket Saurabh.
Slightly Superexponential Parameterized Problems.
SIAM Journal on Computing, 47(3):675–702, 2018.
doi:10.1137/16M1104834. [1][2]
[LW49] Lynn H. Loomis, Hassler Whitney.
An Inequality Related to the Isoperimetric Inequality.
Bulletin of the American Mathematical Society, 55(10):961–962, 1949.
doi:10.1090/S0002-9904-1949-09320-5. [1][2]
[LS88] László Lovász, Michael Saks.
Lattices, Möbius Functions and Communication Complexity.
In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, FOCS 1988, 81–90. 1988.
doi:10.1109/SFCS.1988.21924. [1][2][3]
[Lup65] O. B. Lupanov.
On an Approach to the Synthesis of Control Systems: the Principle of Local Coding.
Problemy Kibernetiki, 14:31–110, 1965.
In Russian. [1][2][3][4][5]
[Lyu09] Vadim Lyubashevsky.
Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures.
In Advances in Cryptology – ASIACRYPT 2009, volume 5912 of Lecture Notes in Computer Science, 598–616. Springer, 2009.
doi:10.1007/978-3-642-10366-7_35. [1][2][3][4][5][6]
[Lyu12] Vadim Lyubashevsky.
Lattice Signatures without Trapdoors.
In Advances in Cryptology – EUROCRYPT 2012, volume 7237 of Lecture Notes in Computer Science, 738–755. Springer, 2012.
doi:10.1007/978-3-642-29011-4_43. [1][2][3][4][5][6]
[McD89] Colin McDiarmid.
On the Method of Bounded Differences.
In J. Siemons, editor, Surveys in Combinatorics, 1989, volume 141 of London Mathematical Society Lecture Note Series, pages 148–188.
Cambridge University Press, 1989.
doi:10.1017/CBO9781107359949.008. [1][2][3]
[McKMW19] Dylan McKay, Cody D. Murray, R. Ryan Williams.
Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes.
In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019), 1215–1225. ACM, 2019.
doi:10.1145/3313276.3316396. [1][2]
[MS82] Kurt Mehlhorn, Erik M. Schmidt.
Las Vegas Is Better than Determinism in VLSI and Distributed Computing.
In Proceedings of the 14th Annual ACM Symposium on Theory of Computing, STOC 1982, 330–337. 1982.
doi:10.1145/800070.802208. [1][2][3]
[Mit77] Tom M. Mitchell.
Version Spaces: A Candidate Elimination Approach to Rule Learning.
In Proceedings of the 5th International Joint Conference on Artificial Intelligence, volume 1, 305–310. 1977.
[MT10] Robin A. Moser, Gábor Tardos.
A Constructive Proof of the General Lovász Local Lemma.
Journal of the ACM, 57(2):11:1–11:15, 2010.
doi:10.1145/1667053.1667060. [1][2]
[Mul54] David E. Muller.
Application of Boolean Algebra to Switching Circuit Design and to Error Detection.
Transactions of the I.R.E. Professional Group on Electronic Computers, EC-3(3):6–12, 1954.
doi:10.1109/IREPGELC.1954.6499441. [1][2]
[MVV87] Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani.
Matching Is as Easy as Matrix Inversion.
Combinatorica, 7(1):105–113, 1987.
doi:10.1007/BF02579206. [1][2][3]
[NN93] Joseph Naor, Moni Naor.
Small-Bias Probability Spaces: Efficient Constructions and Applications.
SIAM Journal on Computing, 22(4):838–856, 1993.
doi:10.1137/0222053. [1][2][3][4][5][6][7][8]
[Nec65] E. I. Nechiporuk.
On the Complexity of Gating Circuits Realizing Boolean Matrices with Undefined Elements.
Doklady Akademii Nauk SSSR, 163(1):40–42, 1965.
In Russian. [1][2]
[Nec66] E. I. Nechiporuk.
On a Boolean function.
Soviet Mathematics Doklady, 7(4):999–1000, 1966. [1][2][3][4]
[NZ96] Noam Nisan, David Zuckerman.
Randomness is Linear in Space.
Journal of Computer and System Sciences, 52(1):43–52, 1996.
doi:10.1006/jcss.1996.0004. [1][2]
[PZ82] Christos H. Papadimitriou, Stathis K. Zachos.
Two Remarks on the Power of Counting.
In Armin B. Cremers, Hans-Peter Kriegel, editors, Theoretical Computer Science: 6th GI-Conference, Dortmund, January 5–7, 1983, volume 145 of Lecture Notes in Computer Science, 269–275. Springer-Verlag, 1982.
Proceedings published in December 1982 for the January 1983 conference.
doi:10.1007/BFb0009651, URL: https://doi.org/10.1007/BFb0009651. [1][2][3][4][5][6][7]
[Raz85] Alexander A. Razborov.
Lower Bounds on the Monotone Complexity of Some Boolean Functions.
Soviet Mathematics Doklady, 31:354–357, 1985.
Russian original: Doklady Akademii Nauk SSSR 281(4), 798–801. [1][2][3][4][5]
[Raz89] Alexander A. Razborov.
On the Method of Approximations.
In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, 167–176. 1989. [1][2][3][4]
[Raz95] Alexander A. Razborov.
Bounded Arithmetic and Lower Bounds in Boolean Complexity.
In Feasible Mathematics II, volume 13 of Progress in Computer Science and Applied Logic, pages 344–386.
Birkhäuser, 1995.
doi:10.1007/978-1-4612-2566-9_12. [1][2][3][4]
[Ree54] Irving S. Reed.
A Class of Multiple-Error-Correcting Codes and the Decoding Scheme.
Transactions of the IRE Professional Group on Information Theory, 4(4):38–49, 1954.
doi:10.1109/TIT.1954.1057465. [1][2]
[RS60] Irving S. Reed, Gustave Solomon.
Polynomial Codes Over Certain Finite Fields.
Journal of the Society for Industrial and Applied Mathematics, 8(2):300–304, 1960.
doi:10.1137/0108018. [1][2]
[Rey02] John C. Reynolds.
Separation Logic: A Logic for Shared Mutable Data Structures.
In Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, 55–74. 2002.
doi:10.1109/LICS.2002.1029817. [1][2]
[Sch99] Uwe Schöning.
A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems.
In 40th Annual Symposium on Foundations of Computer Science (FOCS), 410–414. 1999.
doi:10.1109/SFFCS.1999.814612. [1][2]
[SS63] J. C. Shepherdson, H. E. Sturgis.
Computability of Recursive Functions.
Journal of the ACM, 10(2):217–255, 1963.
doi:10.1145/321160.321170. [1]
[She99] W. F. Sheppard.
On the Application of the Theory of Error to Cases of Normal Distribution and Normal Correlation.
Philosophical Transactions of the Royal Society of London. Series A, 192:101–167, 1899.
doi:10.1098/rsta.1899.0003. [1][2][3][4][5][6][7][8][9][10]
[Shi03] Yaoyun Shi.
Both Toffoli and Controlled-NOT Need Little Help to Universal Quantum Computing.
Quantum Information and Computation, 3(1):84–92, 2003.
Title as published; arXiv v2 is titled ``Both Toffoli and Controlled-NOT need little help to do universal quantum computation''.
doi:10.26421/QIC3.1-7, arXiv:quant-ph/0205115. [1][2][3]
[Sho69] L. A. Sholomov.
On the Realization of Incompletely Defined Boolean Functions by Circuits of Functional Elements.
Problemy Kibernetiki, 21:215–226, 1969.
In Russian. [1][2][3][4][5][6][7]
[Sim75] Janos Simon.
On Some Central Problems in Computational Complexity.
PhD thesis, Cornell University, 1975. [1][2][3][4]
[Spi71] Philip M. Spira.
On Time-Hardware Complexity Tradeoffs for Boolean Functions.
In Proceedings of the Fourth Hawaii International Symposium on System Sciences, 525–527. 1971. [1][2]
[SED+26] Shreyas Srinivas, Ethan Ermovick, Tanner Duve, Bashar Hamade, Johannes Tantow, Samuel Schlesinger.
Algolean: Algorithms and Complexity Library using the Lightweight Query Combinator Framework Called Prog.
2026.
Lean library, version 1.0.0.
URL: https://github.com/Shreyas4991/Algolean. [1][2][3]
[SHL65] Richard E. Stearns, Juris Hartmanis, II , Philip M. Lewis.
Hierarchies of Memory Limited Computations.
In Proceedings of the 6th Annual Symposium on Switching Circuit Theory and Logical Design, SWCT 1965, 179–190. 1965.
doi:10.1109/FOCS.1965.11. [1][2]
[Sto83] Larry J. Stockmeyer.
The Complexity of Approximate Counting.
In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 118–126. 1983. [1][2][3][4]
[SM73] Larry J. Stockmeyer, Albert R. Meyer.
Word Problems Requiring Exponential Time (Preliminary Report).
In Proceedings of the Fifth Annual ACM Symposium on Theory of Computing (STOC 1973), 1–9. 1973.
doi:10.1145/800125.804029. [1][2][3]
[Sub61] B. A. Subbotovskaya.
Realizations of Linear Functions by Formulas Using $\lor$, $\&$, $-$.
Soviet Mathematics Doklady, 2:110–112, 1961.
Russian original: Doklady Akademii Nauk SSSR 136(3), 553–555. [1][2][3]
[Sze87] Róbert Szelepcsényi.
The Method of Forcing for Nondeterministic Automata.
Bulletin of the European Association for Theoretical Computer Science, 33:96–100, 1987. [1][2][3][4][5][6][7]
[Tal17] Avishay Tal.
Tight Bounds on the Fourier Spectrum of AC$^0$.
In Ryan O'Donnell, editor, 32nd Computational Complexity Conference (CCC 2017), volume 79 of Leibniz International Proceedings in Informatics (LIPIcs), 15:1–15:31. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017.
doi:10.4230/LIPIcs.CCC.2017.15. [1][2][3]
[Tar89] Gábor Tardos.
Query complexity, or why is it difficult to separate NP$^A \cap$ coNP$^A$ from P$^A$ by random oracles A?
Combinatorica, 9(4):385–392, 1989. [1][2]
[Tch52] Pafnuty L. Tchebichef.
Mémoire sur les nombres premiers.
Journal de Mathématiques Pures et Appliquées, 17:366–390, 1852. [1][2]
[Tho90] Wolfgang Thomas.
Automata on Infinite Objects.
In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, pages 133–191.
Elsevier and MIT Press, 1990.
[Tur36] Alan M. Turing.
On Computable Numbers, with an Application to the Entscheidungsproblem.
Proceedings of the London Mathematical Society, s2-42(1):230–265, 1936.
doi:10.1112/plms/s2-42.1.230. [1][2]
[Val77] Leslie G. Valiant.
Graph-Theoretic Arguments in Low-Level Complexity.
In Mathematical Foundations of Computer Science 1977, volume 53 of Lecture Notes in Computer Science, 162–176. Springer, 1977.
doi:10.1007/3-540-08353-7_135. [1][2][3][4][5][6]
[Wag86] Klaus W. Wagner.
The Complexity of Combinatorial Problems with Succinct Input Representation.
Acta Informatica, 23(3):325–356, 1986.
doi:10.1007/BF00289117. [1][2]
[Yab54] S. V. Yablonskii.
Realization of a linear function in the class of $\pi$-schemes.
Doklady Akademii Nauk SSSR, 94(5):805–806, 1954.
In Russian. [1][2][3]
[Yao77] Andrew Chi-Chih Yao.
Probabilistic Computations: Toward a Unified Measure of Complexity.
In Proceedings of the 18th Annual Symposium on Foundations of Computer Science, FOCS 1977, 222–227. 1977.
doi:10.1109/SFCS.1977.24. [1][2][3][4][5][6][7][8][9][10]
[Zha23] Yufei Zhao.
Probabilistic Methods in Combinatorics.
Lecture notes, MIT 18.226, 2023. [1][2]