{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T07:40:11Z","timestamp":1736235611726,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":99,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540304951"},{"type":"electronic","value":"9783540324195"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11590156_2","type":"book-chapter","created":{"date-parts":[[2005,12,5]],"date-time":"2005-12-05T15:43:16Z","timestamp":1133797396000},"page":"19-47","source":"Crossref","is-referenced-by-count":0,"title":["Computational Complexity Since 1980"],"prefix":"10.1007","author":[{"given":"Russell","family":"Impagliazzo","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"Adleman, L.: Two Theorems on Random Polynomial Time. In: FOCS, pp. 75\u201383 (1978)","DOI":"10.1109\/SFCS.1978.37"},{"issue":"1","key":"2_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF02122692","volume":"10","author":"W. Aiello","year":"1990","unstructured":"Aiello, W., Goldwasser, S., Hstad, J.: On the power of interaction. Combinatorica\u00a010(1), 3\u201325 (1990)","journal-title":"Combinatorica"},{"issue":"2","key":"2_CR3","doi-asserted-by":"publisher","first-page":"781","DOI":"10.4007\/annals.2004.160.781","volume":"160","author":"M. Agrawal","year":"2004","unstructured":"Agrawal, M., Kayal, N., Saxena, N.: Primes is in P. Annals of Mathematics\u00a0160(2), 781\u2013793 (2004)","journal-title":"Annals of Mathematics"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: \u03a31,1 formulas on finite structures. Annals of Pure and Applied Logic (1983)","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Komlos, J., Szemeredi, E.: Deterministic Simulation in LOGSPACE. In: 19th STOC, pp. 132\u2013140 (1987)","DOI":"10.1145\/28395.28410"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Akavia, A., Goldwasser, S., Safra, S.: Proving Hard-core Predicates Using List Decoding. In: FOCS, pp. 146\u2013156 (2003)","DOI":"10.1109\/SFCS.2003.1238189"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Aleliunas, R., Karp, R., Lipton, R., Lovasz, L., Rackoff, C.: Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems. In: 20th FOCS, pp. 218\u2013223 (1979)","DOI":"10.1109\/SFCS.1979.34"},{"issue":"1","key":"2_CR8","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1145\/273865.273933","volume":"45","author":"A.E. Andreev","year":"1998","unstructured":"Andreev, A.E., Clementi, A.E.F., Rolim, J.D.P.: A new general derandomization method. Journal of the Association for Computing Machinery\u00a045(1), 179\u2013213 (1998), (preliminary version in ICALP 1996)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Andreev, A., Clementi, A., Rolim, J., Trevisan, L.: Weak random sources, hitting sets, and BPP simulation. In: 38th FOCS, pp. 264\u2013272 (1997)","DOI":"10.1109\/SFCS.1997.646115"},{"key":"2_CR10","unstructured":"Arora, S., Lund, C.: Hardness of Approximations. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-hard Problems, PWS Publishing (1996)"},{"issue":"3","key":"2_CR11","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. Journal of the Association for Computing Machinery\u00a045(3), 501\u2013555 (1998)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Arora, S., Sudan, M.: Improved low-degree testing and its applications. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 485\u2013495 (1997)","DOI":"10.1145\/258533.258642"},{"issue":"1","key":"2_CR13","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: A new characterization of NP. Journal of the Association for Computing Machinery\u00a045 (1), 70\u2013122 (1998) (preliminary version in FOCS 1992)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking Computations in Polylogarithmic Time 23rd STOC, pp. 21-31 (1991)","DOI":"10.1145\/103418.103428"},{"key":"2_CR15","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity\u00a01, 3\u201340 (1991)","journal-title":"Computational Complexity"},{"key":"2_CR16","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"Babai, L., Fortnow, L., Nisan, N., Wigderson, A.: BPP has subexponential time simulations unless EXPTIME has publishable proofs. Complexity\u00a03, 307\u2013318 (1993)","journal-title":"Complexity"},{"issue":"2","key":"2_CR17","first-page":"254","volume":"36","author":"L. Babai","year":"1988","unstructured":"Babai, L., Moran, S.: Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class. JCSS\u00a036 (2), 254\u2013276 (1988)","journal-title":"JCSS"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Barak, B., Impagliazzo, R., Wigderson, A.: Extracting Randomness Using Few Independent Sources. In: 45th FOCS, pp. 384\u2013393 (2004)","DOI":"10.1109\/FOCS.2004.29"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Barak, B., Kindler, G., Shaltiel, R., Sudakov, B., Wigderson, A.: Simulating independence: new constructions of condesnsors, ramsey graphs, dispersers and extractors. In: 37th STOC, pp. 1\u201310 (2005)","DOI":"10.1145\/1060590.1060592"},{"key":"2_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-52282-4_30","volume-title":"STACS 90","author":"D. Beaver","year":"1990","unstructured":"Beaver, D., Feigenbaum, J.: Hiding instances in multioracle queries. In: Choffrut, C., Lengauer, T. (eds.) STACS 1990. LNCS, vol.\u00a0415, pp. 37\u201348. Springer, Heidelberg (1990)"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Kilian, J., Wigderson, A.: Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions. In: STOC, pp. 113\u2013131 (1988)","DOI":"10.1145\/62212.62223"},{"key":"2_CR22","unstructured":"Berlekamp, E.R.: Proc. of the 3rd Southeastern Conference on Combinatorics. In: Proc. of the 3rd Southeastern Conference on Combinatorics, GRAPH THEORY AND COMPUTING, pp. 1\u20137 (1972)"},{"issue":"2","key":"2_CR23","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF02579167","volume":"6","author":"M. Blum","year":"1986","unstructured":"Blum, M.: Independent Unbiased Coin Flips From a Correlated Biased Source: a Finite State Markov. Combinatorica\u00a06(2), 97\u2013108 (1986); Chain FOCS, 425-433 (1984)","journal-title":"Combinatorica"},{"key":"2_CR24","doi-asserted-by":"crossref","unstructured":"Blum, M., Kannan, S.: Designing Programs That Check Their Work. In: STOC, pp. 86\u201397 (1989)","DOI":"10.1145\/73007.73015"},{"issue":"3","key":"2_CR25","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M. Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-Testing\/Correcting with Applications to Numerical Problems. J. Comput. Syst. Sci.\u00a047(3), 549\u2013595 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR26","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"Blum, M., Micali, S.: How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits. SIAM J. Comput.\u00a013, 850\u2013864 (1984)","journal-title":"SIAM J. Comput."},{"key":"2_CR27","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s00039-004-0451-1","volume":"14","author":"J. Bourgain","year":"2004","unstructured":"Bourgain, J., Katz, N., Tao, T.: A sum-product estimate in finite fields, and applications. Geometric and Functional Analysis\u00a014, 27\u201357 (2004)","journal-title":"Geometric and Functional Analysis"},{"issue":"6","key":"2_CR28","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"IT-22","author":"W. Diffie","year":"1976","unstructured":"Diffie, W., Hellman, M.: New Directions in Cryptography. IEEE Transaction on Information Theory\u00a0IT-22 (6), 644\u2013654 (1976)","journal-title":"IEEE Transaction on Information Theory"},{"key":"2_CR29","doi-asserted-by":"crossref","unstructured":"Chor, B., Goldreich, O., Hstad, J., Friedman, J., Rudich, S., Smolensky, R.: The Bit Extraction Problem of t-Resilient Functions. In: FOCS, pp. 396\u2013407 (1985)","DOI":"10.1109\/SFCS.1985.55"},{"key":"2_CR30","unstructured":"Cook, S.: An Overview of Computational Complexity. Communications of the ACM\u00a026(3), 401\u2013407"},{"key":"2_CR31","doi-asserted-by":"crossref","unstructured":"Dinur, I.: The PCP Theorem by gap amplification. ECCC tech. report TR05-046 (2005)","DOI":"10.1145\/1132516.1132553"},{"key":"2_CR32","doi-asserted-by":"crossref","unstructured":"Feige, U., Goldwasser, S., Lovasz, L., Safra, S., Szegedy, M.: Approximating Clique is Almost NP-complete. In: FOCS, pp. 2\u201312 (1991)","DOI":"10.1109\/SFCS.1991.185341"},{"key":"2_CR33","doi-asserted-by":"crossref","unstructured":"Fortnow, L.: Comparing notions of full derandomization. In: Proceedings of the Sixteenth Annual IEEE Conference on Computational Complexity, pp. 28\u201334 (2001)","DOI":"10.1109\/CCC.2001.933869"},{"issue":"1","key":"2_CR34","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"Furst, M., Saxe, J.B., Sipser, M.: Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory\u00a017(1), 13\u201327 (1984)","journal-title":"Mathematical Systems Theory"},{"issue":"3","key":"2_CR35","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"O. Gabber","year":"1981","unstructured":"Gabber, O., Galil, Z.: Explicit Constructions of Linear-Sized Superconcentrators. J. Comput. Syst. Sci.\u00a022(3), 407\u2013420 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR36","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"Gill, J.: Computational complexity of proabilistic Turing machines. SIAM J. Comput.\u00a06, 675\u2013695 (1977)","journal-title":"SIAM J. Comput."},{"key":"2_CR37","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Levin, L.A.: A Hard-Core Predicate for all One-Way Functions. In: ACM Symp. on Theory of Computing, pp. 25\u201332 (1989)","DOI":"10.1145\/73007.73010"},{"issue":"4","key":"2_CR38","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O. Goldreich","year":"1986","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM\u00a033(4), 792\u2013807 (1986)","journal-title":"J. ACM"},{"key":"2_CR39","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Sipser, M.: Private Coins versus Public Coins in Interactive Proof Systems. In: STOC, pp. 59\u201368 (1986)","DOI":"10.1145\/12130.12137"},{"issue":"1","key":"2_CR40","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1989","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge Complexity of Interactive Proof Systems. SIAM J. Comput.\u00a018(1), 186\u2013208 (1989)","journal-title":"SIAM J. Comput."},{"key":"2_CR41","doi-asserted-by":"crossref","unstructured":"Hstad, J.: Almost Optimal Lower Bounds for Small Depth Circuits. In: STOC, pp. 6\u201320 (1986)","DOI":"10.1145\/12130.12132"},{"issue":"4","key":"2_CR42","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J. Hstad","year":"1999","unstructured":"Hstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A Pseudorandom Generator from any One-way Function. SIAM J. Comput.\u00a028(4), 1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"key":"2_CR43","doi-asserted-by":"crossref","unstructured":"Heintz, J., Schnorr, C.-P.: Testing Polynomials which Are Easy to Compute. In: STOC, pp. 262\u2013272 (1980)","DOI":"10.1145\/800141.804674"},{"key":"2_CR44","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R.: Hard-core Distributions for Somewhat Hard Problems. In: 36th FOCS, pp. 538\u2013545 (1995)","DOI":"10.1109\/SFCS.1995.492584"},{"key":"2_CR45","unstructured":"Impagliazzo, R.: Hardness as randomness: a survey of universal derandomization. CoRR cs.CC\/0304040 (2003)"},{"key":"2_CR46","unstructured":"Impagliazzo, R., Kabanets, V., Wigderson, A.: In search of an easy witness: Exponential time vs. probabilistic polynomial time. In: Proceedings of the Sixteenth Annual IEEE Conference on Computational Complexity, pp. 1\u201311 (2001)"},{"key":"2_CR47","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Rudich, S.: Limits on the Provable Consequences of One-Way Permutations. In: STOC, pp. 44\u201361 (1989)","DOI":"10.1145\/73007.73012"},{"key":"2_CR48","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"key":"2_CR49","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: Randomness vs. time: Derandomization under a uniform assumption. In: Proceedings of the Thirty-Ninth Annual IEEE Symposium on Foundations of Computer Science, pp. 734\u2013743 (1998)","DOI":"10.1109\/SFCS.1998.743524"},{"key":"2_CR50","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1016\/0196-6774(84)90022-1","volume":"5","author":"D. Johnson","year":"1984","unstructured":"Johnson, D.: The NP-completeness column: An ongoing guide (12th article) Journal of Algorithms\u00a05, 433\u2013447 (1984)","journal-title":"(12th article) Journal of Algorithms"},{"issue":"2","key":"2_CR51","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jcss.2001.1763","volume":"63","author":"V. Kabanets","year":"2001","unstructured":"Kabanets, V.: Easiness assumptions and hardness tests: Trading time for zero error. Journal of Computer and System Sciences\u00a063(2), 236\u2013252 (2001) (preliminary version in CCC 2000)","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR52","first-page":"88","volume":"76","author":"V. Kabanets","year":"2002","unstructured":"Kabanets, V.: Derandomization: A brief overview. Bulletin of the European Association for Theoretical Computer Science\u00a076, 88\u2013103 (2002) (also available as ECCC TR02-008)","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"issue":"1-2","key":"2_CR53","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"V. Kabanets","year":"2004","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Computational Complexity\u00a013(1-2), 1\u201346 (2004)","journal-title":"Computational Complexity"},{"key":"2_CR54","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/BFb0023837","volume-title":"LATIN \u201992","author":"E. Kaltofen","year":"1992","unstructured":"Kaltofen, E.: Polynomial factorization 1987\u20131991. In: Simon, I. (ed.) LATIN 1992. LNCS, vol.\u00a0583, pp. 294\u2013313. Springer, Heidelberg (1992)"},{"issue":"2","key":"2_CR55","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1145\/5657.5658","volume":"29","author":"R.M. Karp","year":"1986","unstructured":"Karp, R.M.: Combinatorics, Complexity, and Randomness. Commun. ACM\u00a029(2), 97\u2013109 (1986)","journal-title":"Commun. ACM"},{"key":"2_CR56","first-page":"191","volume":"28","author":"R.M. Karp","year":"1982","unstructured":"Karp, R.M., Lipton, R.J.: Turing Machines that Take Advice. L\u2019Ensignment Mathematique\u00a028, 191\u2013209 (1982)","journal-title":"L\u2019Ensignment Mathematique"},{"key":"2_CR57","unstructured":"Karp, R.M., Pippenger, N., Sipser, M.: A time randomness tradeoff AMS. In: Conference on Probabilistic Computational Complexity (1985)"},{"key":"2_CR58","unstructured":"Konyagin, S.: A sum-product estimate in fields of prime order Arxiv technical report 0304217 (2003)"},{"issue":"4","key":"2_CR59","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/BF02579323","volume":"7","author":"L.A. Levin","year":"1987","unstructured":"Levin, L.A.: One-Way Functions and Pseudorandom Generators. Combinatorica\u00a07(4), 357\u2013363 (1987)","journal-title":"Combinatorica"},{"issue":"1","key":"2_CR60","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L.A. Levin","year":"1986","unstructured":"Levin, L.A.: Average Case Complete Problems. SIAM J. Comput.\u00a015(1), 285\u2013286 (1986)","journal-title":"SIAM J. Comput."},{"key":"2_CR61","unstructured":"New directions in testing. Distributed Computing and Cryptography (1991)"},{"issue":"2","key":"2_CR62","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/0217022","volume":"17","author":"M. Luby","year":"1988","unstructured":"Luby, M., Rackoff, C.: How to Construct Pseudorandom Permutations from Pseudorandom Functions. SIAM J. Comput.\u00a017(2), 373\u2013386 (1988)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"2_CR63","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C. Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H., Nisan, N.: Algebraic methods for interactive proof systems. Journal of the Association for Computing Machinery\u00a039(4), 859\u2013868 (1992)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"2_CR64","doi-asserted-by":"crossref","unstructured":"Lipton, R.: New directions in testing. In: Feigenbaum, J., Merrit, M. (eds.) Distributed Computing and Cryptography. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a02, pp. 191\u2013202. AMS, Providence(1991)","DOI":"10.1090\/dimacs\/002\/13"},{"key":"2_CR65","volume-title":"Perceptrons: An Introduction to Computational Geometry","author":"M. Minsky","year":"1969","unstructured":"Minsky, M., Pappert, S.: Perceptrons: An Introduction to Computational Geometry. MIT Press, Cambridge (1969), (expanded edition, 1988)"},{"key":"2_CR66","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Wigderson, A.: Hardness vs. randomness. Journal of Computer and System Sciences\u00a049, 149\u2013167 (1994)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"2_CR67","first-page":"43","volume":"52","author":"N. Nisan","year":"1996","unstructured":"Nisan, N., Zuckerman, D.: Randomness is Linear in Space. JCSS\u00a052(1), 43\u201352 (1996)","journal-title":"JCSS"},{"key":"2_CR68","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"2_CR69","volume-title":"STOC 1988, Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, Approximation, and Complexity Classes. In: STOC 1988, Computational Complexity, Addison-Wesley, Reading (1994)"},{"key":"2_CR70","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/0022-314X(80)90084-0","volume":"12","author":"M.O. Rabin","year":"1980","unstructured":"Rabin, M.O.: Probabilistic Algorithm for Testing Primality. Journal of Number Theory\u00a012, 128\u2013138 (1980)","journal-title":"Journal of Number Theory"},{"issue":"4","key":"2_CR71","first-page":"798","volume":"281","author":"A.A. Razborov","year":"1985","unstructured":"Razborov, A.A.: Lower bounds for the monotone complexity of some Boolean functions. Doklady Akademii Nauk SSSR\u00a0281(4), 798\u2013801 (1985), English translation in Soviet Math. Doklady\u00a031, 354-357 (1985)","journal-title":"Doklady Akademii Nauk SSSR"},{"issue":"4","key":"2_CR72","first-page":"598","volume":"41","author":"A.A. Razborov","year":"1987","unstructured":"Razborov, A.A.: Lower bounds on the size of bounded-depth networks over a complete basis with logical addition. Mathematicheskie Zemetki\u00a041(4), 598\u2013607 (1987), English translation in Notes of the Academy of Sci. of the USSR \u00a041(4)333-338 (1987)","journal-title":"Mathematicheskie Zemetki"},{"key":"2_CR73","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"A.A. Razborov","year":"1997","unstructured":"Razborov, A.A., Rudich, S.: Natural proofs. Journal of Computer and System Sciences\u00a055, 24\u201335 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR74","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/sapm194221183","volume":"21","author":"J. Riordan","year":"1942","unstructured":"Riordan, J., Shannon, C.: The Number of Two-Terminal Series-Parallel Networks. Journal of Mathematics and Physics\u00a021, 83\u201393 (1942)","journal-title":"Journal of Mathematics and Physics"},{"issue":"2","key":"2_CR75","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"R. Rivest","year":"1978","unstructured":"Rivest, R., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM\u00a021(2), 120\u2013126 (1978)","journal-title":"Communications of the ACM"},{"key":"2_CR76","series-title":"Lecture Notes in Computer Science","first-page":"242","volume-title":"Advances in Cryptology - CRYPTO \u201991","author":"S. Rudich","year":"1991","unstructured":"Rudich, S.: The Use of Interaction in Public Cryptosystems. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol.\u00a0576, pp. 242\u2013251. Springer, Heidelberg (1991)"},{"key":"2_CR77","doi-asserted-by":"crossref","unstructured":"Santha, M., Vazirani, U.V.: Generating Quasi-Random Sequences from Slightly Random Sources. In: 25th FOCS, pp. 434\u2013440 (1984)","DOI":"10.1109\/SFCS.1984.715945"},{"issue":"4","key":"2_CR78","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. Journal of the Association for Computing Machinery\u00a027(4), 701\u2013717 (1980)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"2_CR79","doi-asserted-by":"crossref","unstructured":"Shaltiel, R., Umans, C.: Simple extractors for all min-entropies and a new pseudo-random generator. In: Proceedings of the Forty-Second Annual IEEE Symposium on Foundations of Computer Science, pp. 648\u2013657 (2001)","DOI":"10.1109\/SFCS.2001.959941"},{"issue":"4","key":"2_CR80","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A. Shamir","year":"1992","unstructured":"Shamir, A.: IP=PSPACE. Journal of the Association for Computing Machinery\u00a039(4), 869\u2013877 (1992)","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"3","key":"2_CR81","first-page":"379","volume":"36","author":"M. Sipser","year":"1988","unstructured":"Sipser, M.: Extractors, Randomness, or Time versus Space. JCSS\u00a036(3), 379\u2013383 (1988)","journal-title":"JCSS"},{"key":"2_CR82","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In: STOC, pp. 77\u201382 (1987)","DOI":"10.1145\/28395.28404"},{"issue":"1","key":"2_CR83","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1137\/0206006","volume":"6","author":"R. Solovay","year":"1979","unstructured":"Solovay, R., Strassen, V.: A fast Monte Carlo test for primality. SIAM Journal on Computing\u00a06(1), 84\u201385 (1979)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"2_CR84","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jcss.2000.1730","volume":"62","author":"M. Sudan","year":"2001","unstructured":"Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the XOR lemma. Journal of Computer and System Sciences\u00a062 (2), 236\u2013266 (2001) (preliminary version in STOC 1999)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"2_CR85","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jcom.1997.0439","volume":"13","author":"M. Sudan","year":"1997","unstructured":"Sudan, M.: Decoding of Reed Solomon codes beyond the error-correction bound. Journal of Complexity\u00a013(1), 180\u2013193 (1997)","journal-title":"Journal of Complexity"},{"issue":"1","key":"2_CR86","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF02122563","volume":"8","author":"\u00c9. Tardos","year":"1988","unstructured":"Tardos, \u00c9.: The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica\u00a08(1), 141\u2013142 (1988)","journal-title":"Combinatorica"},{"key":"2_CR87","doi-asserted-by":"crossref","unstructured":"Toda, S.: On the computational power of PP and \u2295P. In: 30th FOCS, pp. 514\u2013519 (1989)","DOI":"10.1109\/SFCS.1989.63527"},{"issue":"4","key":"2_CR88","doi-asserted-by":"crossref","first-page":"860","DOI":"10.1145\/502090.502099","volume":"48","author":"L. Trevisan","year":"2001","unstructured":"Trevisan, L.: Extractors and pseudorandom generators. Journal of the Association for Computing Machinery\u00a048(4), 860\u2013879 (2001) (preliminary version in STOC 1999)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"2_CR89","unstructured":"Trevisan, L.: List Decoding Using the XOR Lemma. Electronic Colloquium on Computational Complexity tech report 03-042 (2003)"},{"key":"2_CR90","doi-asserted-by":"crossref","unstructured":"Umans, C.: Pseudo-random generators for all hardnesses. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (2002)","DOI":"10.1145\/509907.509997"},{"key":"2_CR91","series-title":"London Math. Society Lecture Note Series","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1017\/CBO9780511526633.008","volume-title":"Boolean Function Complexity","author":"L. Valiant","year":"1992","unstructured":"Valiant, L.: Why is Boolean complexity theory difficult? In: Paterson, M.S. (ed.) Feedback Shift Registers. London Math. Society Lecture Note Series, vol.\u00a0169, pp. 84\u201394. Cambridge University Press, Cambridge (1992)"},{"key":"2_CR92","first-page":"36","volume":"12","author":"J. Neumann von","year":"1951","unstructured":"von Neumann, J.: Various Techniques Used in Relation to Random Digits. Applied Math. Series\u00a012, 36\u201338 (1951)","journal-title":"Applied Math. Series"},{"key":"2_CR93","volume-title":"The Complexity of Boolean Functions","author":"I. Wegener","year":"1987","unstructured":"Wegener, I.: The Complexity of Boolean Functions. Wiley-Teubner, Chichester (1987)"},{"key":"2_CR94","first-page":"75","volume":"2","author":"S. Yablonski","year":"1959","unstructured":"Yablonski, S.: The algorithmic difficulties of synthesizing minimal switching circuits. Problemy Kibornetiki\u00a02, 75\u2013121 (1959)","journal-title":"Problemy Kibornetiki"},{"key":"2_CR95","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Theory and applications of trapdoor functions. In: Proceedings of the Twenty-Third Annual IEEE Symposium on Foundations of Computer Science, pp. 80\u201391 (1982)","DOI":"10.1109\/SFCS.1982.45"},{"key":"2_CR96","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Separating the Polynomial-Time Hierarchy by Oracles. In: FOCS, pp. 1\u201310 (1985)","DOI":"10.1109\/SFCS.1985.49"},{"key":"2_CR97","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"Symbolic and Algebraic Computation","author":"R.E. Zippel","year":"1979","unstructured":"Zippel, R.E.: Probabilistic algorithms for sparse polynomials. In: Ng, K.W. (ed.) EUROSAM 1979 and ISSAC 1979. LNCS, vol.\u00a072, pp. 216\u2013226. Springer, Heidelberg (1979)"},{"key":"2_CR98","doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: General Weak Random Sources. In: 31st FOCS, pp. 534\u2013543 (1990)","DOI":"10.1109\/FSCS.1990.89574"},{"key":"2_CR99","doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: Simulating BPP Using a General Weak Random Source. In: FOCS, pp. 79\u201389 (1991)","DOI":"10.1109\/SFCS.1991.185351"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11590156_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T05:12:35Z","timestamp":1736140355000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11590156_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540304951","9783540324195"],"references-count":99,"URL":"https:\/\/doi.org\/10.1007\/11590156_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}