[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]
[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]
[BN98] Franz Baader, Tobias Nipkow.
Term rewriting and all that.
Cambridge University Press, USA, 1998.
ISBN 0521455200. [1]
[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]
[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]
[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]
[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]
[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]
[CG88] Benny Chor, Oded Goldreich.
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity.
SIAM Journal on Computing, 17(2):230–261, 1988.
doi:10.1137/0217015. [1][2][3][4][5][6]
[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]
[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]
[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]
[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]
[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]
[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.
[Gol06] Oded Goldreich.
On Promise Problems: A Survey.
In Theoretical Computer Science: Essays in Memory of Shimon Even, volume 3895 of Lecture Notes in Computer Science, pages 254–290.
Springer, 2006.
doi:10.1007/11685654_12. [1][2][3][4][5][6][7]
[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]
[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]
[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]
[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.
[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]
[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]
[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]
[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]
[LN97] Rudolf Lidl, Harald Niederreiter.
Finite Fields.
Second edition.
Volume 20 of Encyclopedia of Mathematics and its Applications.
Cambridge University Press, 1997.
doi:10.1017/CBO9780511525926. [1][2][3][4][5][6]
[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]
[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]
[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]
[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]
[MWS77] F. J. MacWilliams, N. J. A. Sloane.
The Theory of Error-Correcting Codes.
Volume 16 of North-Holland Mathematical Library.
North-Holland, 1977. [1][2][3][4][5][6][7][8][9][10][11]
[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]
[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.
[Mit97] Tom M. Mitchell.
Machine Learning.
McGraw-Hill, 1997.
ISBN 0070428077.
[MU17] Michael Mitzenmacher, Eli Upfal.
Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis.
Second edition.
Cambridge University Press, 2017. [1][2][3][4][5][6]
[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]
[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]
[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]
[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]
[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]
[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]
[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]
[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]
[Yao82] Andrew C. Yao.
Theory and Application of Trapdoor Functions.
In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, FOCS 1982, 80–91. 1982.
doi:10.1109/SFCS.1982.45. [1][2][3][4][5]
[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]