{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:43:14Z","timestamp":1775054594558,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540304951","type":"print"},{"value":"9783540324195","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11590156_6","type":"book-chapter","created":{"date-parts":[[2005,12,5]],"date-time":"2005-12-05T15:43:16Z","timestamp":1133797396000},"page":"92-105","source":"Crossref","is-referenced-by-count":60,"title":["Proving Lower Bounds Via Pseudo-random Generators"],"prefix":"10.1007","author":[{"given":"Manindra","family":"Agrawal","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal On, M.: derandomizing tests for certain polynomial identities. In: Proceedings of the Conference on Computational Complexity, pp. 355\u2013362 (2003)","DOI":"10.1109\/CCC.2003.1214434"},{"issue":"2","key":"6_CR2","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":"6_CR3","doi-asserted-by":"crossref","unstructured":"Alon, N., Goldreich, O., H\u00e5stad, J., Peralta, R.: Simple constructions of almost fc-wise independent random variables. In: Proceedings of Annual IEEE Symposium on Foundations of Computer Science, pp. 544\u2013553 (1990)","DOI":"10.1109\/FSCS.1990.89575"},{"key":"6_CR4","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 Journal on Computing\u00a013, 850\u2013864 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"6_CR5","unstructured":"Damm, C.: DET=L#l . Technical Report Informatik-preprint 8, Fachbereich In- formatik der Humboldt Universitat zu Berlin (1991)"},{"key":"6_CR6","unstructured":"Fortnow, L.: The role of relativization in complexity theory. In: Bulletin of the European Association for Theoretical Computer Science, Complexity Theory Column (1994)"},{"issue":"2","key":"6_CR7","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1006\/jcss.1999.1671","volume":"60","author":"L. Fortnow","year":"2000","unstructured":"Fortnow, L.: Time-space tradeoffs for satisfiability. J. Comput. Sys. Sci.\u00a060(2), 337\u2013353 (2000)","journal-title":"J. Comput. Sys. Sci."},{"key":"6_CR8","unstructured":"H\u00e5stad, J.: Computational limitations on small depth circuits.PhD thesis, Massachusetts Institute of Technology (1986)"},{"key":"6_CR9","unstructured":"Hastad, J., Impagliazzo, R., Levin, L., Luby, M.: A pseudo-random generator from any one-way function. SIAM Journal on Computing, 221\u2013243 (1998)"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits Derandomizing the XOR lemma. In: Proceedings of Annual ACM Symposium on the Theory of Computing, pp. 220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing polyonmial identity tests means proving circuit lower bounds. In: Proceedings of Annual ACM Symposium on the Theory of Computing, pp. 355\u2013364 (2003)","DOI":"10.1145\/780542.780595"},{"issue":"2","key":"6_CR12","first-page":"496","volume":"31","author":"K. Mulmuley","year":"2002","unstructured":"Mulmuley, K., Sohoni, M.: Geometric complexity theory I: An approach to the P vs. NP and other related problems. SIAM Journal on Computing\u00a031(2), 496\u2013526 (2002)","journal-title":"NP and other related problems. SIAM Journal on Computing"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. In: Proceedings of Annual ACM Symposium on the Theory of Computing, pp. 213\u2013223 (1990)","DOI":"10.1145\/100216.100244"},{"issue":"2","key":"6_CR14","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. J. Comput. Sys. Sci\u00a049(2), 149\u2013167 (1994)","journal-title":"J. Comput. Sys. Sci"},{"key":"#cr-split#-6_CR15.1","unstructured":"Razborov, A.: Lower bounds for the monotone complexity of some boolean functions. Doklady Akademii Nauk SSSR\u00a0281(4), 798\u2013801 (1985);"},{"key":"#cr-split#-6_CR15.2","unstructured":"English translation in Soviet Math. Doklady\u00a031, 354\u2013357 (1985)"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Razborov, A., Rudich, S.: Natural proofs. In: Proceedings of Annual ACM Symposium on the Theory of Computing, pp. 204\u2013213 (1994)","DOI":"10.1145\/195058.195134"},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected s-t-connectivity in logspace. In: Proceedings of Annual ACM Symposium on the Theory ofComputing, pp. 376\u2013385 (2005)","DOI":"10.1145\/1060590.1060647"},{"issue":"4","key":"6_CR18","doi-asserted-by":"publisher","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. J. ACM\u00a027(4), 701\u2013717 (1980)","journal-title":"J. ACM"},{"key":"6_CR19","unstructured":"Toda, S.: Counting problems computationally equivalent to the determinant (1991) (manuscript)"},{"key":"6_CR20","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"L. Valiant","year":"1983","unstructured":"Valiant, L., Skyum, S., Berkowitz, S., Rackoff, C.: Fast parallel computation of polynnomials using few processors. SIAM Journal on Computing\u00a012, 641\u2013644 (1983)","journal-title":"SIAM Journal on Computing"},{"key":"6_CR21","series-title":"Lecture Notes in Computer Science","first-page":"270","volume-title":"Structure in Complexity Theory","author":"V. Vinay","year":"1991","unstructured":"Vinay, V.: Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In: Selman, A.L. (ed.) Structure in Complexity Theory. LNCS, vol.\u00a0223, pp. 270\u2013284. Springer, Heidelberg (1991)"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Theory and applications of trapdoor functions. In: Proceedings of Annual IEEE Symposium on Foundations of Computer Science, pp. 80\u201391 (1982)","DOI":"10.1109\/SFCS.1982.45"},{"key":"6_CR23","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)"}],"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_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T05:11:43Z","timestamp":1736140303000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11590156_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540304951","9783540324195"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11590156_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}