{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:14:34Z","timestamp":1725664474270},"publisher-location":"Berlin, Heidelberg","reference-count":93,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540587156"},{"type":"electronic","value":"9783540490548"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58715-2_130","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:41:19Z","timestamp":1330274479000},"page":"256-275","source":"Crossref","is-referenced-by-count":0,"title":["My favorite ten complexity theorems of the past decade"],"prefix":"10.1007","author":[{"given":"Lance","family":"Fortnow","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"issue":"1","key":"22_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"N. Alon","year":"1987","unstructured":"N. Alon and R. Boppana. The monotone complexity of Boolean functions. Combinatorica, 7(1): 1\u201322, 1987.","journal-title":"Combinatorica"},{"key":"22_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai. \u2211 1 1 -formulae on unite structures. Annals of Pure and Applied Logic, 24: 1\u201348, 1983.","journal-title":"Annals of Pure and Applied Logic"},{"key":"22_CR3","first-page":"218","volume-title":"Random walks, universal traversal sequences, and the complexity of maze problems","author":"R. Aleliunas","year":"1979","unstructured":"R. Aleliunas, R. Karp, R. Lipton, L. Lov\u00e1sz, and C. Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In Proceedings of the 20th IEEE Symposium on Foundations of Computer Science, pages 218\u2013223. IEEE, New York, 1979."},{"key":"22_CR4","first-page":"580","volume-title":"A note on the power of threshold circuits","author":"E. Allender","year":"1989","unstructured":"E. Allender. A note on the power of threshold circuits. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 580\u2013584. IEEE, New York, 1989."},{"key":"22_CR5","first-page":"14","volume-title":"Proof verification and hardness of approximation problems","author":"S. Arora","year":"1992","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pages 14\u201323. IEEE, New York, 1992."},{"key":"22_CR6","first-page":"2","volume-title":"Probabilistic checking of proofs: A new characterization of NP","author":"S. Arora","year":"1992","unstructured":"S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pages 2\u201313. IEEE, New York, 1992."},{"key":"22_CR7","first-page":"421","volume-title":"Trading group theory for randomness","author":"L. Babai","year":"1985","unstructured":"L. Babai. Trading group theory for randomness. In Proceedings of the 17th ACM Symposium on the Theory of Computing, pages 421\u2013429. ACM, New York, 1985."},{"issue":"1","key":"22_CR8","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D. Barrington","year":"1989","unstructured":"D. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. Journal of Computer and System Sciences, 38(1): 150\u2013164, 1989.","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"22_CR9","doi-asserted-by":"crossref","first-page":"1283","DOI":"10.1137\/0218084","volume":"18","author":"A. Borodin","year":"1989","unstructured":"A. Borodin, S. Cook, P. Dymond, L. Ruzzo, and M. Tompa. Erratum: Two applications of inductive counting for complementation problems. SIAM Journal on Computing, 18(6): 1283, 1989.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"22_CR10","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1137\/0218038","volume":"18","author":"A. Borodin","year":"1989","unstructured":"A. Borodin, S. Cook, P. Dymond, L. Ruzzo, and M. Tompa. Two applications of inductive counting for complementation problems. SIAM Journal on Computing, 18(3): 559\u2013578, 1989. See also Erratum [BCD+89a].","journal-title":"SIAM Journal on Computing"},{"key":"22_CR11","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0304-3975(92)90125-Y","volume":"104","author":"D. Bovet","year":"1992","unstructured":"D. Bovet, P. Crescenzi, and R. Silvestri. A uniform approach to define complexity classes. Theoretical Computer Science, 104: 263\u2013283, 1992.","journal-title":"Theoretical Computer Science"},{"key":"22_CR12","first-page":"14","volume-title":"Perceptrons, PP and the polynomial hierarchy","author":"R. Beigel","year":"1992","unstructured":"R. Beigel. Perceptrons, PP and the polynomial hierarchy. In Proceedings of the 7th IEEE Structure in Complexity Theory Conference, pages 14\u201319. IEEE, New York, 1992."},{"issue":"1","key":"22_CR13","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1(1): 3\u201340, 1991.","journal-title":"Computational Complexity"},{"key":"22_CR14","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(92)90084-S","volume":"103","author":"R. Beigel","year":"1992","unstructured":"R. Beigel and J. Gill. Counting classes: Thresholds, parity, mods, and fewness. Theoretical Computer Science, 103: 3\u201323, 1992.","journal-title":"Theoretical Computer Science"},{"key":"22_CR15","first-page":"113","volume-title":"Multi-prover interactive proofs: How to remove intractability assumptions","author":"M. Ben-Or","year":"1988","unstructured":"M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson. Multi-prover interactive proofs: How to remove intractability assumptions. In Proceedings of the 20th ACM Symposium on the Theory of Computing, pages 113\u2013131. ACM, New York, 1988."},{"key":"22_CR16","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"1","author":"L. Berman","year":"1977","unstructured":"L. Berman and J. Hartmanis. On isomorphism and density of NP and other complete sets. SIAM. Journal on Computing, 1: 305\u2013322, 1977.","journal-title":"SIAM. Journal on Computing"},{"issue":"2","key":"22_CR17","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R. Boppana","year":"1987","unstructured":"R. Boppana, J. H\u00e5stad, and S. Zachos. Does co-NP have short interactive proofs? Information Processing Letters, 25(2): 127\u2013132, 1987.","journal-title":"Information Processing Letters"},{"key":"22_CR18","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"M. Blum and S. Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing, 13: 850\u2013864, 1984.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"22_CR19","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"L. Babai and S. Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences, 36(2): 254\u2013276, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"R. Beigel, N. Reingold, and D. Spielman. PP is closed under intersection. Journal of Computer and System Sciences, 1994. To appear. Paper also appeared in Proceedings of 23rd STOC conference, 1991, pages 1\u20139.","DOI":"10.1145\/103418.103426"},{"key":"22_CR21","unstructured":"R. Beigel and J. Tarui. On ACC. In Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science, pages 783\u2013792. IEEE, 1991."},{"key":"22_CR22","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1142\/S0129054191000054","volume":"2","author":"J. Cai","year":"1991","unstructured":"J. Cai and M. Furst. PSPACE survives constant-width bottlenecks. International Journal of Foundations of Computer Science, 2: 67\u201376, 1991.","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"1","key":"22_CR23","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"A. Chandra, D. Kozen, and L. Stockmeyer. Alternation. Journal of the ACM, 28(1): 114\u2013133, 1981.","journal-title":"Journal of the ACM"},{"key":"22_CR24","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds. Paths, trees and flowers. Canadian Journal of Mathematics, 17: 449\u2013467, 1965.","journal-title":"Canadian Journal of Mathematics"},{"key":"22_CR25","unstructured":"Feldman. The optimum prover lives in PSPACE. Manuscript, 1986."},{"key":"22_CR26","first-page":"30","volume-title":"The isomorphism conjecture holds relative to an oracle","author":"S. Fenner","year":"1992","unstructured":"S. Fenner, L. Fortnow, and S. Kurtz. The isomorphism conjecture holds relative to an oracle. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pages 30\u201339. IEEE, New York, 1992."},{"issue":"1","key":"22_CR27","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1016\/S0022-0000(05)80024-8","volume":"48","author":"S. Fenner","year":"1994","unstructured":"S. Fenner, L. Fortnow, and S. Kurtz. Gap-definable counting classes. Journal of Computer and System Sciences, 48(1): 116\u2013148, 1994.","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR28","first-page":"733","volume-title":"Two-prover one-round proof systems: Their power and their problems","author":"U. Feige","year":"1992","unstructured":"U. Feige and L. Lov\u00e1sz. Two-prover one-round proof systems: Their power and their problems. In Proceedings of the 24th ACM Symposium on the Theory of Computing, pages 733\u2013744. ACM, New York, 1992."},{"key":"22_CR29","first-page":"13","volume-title":"PP is closed under truth-table reductions","author":"L. Fortnow","year":"1991","unstructured":"L. Fortnow and N. Reingold. PP is closed under truth-table reductions. In Proceedings of the 6th IEEE Structure in Complexity Theory Conference, pages 13\u201315. IEEE, New York, 1991."},{"key":"22_CR30","doi-asserted-by":"crossref","unstructured":"L. Fortnow, J. Rompel, and M. Sipser. On the power of multi-prover interactive protocols. Theoretical Computer Science A, 1994. To appear.","DOI":"10.1016\/0304-3975(94)90251-8"},{"key":"22_CR31","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(88)90199-8","volume":"28","author":"L. Fortnow","year":"1988","unstructured":"L. Fortnow and M. Sipser. Are there interactive protocols for co-NP languages? Information Processing Letters, 28: 249\u2013251, 1988.","journal-title":"Information Processing Letters"},{"key":"22_CR32","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. Saxe, and M. Sipser. Parity, circuits and the polynomial-time hierarchy. Mathematical Systems Theory, 17: 13\u201327, 1984.","journal-title":"Mathematical Systems Theory"},{"key":"22_CR33","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"J. Gill. Computational complexity of probabilistic complexity classes. SIAM Journal on Computing, 6: 675\u2013695, 1977.","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"22_CR34","doi-asserted-by":"crossref","first-page":"1163","DOI":"10.1137\/0222069","volume":"22","author":"O. Goldreich","year":"1993","unstructured":"O. Goldreich, H. Krawczyk, and M. Luby. On the existence of pseudorandom generators. SIAM Journal on Computing, 22(6): 1163\u20131175, December 1993.","journal-title":"SIAM Journal on Computing"},{"key":"22_CR35","first-page":"25","volume-title":"A hard-core predicate for all one-way functions","author":"O. Goldreich","year":"1989","unstructured":"O. Goldreich and L. Levin. A hard-core predicate for all one-way functions. In Proceedings of the 21st ACM Symposium on the Theory of Computing, pages 25\u201332. ACM, New York, 1989."},{"issue":"1","key":"22_CR36","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1989","unstructured":"S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems. SIAM Journal on Computing, 18(1): 186\u2013208, 1989.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"22_CR37","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1145\/116825.116852","volume":"38","author":"O. Goldreich","year":"1991","unstructured":"O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38(3): 691\u2013729, 1991.","journal-title":"Journal of the ACM"},{"key":"22_CR38","series-title":"volume 5 of Advances in Computing Research","first-page":"73","volume-title":"Randomness and Computation","author":"S. Goldwasser","year":"1989","unstructured":"S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. In S. Micali, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pages 73\u201390. JAI Press, Greenwich, 1989."},{"key":"22_CR39","series-title":"volume 5 of Advances in Computing Research","first-page":"143","volume-title":"Randomness and Computation","author":"J. H\u00e5stad","year":"1989","unstructured":"J. H\u00e5stad. Almost optimal lower bounds for small depth circuits. In S. Micali, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pages 143\u2013170. JAI Press, Greenwich, 1989."},{"key":"22_CR40","first-page":"395","volume-title":"Pseudo-random generators under uniform assumptions","author":"J. H\u00e5stad","year":"1990","unstructured":"J. H\u00e5stad. Pseudo-random generators under uniform assumptions. In Proceedings of the 22nd ACM Symposium on the Theory of Computing, pages 395\u2013404. ACM, New York, 1990."},{"key":"22_CR41","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0304-3975(90)90081-R","volume":"74","author":"U. Hertrampf","year":"1990","unstructured":"U. Hertrampf. Relations among MOD classes (note). Theoretical Computer Science, 74: 325\u2013328, 1990.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"22_CR42","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0304-3975(91)90323-T","volume":"81","author":"J. Hartmanis","year":"1991","unstructured":"J. Hartmanis and L. Hemachandra. One-way functions and the nonisomorphism of NP-complete sets. Theoretical Computer Science, 81(1): 155\u2013163, 1991.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"22_CR43","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1016\/S0022-0000(05)80006-6","volume":"48","author":"S. Homer","year":"1994","unstructured":"S. Homer and L. Longpr\u00e9. On reductions of NP sets to sparse sets. Journal of Computer and System Sciences, 48(2): 324\u2013336, 1994.","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR44","first-page":"200","volume-title":"On the power of polynomial time bit-reductions","author":"U. Hertrampf","year":"1993","unstructured":"U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer, and K. Wagner. On the power of polynomial time bit-reductions. In Proceedings of the 8th IEEE Structure in Complexity Theory Conference, pages 200\u2013207. IEEE, New York, 1993."},{"key":"22_CR45","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"J. Hartmanis and R. Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117: 285\u2013306, 1965.","journal-title":"Transactions of the American Mathematical Society"},{"key":"22_CR46","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"J. E. Hopcroft","year":"1979","unstructured":"J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, Mass., 1979."},{"key":"22_CR47","first-page":"12","volume-title":"Pseudo-random number generation from one-way functions","author":"R. Impagliazzo","year":"1989","unstructured":"R. Impagliazzo, L. Levin, and M. Luby. Pseudo-random number generation from one-way functions. In Proceedings of the 21st ACM Symposium on the Theory of Computing, pages 12\u201324. ACM, New York, 1989."},{"issue":"5","key":"22_CR48","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman. Nondeterministic space is closed under complementation. SIAM Journal on Computing, 17(5): 935\u2013938, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"22_CR49","first-page":"44","volume-title":"Limits on the provable consequences of oneway permutations","author":"R. Impagliazzo","year":"1989","unstructured":"R. Impagliazzo and S. Rudich. Limits on the provable consequences of oneway permutations. In Proceedings of the 21st ACM Symposium on the Theory of Computing, pages 44\u201361. ACM, New York, 1989."},{"key":"22_CR50","first-page":"491","volume-title":"Polynomial, universal traversing sequences for cycles are constructible","author":"S. Istrail","year":"1988","unstructured":"S. Istrail. Polynomial, universal traversing sequences for cycles are constructible. In Proceedings of the 20th ACM Symposium on the Theory of Computing, pages 491\u2013503. ACM, New York, 1988."},{"key":"22_CR51","first-page":"248","volume-title":"How to recycle random bits","author":"R. Impagliazzo","year":"1989","unstructured":"R. Impagliazzo and D. Zuckerman. How to recycle random bits. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 248\u2013253. IEEE, New York, 1989."},{"key":"22_CR52","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0304-3975(85)90140-9","volume":"39","author":"D. Joseph","year":"1985","unstructured":"D. Joseph and P. Young. Some remakrs on witness functions for poynomial reducibilities in NP. Theoretical Computer Science, 39: 225\u2013237, 1985.","journal-title":"Theoretical Computer Science"},{"key":"22_CR53","first-page":"191","volume":"28","author":"R. Karp","year":"1982","unstructured":"R. Karp and R. Lipton. Turing machines that take advice. L'Enseignement Mathematique, 28: 191\u2013209, 1982.","journal-title":"L'Enseignement Mathematique"},{"key":"22_CR54","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0304-3975(86)90152-0","volume":"47","author":"K. Ko","year":"1987","unstructured":"K. Ko, T. Long, and D. Du. A note on one-way functions and polynomial-time isomorphisms. Theoretical Computer Science, 47: 263\u2013276, 1987.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"22_CR55","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0022-0000(88)90007-4","volume":"37","author":"S. Kurtz","year":"1988","unstructured":"S. Kurtz, S. Mahaney, and J. Royer. Collapsing degrees. Journal of Computer and System Sciences, 37(2): 247\u2013268, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR56","first-page":"157","volume-title":"The isomorphism conjecture fails relative to a random oracle","author":"S. Kurtz","year":"1989","unstructured":"S. Kurtz, S. Mahaney, and J. Royer. The isomorphism conjecture fails relative to a random oracle. In Proceedings of the 21st ACM Symposium on the Theory of Computing, pages 157\u2013166. ACM, New York, 1989."},{"key":"22_CR57","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1137\/0403021","volume":"3","author":"M. Karchmer","year":"1990","unstructured":"M. Karchmer and A. Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics, 3: 255\u2013265, 1990.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"2","key":"22_CR58","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/S0019-9958(63)90169-4","volume":"6","author":"P. Landweber","year":"1963","unstructured":"P. Landweber. Three theorems on phase structure grammars of type 1. Information and Control, 6(2): 131\u2013136, 1963.","journal-title":"Information and Control"},{"key":"22_CR59","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/BF02579323","volume":"7","author":"L. Levin","year":"1987","unstructured":"L. Levin. One-way functions and pseudo-random generators. Combinatorica, 7: 357\u2013363, 1987.","journal-title":"Combinatorica"},{"issue":"4","key":"22_CR60","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C. Lund","year":"1992","unstructured":"C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4): 859\u2013868, 1992.","journal-title":"Journal of the ACM"},{"issue":"3","key":"22_CR61","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits, fourier transform, and learnability. Journal of the ACM, 40(3): 607\u2013620, 1993.","journal-title":"Journal of the ACM"},{"key":"22_CR62","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","volume":"25","author":"S. Mahaney","year":"1982","unstructured":"S. Mahaney. Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis. Journal of Computer and System Sciences, 25: 130\u2013143, 1982.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"22_CR63","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF01305237","volume":"12","author":"N. Nisan","year":"1992","unstructured":"N. Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4): 449\u2013461, 1992.","journal-title":"Combinatorica"},{"key":"22_CR64","first-page":"619","volume-title":"RL is contained in SC","author":"N. Nisan","year":"1992","unstructured":"N. Nisan. RL is contained in SC. In Proceedings of the 24th ACM Symposium on the Theory of Computing, pages 619\u2013623. ACM, New York, 1992."},{"key":"22_CR65","first-page":"24","volume-title":"Undirected connectivity in O(log1.5 n) space","author":"N. Nisan","year":"1992","unstructured":"N. Nisan, E. Szemer\u00e9di, and A. Wigderson. Undirected connectivity in O(log1.5 n) space. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pages 24\u201329. IEEE, New York, 1992."},{"key":"22_CR66","first-page":"235","volume-title":"More deterministic simulation in logspace","author":"N. Nisan","year":"1993","unstructured":"N. Nisan and D. Zuckerman. More deterministic simulation in logspace. In Proceedings of the 25th ACM Symposium on the Theory of Computing, pages 235\u2013244. ACM, New York, 1993."},{"issue":"3","key":"22_CR67","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1137\/0220030","volume":"20","author":"M. Ogiwara","year":"1991","unstructured":"M. Ogiwara and O. Watanabe. On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing, 20(3): 471\u2013483, 1991.","journal-title":"SIAM Journal on Computing"},{"key":"22_CR68","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43: 425\u2013440, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR69","series-title":"volume 145 of Lecture Notes in Computer Science","first-page":"269","volume-title":"Two remarks on the power of counting","author":"C. Papadimitriou","year":"1983","unstructured":"C. Papadimitriou and S. Zachos. Two remarks on the power of counting. In Proceedings of the 6th GI Conference on Theoretical Computer Science, volume 145 of Lecture Notes in Computer Science, pages 269\u2013276. Springer, Berlin, 1983."},{"key":"22_CR70","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/BF01157687","volume":"37","author":"A. Razborov","year":"1985","unstructured":"A. Razborov. Lower bounds of monotone complexity of the logical permanent function. Mathematical Notes of the Academy of Sciences of the USSR, 37: 485\u2013493, 1985.","journal-title":"Mathematical Notes of the Academy of Sciences of the USSR"},{"issue":"4","key":"22_CR71","first-page":"798","volume":"281","author":"A. Razborov","year":"1985","unstructured":"A. Razborov. Lower bounds on the monotone complexity of some boolean functions. Dokl. Akad. Nauk SSSR, 281(4): 798\u2013801, 1985. In Russian. English Translation in [Raz85c].","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"22_CR72","first-page":"485","volume":"31","author":"A. Razborov","year":"1985","unstructured":"A. Razborov. Lower bounds on the monotone complexity of some boolean functions. Soviet Math. dokl., 31: 485\u2013493, 1985.","journal-title":"Soviet Math. dokl."},{"issue":"4","key":"22_CR73","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF01137685","volume":"41","author":"A. Razborov","year":"1987","unstructured":"A. Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4): 333\u2013338, 1987.","journal-title":"Mathematical Notes of the Academy of Sciences of the USSR"},{"key":"22_CR74","first-page":"167","volume-title":"On the method of approximations","author":"A. Razborov","year":"1989","unstructured":"A. Razborov. On the method of approximations. In Proceedings of the 21st ACM Symposium on the Theory of Computing, pages 167\u2013176. ACM, New York, 1989."},{"issue":"1","key":"22_CR75","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02122698","volume":"10","author":"A. Razborov","year":"1990","unstructured":"A. Razborov. Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica, 10(1): 81\u201393, 1990.","journal-title":"Combinatorica"},{"key":"22_CR76","doi-asserted-by":"crossref","unstructured":"A. Razborov. Bounded Arithmetic and lower bounds in Boolean complexity. Feasible Mathematics II, 1994. To appear.","DOI":"10.1007\/978-1-4612-2566-9_12"},{"key":"22_CR77","first-page":"204","volume-title":"Natural proofs","author":"A. Razborov","year":"1994","unstructured":"A. Razborov and S. Rudich. Natural proofs. In Proceedings of the 26th ACM Symposium on the Theory of Computing, pages 204\u2013213. ACM, New York, 1994."},{"issue":"3","key":"22_CR78","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1145\/146637.146684","volume":"39","author":"R. Raz","year":"1992","unstructured":"R. Raz and A. Wigderson. Monotone circuits for matching require linear depth. Journal of the ACM, 39(3): 736\u2013744, 1992.","journal-title":"Journal of the ACM"},{"key":"22_CR79","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. Savitch","year":"1970","unstructured":"W., Savitch. Relationship between nondeterministic and deterministic tape classes. Journal of Computer and System Sciences, 4: 177\u2013192, 1970.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"22_CR80","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A. Shamir","year":"1992","unstructured":"A. Shamir. IP = PSPACE. Journal of the ACM, 39(4): 869\u2013877, 1992.","journal-title":"Journal of the ACM"},{"key":"22_CR81","first-page":"77","volume-title":"Algebraic methods in the theory of lower bounds for Boolean circuit complexity","author":"R. Smolensky","year":"1987","unstructured":"R. Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the 19th ACM Symposium on the Theory of Computing, pages 77\u201382. ACM, New York, 1987."},{"key":"22_CR82","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"R. Szelepcs\u00e9nyi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26: 279\u2013284, 1988.","journal-title":"Acta Informatica"},{"key":"22_CR83","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF02122563","volume":"8","author":"\u00c9. Tardos","year":"1988","unstructured":"\u00c9. Tardos. The gap between monotone and nonmonotone circuit complexity is exponential. Combinatorica, 8: 141\u2013142, 1988.","journal-title":"Combinatorica"},{"key":"22_CR84","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0304-3975(93)90214-E","volume":"113","author":"J. Tarui","year":"1993","unstructured":"J. Tarui. Probabilistic polynomials, AC0 functions and the polynomialtime hierarchy. Theoretical Computer Science A, 113: 167\u2013183, 1993.","journal-title":"Theoretical Computer Science A"},{"issue":"2","key":"22_CR85","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1137\/0221023","volume":"21","author":"S. Toda","year":"1992","unstructured":"S. Toda and M. Ogiwara. Counting classes are at least as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 21(2): 316\u2013328, 1992.","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"22_CR86","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5): 865\u2013877, 1991.","journal-title":"SIAM Journal on Computing"},{"key":"22_CR87","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"L. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8: 189\u2013201, 1979.","journal-title":"Theoretical Computer Science"},{"key":"22_CR88","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L. Valiant","year":"1979","unstructured":"L. Valiant. The complexity of reliability and enumeration problems. SIAM Journal on Computing, 8: 410\u2013421, 1979.","journal-title":"SIAM Journal on Computing"},{"key":"22_CR89","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L. Valiant","year":"1986","unstructured":"L. Valiant and V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47: 85\u201393, 1986.","journal-title":"Theoretical Computer Science"},{"key":"22_CR90","first-page":"80","volume-title":"Theory and applications of trapdoor functions","author":"A. Yao","year":"1982","unstructured":"A. Yao. Theory and applications of trapdoor functions. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, pages 80\u201391. IEEE, New York, 1982."},{"key":"22_CR91","first-page":"420","volume-title":"Lower bounds by probabilistic arguments","author":"A. Yao","year":"1983","unstructured":"A. Yao. Lower bounds by probabilistic arguments. In Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, pages 420\u2013428. IEEE, New York, 1983."},{"key":"22_CR92","first-page":"1","volume-title":"Separating the polynomial-time hierarchy by oracles","author":"A. Yao","year":"1985","unstructured":"A. Yao. Separating the polynomial-time hierarchy by oracles. In Proceedings of the 26th IEEE Symposium on Foundations of Computer Science, pages 1\u201310. IEEE, New York, 1985."},{"key":"22_CR93","first-page":"619","volume-title":"On ACC and threshold circuits","author":"A. Yao","year":"1990","unstructured":"A. Yao. On ACC and threshold circuits. In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, pages 619\u2013631. IEEE, New York, 1990."}],"container-title":["Lecture Notes in Computer Science","Foundation of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58715-2_130.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:23:44Z","timestamp":1605648224000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58715-2_130"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540587156","9783540490548"],"references-count":93,"URL":"https:\/\/doi.org\/10.1007\/3-540-58715-2_130","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}