{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T05:36:22Z","timestamp":1740461782955,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":47,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153686"},{"type":"electronic","value":"9783642153693"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15369-3_29","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T04:01:36Z","timestamp":1282881696000},"page":"380-393","source":"Crossref","is-referenced-by-count":1,"title":["Uniform Derandomization from Pathetic Lower Bounds"],"prefix":"10.1007","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[]},{"given":"V.","family":"Arvind","sequence":"additional","affiliation":[]},{"given":"Fengming","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"29_CR1","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1006\/jcss.1999.1675","volume":"60","author":"M. Agrawal","year":"2000","unstructured":"Agrawal, M., Allender, E., Datta, S.: On TC $^{\\mbox{0}}$ , AC $^{\\mbox{0}}$ , and arithmetic circuits. Journal of Computer and System Sciences\u00a060(2), 395\u2013421 (2000)","journal-title":"Journal of Computer and System Sciences"},{"key":"29_CR2","doi-asserted-by":"crossref","unstructured":"Allender, E., Arvind, V., Wang, F.: Uniform derandomization from pathetic lower bounds. Technical Report TR10-069, Electronic Colloquium on Computational Complexity, ECCC (2010)","DOI":"10.1007\/978-3-642-15369-3_29"},{"issue":"1","key":"29_CR3","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1137\/060664537","volume":"38","author":"E. Allender","year":"2008","unstructured":"Allender, E., Hellerstein, L., McCabe, P., Pitassi, T., Saks, M.E.: Minimizing disjunctive normal form formulas and AC $^{\\mbox{0}}$ circuits given a truth table. SIAM Journal on Computing\u00a038(1), 63\u201384 (2008)","journal-title":"SIAM Journal on Computing"},{"key":"#cr-split#-29_CR4.1","unstructured":"Allender, E., Kouck\u00fd, M.: Amplifying lower bounds by means of self-reducibility. Journal of the ACM (to appear);"},{"key":"#cr-split#-29_CR4.2","unstructured":"A preliminary version appeared in Proc. IEEE Conference on Computational Complexity (2008)"},{"issue":"1","key":"29_CR5","doi-asserted-by":"publisher","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 ACM\u00a045(1), 179\u2013213 (1998)","journal-title":"Journal of the ACM"},{"issue":"1-2","key":"29_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(99)00024-9","volume":"221","author":"A.E. Andreev","year":"1999","unstructured":"Andreev, A.E., Clementi, A.E.F., Rolim, J.D.P.: Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs. Theoretical Computer Science\u00a0221(1-2), 3\u201318 (1999)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"29_CR7","doi-asserted-by":"publisher","first-page":"2103","DOI":"10.1137\/S0097539797325636","volume":"28","author":"A.E. Andreev","year":"1999","unstructured":"Andreev, A.E., Clementi, A.E.F., Rolim, J.D.P., Trevisan, L.: Weak random sources, hitting sets, and BPP simulations. SIAM Journal on Computing\u00a028(6), 2103\u20132116 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"29_CR8","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity, a modern approach","author":"S. Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity, a modern approach. Cambridge University Press, Cambridge (2009)"},{"key":"29_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/BFb0058034","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"V. Arvind","year":"1997","unstructured":"Arvind, V., K\u00f6bler, J.: On resource-bounded measure and pseudorandomness. In: Ramesh, S., Sivakumar, G. (eds.) FST TCS 1997. LNCS, vol.\u00a01346, pp. 235\u2013249. Springer, Heidelberg (1997)"},{"key":"29_CR10","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. Computational Complexity\u00a03, 307\u2013318 (1993)","journal-title":"Computational Complexity"},{"issue":"1","key":"29_CR11","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D.A. Barrington","year":"1989","unstructured":"Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC $^{\\mbox{1}}$ . Journal of Computer and System Sciences\u00a038(1), 150\u2013164 (1989)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"29_CR12","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1145\/636865.636867","volume":"50","author":"P. Beame","year":"2003","unstructured":"Beame, P., Saks, M.E., Sun, X., Vee, E.: Time-space trade-off lower bounds for randomized computation of decision problems. Journal of the ACM\u00a050(2), 154\u2013195 (2003)","journal-title":"Journal of the ACM"},{"issue":"1","key":"29_CR13","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/0221006","volume":"21","author":"M. Ben-Or","year":"1992","unstructured":"Ben-Or, M., Cleve, R.: Computing algebraic formulas using a constant number of registers. SIAM Journal on Computing\u00a021(1), 54\u201358 (1992)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"29_CR14","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(4), 850\u2013864 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"29_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/3-540-49116-3_9","volume-title":"STACS 99","author":"H. Buhrman","year":"1999","unstructured":"Buhrman, H., Fortnow, L.: One-sided versus two-sided error in probabilistic computation. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 100\u2013109. Springer, Heidelberg (1999)"},{"issue":"4","key":"29_CR16","doi-asserted-by":"publisher","first-page":"1279","DOI":"10.1137\/080735850","volume":"39","author":"Z. Dvir","year":"2009","unstructured":"Dvir, Z., Shpilka, A., Yehudayoff, A.: Hardness-randomness tradeoffs for bounded depth circuits. SIAM Journal on Computing\u00a039(4), 1279\u20131293 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Vadhan, S.P., Wigderson, A.: Simplified derandomization of BPP using a hitting set generator. Electronic Colloquium on Computational Complexity\u00a07(4) (2000)","DOI":"10.1007\/978-3-540-48413-4_14"},{"key":"29_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/978-3-540-48413-4_14","volume-title":"Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques","author":"O. Goldreich","year":"1999","unstructured":"Goldreich, O., Wigderson, A.: Improved derandomization of BPP using a hitting set generator. In: Hochbaum, D.S., Jansen, K., Rolim, J.D.P., Sinclair, A. (eds.) RANDOM 1999 and APPROX 1999. LNCS, vol.\u00a01671, pp. 131\u2013137. Springer, Heidelberg (1999)"},{"key":"29_CR19","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Gutfreund, D., Healy, A., Kaufman, T., Rothblum, G.N.: A (de)constructive approach to program checking. Technical Report TR07-047, Electronic Colloquium on Computational Complexity, ECCC (2007); See also STOC 2008","DOI":"10.1145\/1374376.1374399"},{"key":"29_CR20","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/s002009900021","volume":"10","author":"D. Grigoriev","year":"2000","unstructured":"Grigoriev, D., Razborov, A.: Exponential complexity lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. Applicable Algebra in Engineering, Communication and Computing\u00a010, 465\u2013487 (2000)","journal-title":"Applicable Algebra in Engineering, Communication and Computing"},{"key":"29_CR21","doi-asserted-by":"crossref","unstructured":"Grigoriev, D., Karpinski, M.: An exponential lower bound for depth 3 arithmetic circuits. In: Proc. ACM Symp. on Theory of Computing (STOC), pp. 577\u2013582 (1998)","DOI":"10.1145\/276698.276872"},{"key":"29_CR22","doi-asserted-by":"crossref","unstructured":"Gutfreund, D., Viola, E.: Fooling parity tests with parity gates. In: APPROX-RANDOM, pp. 381\u2013392 (2004)","DOI":"10.1007\/978-3-540-27821-4_34"},{"issue":"1","key":"29_CR23","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1137\/S0097539794261556","volume":"27","author":"J. H\u00e5stad","year":"1998","unstructured":"H\u00e5stad, J.: The shrinkage exponent of de morgan formulas is 2. SIAM Journal on Computing\u00a027(1), 48\u201364 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"29_CR24","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1016\/S0022-0000(02)00025-9","volume":"65","author":"W. Hesse","year":"2002","unstructured":"Hesse, W., Allender, E., Barrington, D.A.M.: Uniform constant-depth threshold circuits for division and iterated multiplication. Journal of Computer and System Sciences\u00a065(4), 695\u2013716 (2002)","journal-title":"Journal of Computer and System Sciences"},{"key":"29_CR25","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R.: Hard-core distributions for somewhat hard problems. In: Proc. IEEE Symp. on Found. of Comp. Sci. (FOCS), pp. 538\u2013545 (1995)","DOI":"10.1109\/SFCS.1995.492584"},{"issue":"3","key":"29_CR26","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1137\/S0097539792282965","volume":"26","author":"R. Impagliazzo","year":"1997","unstructured":"Impagliazzo, R., Paturi, R., Saks, M.E.: Size-depth tradeoffs for threshold circuits. SIAM Journal on Computing\u00a026(3), 693\u2013707 (1997)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"29_CR27","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1007\/s00493-006-0036-8","volume":"26","author":"R. Impagliazzo","year":"2006","unstructured":"Impagliazzo, R., Shaltiel, R., Wigderson, A.: Reducing the seed length in the Nisan-Wigderson generator. Combinatorica\u00a026(6), 647\u2013681 (2006)","journal-title":"Combinatorica"},{"key":"29_CR28","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proc. ACM Symp. on Theory of Computing (STOC), pp. 220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"issue":"4","key":"29_CR29","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1006\/jcss.2001.1780","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Wigderson, A.: Randomness vs time: Derandomization under a uniform assumption. Journal of Computer and System Sciences\u00a063(4), 672\u2013688 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"29_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/3-540-45687-2_29","volume-title":"Mathematical Foundations of Computer Science 2002","author":"K. Iwama","year":"2002","unstructured":"Iwama, K., Morizumi, H.: An explicit lower bound of 5n\u2009\u2212\u2009o(n) for boolean circuits. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 353\u2013364. Springer, Heidelberg (2002)"},{"issue":"1-2","key":"29_CR31","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"},{"issue":"5","key":"29_CR32","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1137\/S0097539700389652","volume":"31","author":"A. Klivans","year":"2002","unstructured":"Klivans, A., van Melkebeek, D.: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM Journal on Computing\u00a031(5), 1501\u20131526 (2002)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"29_CR33","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/s00037-005-0197-7","volume":"14","author":"P.B. Miltersen","year":"2005","unstructured":"Miltersen, P.B., Vinodchandran, N.V.: Derandomizing Arthur-Merlin games using hitting sets. Computational Complexity\u00a014(3), 256\u2013279 (2005)","journal-title":"Computational Complexity"},{"issue":"2","key":"29_CR34","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(2), 149\u2013167 (1994)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"29_CR35","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01294256","volume":"6","author":"N. Nisan","year":"1997","unstructured":"Nisan, N., Wigderson, A.: Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity\u00a06(3), 217\u2013234 (1997)","journal-title":"Computational Complexity"},{"key":"29_CR36","doi-asserted-by":"crossref","unstructured":"Raz, R.: Elusive functions and lower bounds for arithmetic circuits. In: Proc. ACM Symp. on Theory of Computing (STOC), pp. 711\u2013720 (2008)","DOI":"10.1145\/1374376.1374479"},{"issue":"2","key":"29_CR37","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s00037-009-0270-8","volume":"18","author":"R. Raz","year":"2009","unstructured":"Raz, R., Yehudayoff, A.: Lower bounds and separations for constant depth multilinear circuits. Journal of Computational Complexity\u00a018(2), 171\u2013207 (2009)","journal-title":"Journal of Computational Complexity"},{"issue":"2","key":"29_CR38","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1145\/1059513.1059516","volume":"52","author":"R. Shaltiel","year":"2005","unstructured":"Shaltiel, R., Umans, C.: Simple extractors for all min-entropies and a new pseudorandom generator. Journal of the ACM\u00a052(2), 172\u2013216 (2005)","journal-title":"Journal of the ACM"},{"key":"29_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1007\/3-540-10843-2_43","volume-title":"Automata, Languages and Programming","author":"A. Shamir","year":"1981","unstructured":"Shamir, A.: On the generation of cryptographically strong pseudo-random sequences. In: Even, S., Kariv, O. (eds.) ICALP 1981. LNCS, vol.\u00a0115, pp. 544\u2013550. Springer, Heidelberg (1981)"},{"issue":"1","key":"29_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00001609","volume":"10","author":"A. Shpilka","year":"2001","unstructured":"Shpilka, A., Wigderson, A.: Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity\u00a010(1), 1\u201327 (2001)","journal-title":"Computational Complexity"},{"issue":"2","key":"29_CR41","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.P.: Pseudorandom generators without the XOR lemma. Journal of Computer and System Sciences\u00a062(2), 236\u2013266 (2001)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"29_CR42","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1016\/S0022-0000(03)00046-1","volume":"67","author":"C. Umans","year":"2003","unstructured":"Umans, C.: Pseudo-random generators for all hardnesses. Journal of Computer and System Sciences\u00a067(2), 419\u2013440 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"29_CR43","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58575-3","volume-title":"Introduction to Coding Complexity","author":"J.H. Lint van","year":"1999","unstructured":"van Lint, J.H.: Introduction to Coding Complexity. Springer, Heidelberg (1999)"},{"issue":"3-4","key":"29_CR44","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/s00037-004-0187-1","volume":"13","author":"E. Viola","year":"2005","unstructured":"Viola, E.: The complexity of constructing pseudorandom generators from hard functions. Computational Complexity\u00a013(3-4), 147\u2013188 (2005)","journal-title":"Computational Complexity"},{"key":"29_CR45","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity","author":"H. Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity. Springer, Heidelberg (1999)"},{"key":"29_CR46","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Theory and applications of trapdoor functions (extended abstract). In: Proc. IEEE Symp. on Found. of Comp. Sci. (FOCS), pp. 80\u201391 (1982)","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15369-3_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T03:47:41Z","timestamp":1740455261000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}