{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T19:10:03Z","timestamp":1745953803377,"version":"3.40.4"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,1,26]],"date-time":"2013-01-26T00:00:00Z","timestamp":1359158400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2014,3]]},"DOI":"10.1007\/s00037-012-0056-2","type":"journal-article","created":{"date-parts":[[2013,1,25]],"date-time":"2013-01-25T07:01:32Z","timestamp":1359097292000},"page":"43-83","source":"Crossref","is-referenced-by-count":7,"title":["Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification"],"prefix":"10.1007","volume":"23","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","published-online":{"date-parts":[[2013,1,26]]},"reference":[{"key":"56_CR1","doi-asserted-by":"crossref","unstructured":"A. Akavia, O. Goldreich, S. Goldwasser & D. Moshkovitz (2006). On basing one-way functions on NP-hardness. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 701\u2013710.","DOI":"10.1145\/1132516.1132614"},{"key":"56_CR2","doi-asserted-by":"crossref","unstructured":"A. Atserias (2006). Distinguishing SAT from Polynomial-Size Circuits, through Black-Box Queries. In IEEE Conference on Computational Complexity, 88\u201395.","DOI":"10.1109\/CCC.2006.17"},{"key":"56_CR3","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"Babai L., Fortnow L., Nisan N., Wigderson A. (1993) BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs. Computational Complexity 3: 307\u2013318","journal-title":"Computational Complexity"},{"key":"56_CR4","unstructured":"A. Bogdanov & M. Safra (2007). Hardness Amplification for Errorless Heuristics. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 418\u2013426."},{"issue":"4","key":"56_CR5","doi-asserted-by":"crossref","first-page":"1119","DOI":"10.1137\/S0097539705446974","volume":"36","author":"A. Bogdanov","year":"2006","unstructured":"Bogdanov A., Trevisan L. (2006) OnWorst-Case to Average-Case Reductions for NP Problems. SIAM J. Comput. 36(4): 1119\u20131159","journal-title":"SIAM J. Comput."},{"issue":"5","key":"56_CR6","doi-asserted-by":"crossref","first-page":"994","DOI":"10.1137\/0222061","volume":"22","author":"J. Feigenbaum","year":"1993","unstructured":"Feigenbaum J., Fortnow L. (1993) Random-Self-Reducibility of Complete Sets. SIAM J. Comput. 22(5): 994\u20131005","journal-title":"SIAM J. Comput."},{"key":"56_CR7","unstructured":"O. Goldreich, N. Nisan & A. Wigderson (2011). On Yao\u2019s XORLemma. In Studies in Complexity and Cryptography, Oded Goldreich, editor, volume 6650 of Lecture Notes in Computer Science, 273\u2013301. Springer. ISBN 978-3-642-22669-4."},{"key":"56_CR8","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, D. Gutfreund, A. Healy, T. Kaufman & G. N. Rothblum (2007). Verifying and decoding in constant depth. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 440\u2013449.","DOI":"10.1145\/1250790.1250855"},{"issue":"1","key":"56_CR9","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/j.jcss.2010.06.008","volume":"77","author":"P. Gopalan","year":"2011","unstructured":"Gopalan P., Guruswami V. (2011) Hardness amplification within NP against deterministic algorithms. J. Comput. Syst. Sci. 77(1): 107\u2013121","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"56_CR10","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1007\/s00037-008-0253-1","volume":"17","author":"V. Guruswami","year":"2008","unstructured":"Guruswami V., Kabanets V. (2008) Hardness Amplification via Space-Efficient Direct Products. Computational Complexity 17(4): 475\u2013500","journal-title":"Computational Complexity"},{"key":"56_CR11","unstructured":"D. Gutfreund & G. Rothblum (2008). The Complexity of Local List Decoding. In Proceedings of the 12th Intl. Workshop on Randomization and Computation."},{"issue":"4","key":"56_CR12","doi-asserted-by":"crossref","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. (2007) If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances. Computational Complexity 16(4): 412\u2013441","journal-title":"Computational Complexity"},{"key":"56_CR13","unstructured":"D. Gutfreund & A. Ta-Shma (2007). Worst-Case to Average-Case Reductions Revisited. In Proceedings of the 11th Intl. Workshop on Randomization and Computation, 569\u2013583."},{"key":"56_CR14","unstructured":"D. Gutfreund & S. P. Vadhan (2008). Limitations of Hardness vs. Randomness under Uniform Reductions. In Proceedings of the 12th Intl. Workshop on Randomization and Computation, 469\u2013482."},{"issue":"4","key":"56_CR15","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1137\/S0097539705447281","volume":"35","author":"A. Healy","year":"2006","unstructured":"Healy A., Vadhan S.P., Viola E. (2006) Using Nondeterminism to Amplify Hardness. SIAM J. Comput. 35(4): 903\u2013931","journal-title":"SIAM J. Comput."},{"key":"56_CR16","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo (1995). Hard-Core Distributions for Somewhat Hard Problems. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, 538\u2013545.","DOI":"10.1109\/SFCS.1995.492584"},{"issue":"2","key":"56_CR17","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1137\/070683994","volume":"39","author":"R. Impagliazzo","year":"2009","unstructured":"Impagliazzo R., Jaiswal R., Kabanets V. (2009a) Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification. SIAM J. Comput. 39(2): 564\u2013605","journal-title":"SIAM J. Comput."},{"issue":"1","key":"56_CR18","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s00145-008-9029-7","volume":"22","author":"R. Impagliazzo","year":"2009","unstructured":"Impagliazzo R., Jaiswal R., Kabanets V. (2009b) Chernoff-Type Direct Product Theorems. J. Cryptology 22(1): 75\u201392","journal-title":"J. Cryptology"},{"issue":"4","key":"56_CR19","doi-asserted-by":"crossref","first-page":"1637","DOI":"10.1137\/080734030","volume":"39","author":"R. Impagliazzo","year":"2010","unstructured":"Impagliazzo R., Jaiswal R., Kabanets V., Wigderson A. (2010) Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. SIAM J. Comput. 39(4): 1637\u20131665","journal-title":"SIAM J. Comput."},{"key":"56_CR20","unstructured":"R. Impagliazzo & A. Wigderson (1997). P =\u00a0 BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 220\u2013229."},{"issue":"4","key":"56_CR21","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1006\/jcss.2001.1780","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo R., Wigderson A. (2001) Randomness vs Time: Derandomization under a Uniform Assumption. J. Comput. Syst. Sci. 63(4): 672\u2013688","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"56_CR22","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1023\/A:1022949332276","volume":"53","author":"A. Klivans","year":"2003","unstructured":"Klivans A., Servedio R.A. (2003) Boosting and Hard-Core Sets. Machine Learning 53(3): 217\u2013238","journal-title":"Machine Learning"},{"issue":"4","key":"56_CR23","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/BF02579323","volume":"7","author":"L.A. Levin","year":"1987","unstructured":"Levin L.A. (1987) One-way functions and pseudorandom generators. Combinatorica 7(4): 357\u2013363","journal-title":"Combinatorica"},{"key":"56_CR24","doi-asserted-by":"crossref","unstructured":"R. Lipton (1991). New Directions in Testing. In Proceedings of DIMACS Workshop on Distributed Computing and Cryptography, volume 2, 191\u2013202. ACM\/AMS.","DOI":"10.1090\/dimacs\/002\/13"},{"issue":"10","key":"56_CR25","doi-asserted-by":"crossref","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. (2008) On the Complexity of Hardness Amplification. IEEE Transactions on Information Theory 54(10): 4575\u20134586","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"56_CR26","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/s00037-011-0003-7","volume":"20","author":"C.-J. Lu","year":"2011","unstructured":"Lu C.-J., Tsai S.-C., Wu H.-L. (2011) Complexity of Hard-Core Set Proofs. Computational Complexity 20(1): 145\u2013171","journal-title":"Computational Complexity"},{"issue":"1","key":"56_CR27","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.jcss.2004.01.001","volume":"69","author":"R. O\u2019Donnell","year":"2004","unstructured":"O\u2019Donnell R. (2004) Hardness amplification within NP. J. Comput. Syst. Sci. 69(1): 68\u201394","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"56_CR28","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"Raz R. (1998) A Parallel Repetition Theorem. SIAM J. Comput. 27(3): 763\u2013803","journal-title":"SIAM J. Comput."},{"key":"56_CR29","doi-asserted-by":"crossref","unstructured":"O. Reingold, L. Trevisan & S. P. Vadhan (2004). Notions of Reducibility between Cryptographic Primitives. In Proceedings of the 1st Theory of Cryptography Conference, 1\u201320.","DOI":"10.1007\/978-3-540-24638-1_1"},{"issue":"2","key":"56_CR30","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1145\/1059513.1059516","volume":"52","author":"R. Shaltiel","year":"2005","unstructured":"Shaltiel R., Umans C. (2005) Simple extractors for all minentropies and a new pseudorandom generator. J. ACM 52(2): 172\u2013216","journal-title":"J. ACM"},{"issue":"7","key":"56_CR31","doi-asserted-by":"crossref","first-page":"3122","DOI":"10.1137\/080735096","volume":"39","author":"R. Shaltiel","year":"2010","unstructured":"Shaltiel R., Viola E. (2010) Hardness Amplification Proofs Require Majority. SIAM J. Comput. 39(7): 3122\u20133154","journal-title":"SIAM J. Comput."},{"issue":"2","key":"56_CR32","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1006\/jcss.2000.1730","volume":"62","author":"M. Sudan","year":"2001","unstructured":"Sudan M., Trevisan L., Vadhan S.P. (2001) Pseudorandom Generators without the XOR Lemma. J. Comput. Syst. Sci. 62(2): 236\u2013266","journal-title":"J. Comput. Syst. Sci."},{"key":"56_CR33","doi-asserted-by":"crossref","unstructured":"L. Trevisan (2003). List-Decoding Using The XOR Lemma. In Proceedings of the 44th Symposium on Foundations of Computer Science, 126\u2013135.","DOI":"10.1109\/SFCS.2003.1238187"},{"key":"56_CR34","unstructured":"L. Trevisan (2004). Some applications of coding theory in computational complexity. In Complexity of computations and proofs, volume 13 of Quad. Mat., 347\u2013424. Dept. Math., Seconda Univ. Napoli, Caserta."},{"key":"56_CR35","doi-asserted-by":"crossref","unstructured":"L. Trevisan (2005). On uniform amplification of hardness in NP. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 31\u201338.","DOI":"10.1145\/1060590.1060595"},{"issue":"4","key":"56_CR36","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/s00037-007-0233-x","volume":"16","author":"L. Trevisan","year":"2007","unstructured":"Trevisan L., Vadhan S. (2007) Pseudorandomness and Average-Case Complexity Via Uniform Reductions. Computational Complexity 16(4): 331\u2013364","journal-title":"Computational Complexity"},{"issue":"3-4","key":"56_CR37","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/s00037-004-0187-1","volume":"13","author":"E. Viola","year":"2005","unstructured":"Viola E. (2005a) The complexity of constructing pseudorandom generators from hard functions. Computational Complexity 13(3-4): 147\u2013188","journal-title":"Computational Complexity"},{"key":"56_CR38","doi-asserted-by":"crossref","unstructured":"E. Viola (2005b). On Constructing Parallel Pseudorandom Generators from One-Way Functions. In IEEE Conference on Computational Complexity, 183\u2013197.","DOI":"10.1109\/CCC.2005.16"},{"key":"56_CR39","doi-asserted-by":"crossref","unstructured":"T. Watson (2011). Query Complexity in Errorless Hardness Amplification. In Proceedings of the 15th Intl. Workshop on Randomization and Computation, 688\u2013699.","DOI":"10.1007\/978-3-642-22935-0_58"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0056-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-012-0056-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0056-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T18:29:16Z","timestamp":1745951356000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-012-0056-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,26]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["56"],"URL":"https:\/\/doi.org\/10.1007\/s00037-012-0056-2","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2013,1,26]]}}}