{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:55:02Z","timestamp":1725490502298},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540742395"},{"type":"electronic","value":"9783540742401"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74240-1_35","type":"book-chapter","created":{"date-parts":[[2007,8,27]],"date-time":"2007-08-27T11:04:18Z","timestamp":1188212658000},"page":"400-411","source":"Crossref","is-referenced-by-count":1,"title":["Impossibility Results on Weakly Black-Box Hardness Amplification"],"prefix":"10.1007","author":[{"given":"Chi-Jen","family":"Lu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shi-Chun","family":"Tsai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hsin-Lung","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"35_CR1","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1006\/jcss.1998.1583","volume":"57","author":"M. Agrawal","year":"1998","unstructured":"Agrawal, M., Allender, E., Rudich, S.: Reductions in circuit complexity: an isomorphism theorem and a gap theorem. Journal of Computer and System Sciences\u00a057, 127\u2013143 (1998)","journal-title":"Journal of Computer and System Sciences"},{"key":"35_CR2","volume-title":"Probability and measure","author":"P. Billingsley","year":"1995","unstructured":"Billingsley, P.: Probability and measure, 3rd edn. Wiley & Sons, Chichester (1995)","edition":"3"},{"issue":"4","key":"35_CR3","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(4), 307\u2013318 (1993)","journal-title":"Computational Complexity"},{"key":"35_CR4","first-page":"112","volume-title":"Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science","author":"M. Blum","year":"1982","unstructured":"Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo random bits. In: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, pp. 112\u2013117. IEEE Computer Society Press, Los Alamitos (1982)"},{"key":"35_CR5","unstructured":"Bogdanov, A., Trevisan, L.: On worst-case to average-case reductions for NP problems. In: 44th Annual Symposium on Foundations of Computer Science, Cambridge, Massachusetts, pp. 11\u201314 (October 2003)"},{"issue":"1","key":"35_CR6","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M.L. Furst","year":"1984","unstructured":"Furst, M.L., 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"},{"key":"35_CR7","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Computational limitations for small depth circuits. PhD thesis, MIT Press (1986)","DOI":"10.1145\/12130.12132"},{"key":"35_CR8","first-page":"192","volume-title":"Proceedings of the 36th ACM Symposium on Theory of Computing","author":"A. Healy","year":"2004","unstructured":"Healy, A., Vadhan, S., Viola, E.: Using nondeterminism to amplify hardness. In: Proceedings of the 36th ACM Symposium on Theory of Computing, pp. 192\u2013201. ACM Press, New York (2004)"},{"key":"35_CR9","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1109\/SFCS.1995.492584","volume-title":"Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science","author":"R. Impagliazzo","year":"1995","unstructured":"Impagliazzo, R.: Hard-core distributions for somewhat hard problems. In: Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pp. 538\u2013545. IEEE Computer Society Press, Los Alamitos (1995)"},{"key":"35_CR10","first-page":"812","volume-title":"Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science","author":"R. Impagliazzo","year":"1990","unstructured":"Impagliazzo, R., Levin, L.: No better ways to generate hard NP instances than picking uniformly at random. In: Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pp. 812\u2013821. IEEE Computer Society Press, Los Alamitos (1990)"},{"key":"35_CR11","first-page":"1","volume-title":"Proceedings of the 32nd ACM Symposium on Theory of Computing","author":"R. Impagliazzo","year":"2000","unstructured":"Impagliazzo, R., Shaltiel, R., Wigderson, A.: Extractors and pseudo-random generators with optimal seed length. In: Proceedings of the 32nd ACM Symposium on Theory of Computing, pp. 1\u201310. ACM Press, New York (2000)"},{"key":"35_CR12","first-page":"220","volume-title":"Proceedings of the 29th ACM Symposium on Theory of Computing","author":"R. Impagliazzo","year":"1997","unstructured":"Impagliazzo, R., Wigderson, A.: P=BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proceedings of the 29th ACM Symposium on Theory of Computing, pp. 220\u2013229. ACM Press, New York (1997)"},{"key":"35_CR13","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1145\/301250.301428","volume-title":"Proceedings of the thirty-first annual ACM symposium on Theory of computing","author":"A. Klivans","year":"1999","unstructured":"Klivans, A., van Melkebeek, D.: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. In: Proceedings of the thirty-first annual ACM symposium on Theory of computing, pp. 659\u2013667. ACM Press, New York (1999)"},{"key":"35_CR14","first-page":"170","volume-title":"Proceedings of the 20th Annual IEEE Conference on Computational Complexity","author":"C.-J. Lu","year":"2005","unstructured":"Lu, C.-J., Tsai, S.-C., Wu, H.-L.: On the complexity of hardness amplification. In: Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pp. 170\u2013182. IEEE Computer Society Press, Los Alamitos (2005)"},{"key":"35_CR15","doi-asserted-by":"crossref","unstructured":"Lin, H., Trevisan, L., Wee, H.: On hardness amplification of one-way functions. In: Proceedings of the 2nd Theory of Cryptography Conference, pp. 34\u201349 (2005)","DOI":"10.1007\/978-3-540-30576-7_3"},{"issue":"1","key":"35_CR16","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/BF01375474","volume":"11","author":"N. Nisan","year":"1991","unstructured":"Nisan, N.: Pseudorandom bits for constant depth circuits. Combinatorica\u00a011(1), 63\u201370 (1991)","journal-title":"Combinatorica"},{"issue":"2","key":"35_CR17","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 Computing System Science\u00a049(2), 149\u2013167 (1994)","journal-title":"Journal of Computing System Science"},{"key":"35_CR18","first-page":"751","volume-title":"Proceedings of the 34th ACM Symposium on Theory of Computing","author":"R. O\u2019Donnell","year":"2002","unstructured":"O\u2019Donnell, R.: Hardness amplification within NP. In: Proceedings of the 34th ACM Symposium on Theory of Computing, pp. 751\u2013760. ACM Press, New York (2002)"},{"key":"35_CR19","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"issue":"2","key":"35_CR20","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)","journal-title":"Journal of Computer and System Sciences"},{"key":"35_CR21","doi-asserted-by":"crossref","first-page":"648","DOI":"10.1109\/SFCS.2001.959941","volume-title":"Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science","author":"R. Shaltiel","year":"2001","unstructured":"Shaltiel, R., Umans, C.: Simple extractors for all min-entropies and a new pseudo-random generator. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pp. 648\u2013657. IEEE Computer Society Press, Los Alamitos (2001)"},{"issue":"2","key":"35_CR22","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"},{"issue":"3-4","key":"35_CR23","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/s00037-004-0187-1","volume":"13","author":"E. Viola","year":"2004","unstructured":"Viola, E.: The complexity of constructing pseudorandom generators from hard functions. Computational Complexity\u00a013(3-4), 147\u2013188 (2004)","journal-title":"Computational Complexity"},{"key":"35_CR24","first-page":"183","volume-title":"Proceedings of the 20th Annual IEEE Conference on Computational Complexity","author":"E. Viola","year":"2005","unstructured":"Viola, E.: On constructing parallel pseudorandom generators from one-way Functions. In: Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pp. 183\u2013197. IEEE Computer Society Press, Los Alamitos (2005)"},{"key":"35_CR25","first-page":"80","volume-title":"Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science","author":"A.C.-C. Yao","year":"1982","unstructured":"Yao, A.C.-C.: Theory and applications of trapdoor functions. In: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, pp. 80\u201391. IEEE Computer Society Press, Los Alamitos (1982)"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74240-1_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T14:28:27Z","timestamp":1558276107000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74240-1_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540742395","9783540742401"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74240-1_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}