{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T05:34:25Z","timestamp":1725600865469},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229343"},{"type":"electronic","value":"9783642229350"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22935-0_32","type":"book-chapter","created":{"date-parts":[[2011,8,12]],"date-time":"2011-08-12T05:20:39Z","timestamp":1313126439000},"page":"377-388","source":"Crossref","is-referenced-by-count":4,"title":["Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification"],"prefix":"10.1007","author":[{"given":"Sergei","family":"Artemenko","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronen","family":"Shaltiel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"Akavia, A., Goldreich, O., Goldwasser, S., Moshkovitz, D.: On basing one-way functions on np-hardness. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 701\u2013710 (2006)","DOI":"10.1145\/1132516.1132614"},{"key":"32_CR2","doi-asserted-by":"crossref","unstructured":"Atserias, A.: Distinguishing sat from polynomial-size circuits, through black-box queries. In: IEEE Conference on Computational Complexity, pp. 88\u201395 (2006)","DOI":"10.1109\/CCC.2006.17"},{"key":"32_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, 307\u2013318 (1993)","journal-title":"Computational Complexity"},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Safra, M.: Hardness amplification for errorless heuristics. In: 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 418\u2013426 (2007)","DOI":"10.1109\/FOCS.2007.25"},{"issue":"4","key":"32_CR5","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1137\/S0097539705446974","volume":"36","author":"A. Bogdanov","year":"2006","unstructured":"Bogdanov, A., Trevisan, L.: On worst-case to average-case reductions for np problems. SIAM J. Comput.\u00a036(4), 1119\u20131159 (2006)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"32_CR6","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1137\/0222061","volume":"22","author":"J. Feigenbaum","year":"1993","unstructured":"Feigenbaum, J., Fortnow, L.: Random-self-reducibility of complete sets. SIAM J. Comput.\u00a022(5), 994\u20131005 (1993)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"32_CR7","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.jcss.2010.06.008","volume":"77","author":"P. Gopalan","year":"2011","unstructured":"Gopalan, P., Guruswami, V.: Hardness amplification within NP against deterministic algorithms. J. Comput. Syst. Sci.\u00a077(1), 107\u2013121 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"32_CR8","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Gutfreund, D., Healy, A., Kaufman, T., Rothblum, G.N.: Verifying and decoding in constant depth. In: 39th Annual ACM Symposium on Theory of Computing (STOC), pp. 440\u2013449 (2007)","DOI":"10.1145\/1250790.1250855"},{"key":"32_CR9","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Impagliazzo, R., Levin, L.A., Venkatesan, R., Zuckerman, D.: Security preserving amplification of hardness. In: FOCS, pp. 318\u2013326 (1990)","DOI":"10.1109\/FSCS.1990.89550"},{"issue":"4","key":"32_CR10","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/s00037-008-0253-1","volume":"17","author":"V. Guruswami","year":"2008","unstructured":"Guruswami, V., Kabanets, V.: Hardness amplification via space-efficient direct products. Computational Complexity\u00a017(4), 475\u2013500 (2008)","journal-title":"Computational Complexity"},{"key":"32_CR11","unstructured":"Goldreich, O., Nisan, N., Wigderson, A.: On Yao\u2019s XOR lemma. Technical Report TR95\u2013050, Electronic Colloquium on Computational Complexity (March 1995), http:\/\/www.eccc.uni-trier.de\/"},{"key":"32_CR12","doi-asserted-by":"crossref","unstructured":"Gutfreund, D., Rothblum, G.: The complexity of local list decoding. In: 12th Intl. Workshop on Randomization and Computation, RANDOM (2008)","DOI":"10.1007\/978-3-540-85363-3_36"},{"issue":"4","key":"32_CR13","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/s00037-007-0235-8","volume":"16","author":"D. Gutfreund","year":"2007","unstructured":"Gutfreund, D., Shaltiel, R., Ta-Shma, A.: If np languages are hard on the worst-case, then it is easy to find their hard instances. Computational Complexity\u00a016(4), 412\u2013441 (2007)","journal-title":"Computational Complexity"},{"key":"32_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/978-3-540-74208-1_41","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"D. Gutfreund","year":"2007","unstructured":"Gutfreund, D., Ta-Shma, A.: Worst-case to average-case reductions revisited. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol.\u00a04627, pp. 569\u2013583. Springer, Heidelberg (2007)"},{"key":"32_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/978-3-540-85363-3_37","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"D. Gutfreund","year":"2008","unstructured":"Gutfreund, D., Vadhan, S.P.: Limitations of hardness vs. Randomness under uniform reductions. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 469\u2013482. Springer, Heidelberg (2008)"},{"issue":"4","key":"32_CR16","doi-asserted-by":"publisher","first-page":"903","DOI":"10.1137\/S0097539705447281","volume":"35","author":"A. Healy","year":"2006","unstructured":"Healy, A., Vadhan, S.P., Viola, E.: Using nondeterminism to amplify hardness. SIAM J. Comput.\u00a035(4), 903\u2013931 (2006)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"32_CR17","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1137\/070683994","volume":"39","author":"R. Impagliazzo","year":"2009","unstructured":"Impagliazzo, R., Jaiswal, R., Kabanets, V.: Approximate list-decoding of direct product codes and uniform hardness amplification. SIAM J. Comput.\u00a039(2), 564\u2013605 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"32_CR18","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s00145-008-9029-7","volume":"22","author":"R. Impagliazzo","year":"2009","unstructured":"Impagliazzo, R., Jaiswal, R., Kabanets, V.: Chernoff-type direct product theorems. J. Cryptology\u00a022(1), 75\u201392 (2009)","journal-title":"J. Cryptology"},{"issue":"4","key":"32_CR19","doi-asserted-by":"publisher","first-page":"1637","DOI":"10.1137\/080734030","volume":"39","author":"R. Impagliazzo","year":"2010","unstructured":"Impagliazzo, R., Jaiswal, R., Kabanets, V., Wigderson, A.: Uniform direct product theorems: Simplified, optimized, and derandomized. SIAM J. Comput.\u00a039(4), 1637\u20131665 (2010)","journal-title":"SIAM J. Comput."},{"key":"32_CR20","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R.: Hard-core distributions for somewhat hard problems. In: FOCS, pp. 538\u2013545 (1995)","DOI":"10.1109\/SFCS.1995.492584"},{"key":"32_CR21","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P\u2009=\u2009BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: STOC, pp. 220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"key":"32_CR22","volume-title":"39th Annual Symposium on Foundations of Computer Science","author":"R. Impagliazzo","year":"1998","unstructured":"Impagliazzo, R., Wigderson, A.: Randomness vs. time: De-randomization under a uniform assumption. In: 39th Annual Symposium on Foundations of Computer Science. IEEE, Los Alamitos (1998)"},{"issue":"3","key":"32_CR23","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1023\/A:1022949332276","volume":"53","author":"A. Klivans","year":"2003","unstructured":"Klivans, A., Servedio, R.A.: Boosting and hard-core sets. Machine Learning\u00a053(3), 217\u2013238 (2003)","journal-title":"Machine Learning"},{"issue":"4","key":"32_CR24","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"},{"key":"32_CR25","doi-asserted-by":"crossref","unstructured":"Lipton, R.: New directions in testing. In: Proceedings of DIMACS Workshop on Distributed Computing and Cryptography, vol.\u00a02, pp. 191\u2013202. ACM\/AMS (1991)","DOI":"10.1090\/dimacs\/002\/13"},{"key":"32_CR26","doi-asserted-by":"crossref","unstructured":"Lu, C.-J., Tsai, S.-C., Wu, H.-L.: On the complexity of hard-core set constructions. In: 34th International Colloquium on Automata, Languages and Programming, pp. 183\u2013194 (2007)","DOI":"10.1007\/978-3-540-73420-8_18"},{"issue":"10","key":"32_CR27","doi-asserted-by":"publisher","first-page":"4575","DOI":"10.1109\/TIT.2008.928988","volume":"54","author":"C.-J. Lu","year":"2008","unstructured":"Lu, C.-J., Tsai, S.-C., Wu, H.-L.: On the complexity of hardness amplification. IEEE Transactions on Information Theory\u00a054(10), 4575\u20134586 (2008)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"32_CR28","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.jcss.2004.01.001","volume":"69","author":"R. O\u2019Donnell","year":"2004","unstructured":"O\u2019Donnell, R.: Hardness amplification within $_{\\mbox{np}}$ . J. Comput. Syst. Sci.\u00a069(1), 68\u201394 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"32_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-24638-1_1","volume-title":"Theory of Cryptography","author":"O. Reingold","year":"2004","unstructured":"Reingold, O., Trevisan, L., Vadhan, S.P.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol.\u00a02951, pp. 1\u201320. Springer, Heidelberg (2004)"},{"issue":"2","key":"32_CR30","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. J. Comput. Syst. Sci.\u00a062(2), 236\u2013266 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"32_CR31","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. J. ACM\u00a052(2), 172\u2013216 (2005)","journal-title":"J. ACM"},{"issue":"7","key":"32_CR32","doi-asserted-by":"publisher","first-page":"3122","DOI":"10.1137\/080735096","volume":"39","author":"R. Shaltiel","year":"2010","unstructured":"Shaltiel, R., Viola, E.: Hardness amplification proofs require majority. SIAM J. Comput.\u00a039(7), 3122\u20133154 (2010)","journal-title":"SIAM J. Comput."},{"key":"32_CR33","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: List-decoding using the xor lemma. In: 44th Symposium on Foundations of Computer Science, pp. 126\u2013135 (2003)","DOI":"10.1109\/SFCS.2003.1238187"},{"key":"32_CR34","series-title":"Quad. Mat.","first-page":"347","volume-title":"Complexity of Computations and Proofs","author":"L. Trevisan","year":"2004","unstructured":"Trevisan, L.: Some applications of coding theory in computational complexity. In: Complexity of Computations and Proofs. Quad. Mat., vol.\u00a013, pp. 347\u2013424. Dept. Math., Seconda Univ., Napoli (2004)"},{"key":"32_CR35","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: On uniform amplification of hardness in np. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 31\u201338 (2005)","DOI":"10.1145\/1060590.1060595"},{"issue":"4","key":"32_CR36","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s00037-007-0233-x","volume":"16","author":"L. Trevisan","year":"2007","unstructured":"Trevisan, L., Vadhan, S.: Pseudorandomness and average-case complexity via uniform reductions. Computational Complexity\u00a016(4), 331\u2013364 (2007)","journal-title":"Computational Complexity"},{"issue":"3-4","key":"32_CR37","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":"32_CR38","doi-asserted-by":"crossref","unstructured":"Viola, E.: On constructing parallel pseudorandom generators from one-way functions. In: IEEE Conference on Computational Complexity, pp. 183\u2013197 (2005)","DOI":"10.1109\/CCC.2005.16"},{"key":"32_CR39","unstructured":"Watson, T.: Query complexity in errorless hardness amplification. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 17, p. 126 (2010)"}],"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-22935-0_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T21:03:03Z","timestamp":1560459783000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22935-0_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229343","9783642229350"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22935-0_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}