{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,6,28]],"date-time":"2023-06-28T04:20:57Z","timestamp":1687926057169},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,5,23]],"date-time":"2023-05-23T00:00:00Z","timestamp":1684800000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,5,23]],"date-time":"2023-05-23T00:00:00Z","timestamp":1684800000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s00037-023-00238-9","type":"journal-article","created":{"date-parts":[[2023,5,23]],"date-time":"2023-05-23T04:03:16Z","timestamp":1684814596000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Is it possible to improve Yao\u2019s XOR lemma using reductions that exploit the efficiency of their oracle?"],"prefix":"10.1007","volume":"32","author":[{"given":"Ronen","family":"Shaltiel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,23]]},"reference":[{"key":"238_CR1","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3s Ajtai (1983). $$\\sum^{1}$$1-Formulae on finite structures. Ann.\nPure Appl. Log. 24(1), 1\u201348. URL https:\/\/doi.org\/10.1016\/0168-0072(83)90038-6.","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"238_CR2","doi-asserted-by":"crossref","unstructured":"Adi Akavia, Oded Goldreich, Shafi Goldwasser & Dana\nMoshkovitz (2006). On basing one-way functions on NP-hardness. In\nProceedings of the 38th Annual ACM Symposium on Theory of Computing,\n701\u2013710. URL https:\/\/doi.org\/10.1145\/1132516.1132614.","DOI":"10.1145\/1132516.1132614"},{"key":"238_CR3","doi-asserted-by":"crossref","unstructured":"Benny Applebaum, Sergei Artemenko, Ronen Shaltiel &\nGuang Yang (2016). Incompressible Functions, Relative-Error Extractors,\nand the Power of Nondeterministic Reductions. Computational\nComplexity 25(2), 349\u2013418. URL https:\/\/doi.org\/10.1007\/s00037-016-0128-9.","DOI":"10.1007\/s00037-016-0128-9"},{"key":"238_CR4","doi-asserted-by":"crossref","unstructured":"Sergei Artemenko & Ronen Shaltiel (2014). Lower Bounds on the\nQuery Complexity of Non-uniform and Adaptive Reductions Showing\nHardness Amplification. Computational Complexity 23(1), 43\u201383. URL\nhttps:\/\/doi.org\/10.1007\/s00037-012-0056-2.","DOI":"10.1007\/s00037-012-0056-2"},{"key":"238_CR5","doi-asserted-by":"crossref","unstructured":"Albert Atserias (2006). Distinguishing SAT from Polynomial-Size\nCircuits, through Black-Box Queries. In 21st Annual IEEE Conference\non Computational Complexity, 88\u201395. URL https:\/\/doi.org\/10.1109\/CCC.2006.17.","DOI":"10.1109\/CCC.2006.17"},{"key":"238_CR6","doi-asserted-by":"crossref","unstructured":"Andrej Bogdanov & Luca Trevisan (2006). On Worst-Case to\nAverage-Case Reductions for NP Problems. SIAM J. Comput. 36(4),\n1119\u20131159. URL https:\/\/doi.org\/10.1137\/S0097539705446974.","DOI":"10.1137\/S0097539705446974"},{"key":"238_CR7","doi-asserted-by":"crossref","unstructured":"Bill Fefferman, Ronen Shaltiel, Christopher Umans &\nEmanuele Viola (2013). On beating the hybrid argument. Theory of\nComputing 9, 809\u2013843.","DOI":"10.4086\/toc.2013.v009a026"},{"key":"238_CR8","doi-asserted-by":"crossref","unstructured":"Joan Feigenbaum & Lance Fortnow (1993). Random-Self-\nReducibility of Complete Sets. SIAM J. Comput. 22(5), 994\u20131005.\nURL https:\/\/doi.org\/10.1137\/0222061.","DOI":"10.1137\/0222061"},{"key":"238_CR9","doi-asserted-by":"crossref","unstructured":"Oded Goldreich & Hugo Krawczyk (1996). On the Composition\nof Zero-Knowledge Proof Systems. SIAM J. Comput. 25(1), 169\u2013192.\nURL https:\/\/doi.org\/10.1137\/S0097539791220688.","DOI":"10.1137\/S0097539791220688"},{"key":"238_CR10","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Noam Nisan & Avi Wigderson (2011). On\nYao\u2019s XOR lemma. In Studies in Complexity and Cryptography.\nMiscellanea on the Interplay between Randomness and Computation,\nOded Goldreich, editor, volume 6650 of Lecture Notes in Computer\nScience, 273\u2013301. Springer. URL https:\/\/doi.org\/10.1007\/978-3-642-22670-0_23.","DOI":"10.1007\/978-3-642-22670-0_23"},{"key":"238_CR11","doi-asserted-by":"crossref","unstructured":"Aryeh Grinberg, Ronen Shaltiel & Emanuele Viola (2018).\nIndistinguishability by Adaptive Procedures with Advice, and Lower\nBounds on Hardness Amplification Proofs. In 59th IEEE Annual Symposium\non Foundations of Computer Science, 956\u2013966. URL https:\/\/doi.org\/10.1109\/FOCS.2018.00094.","DOI":"10.1109\/FOCS.2018.00094"},{"key":"238_CR12","doi-asserted-by":"crossref","unstructured":"Dan Gutfreund (2006). Worst-Case Vs. Algorithmic Average-Case\nComplexity in the Polynomial-Time Hierarchy. In Approximation, Randomization,\nand Combinatorial Optimization. Algorithms and Techniques,\n9th International Workshop on Approximation Algorithms for\nCombinatorial Optimization Problems, APPROX and 10th International\nWorkshop on Randomization and Computation, RANDOM, volume\n4110 of Lecture Notes in Computer Science, 386\u2013397. URL\nhttps:\/\/doi.org\/10.1007\/11830924_36.","DOI":"10.1007\/11830924_36"},{"key":"238_CR13","doi-asserted-by":"crossref","unstructured":"Dan Gutfreund & Guy N. Rothblum (2008). The Complexity of\nLocal List Decoding. In Approximation, Randomization and Combinatorial\nOptimization. Algorithms and Techniques, 11th International\nWorkshop, APPROX, and 12th International Workshop, RANDOM,\nvolume 5171 of Lecture Notes in Computer Science, 455\u2013468. URL\nhttps:\/\/doi.org\/10.1007\/978-3-540-85363-3_36.","DOI":"10.1007\/978-3-540-85363-3_36"},{"key":"238_CR14","doi-asserted-by":"crossref","unstructured":"Dan Gutfreund, Ronen Shaltiel & Amnon Ta-Shma (2007). If\nNP Languages are Hard on the Worst-Case, Then it is Easy to Find\nTheir Hard Instances. Computational Complexity 16(4), 412\u2013441. URL\nhttps:\/\/doi.org\/10.1007\/s00037-007-0235-8.","DOI":"10.1007\/s00037-007-0235-8"},{"key":"238_CR15","doi-asserted-by":"crossref","unstructured":"Dan Gutfreund & Amnon Ta-Shma (2007). Worst-Case to Average-\nCase Reductions Revisited. In Approximation, Randomization, and\n Combinatorial Optimization. Algorithms and Techniques, 10th International\nWorkshop, APPROX, and 11th International Workshop, RANDOM,\nvolume 4627 of Lecture Notes in Computer Science, 569\u2013583.\nURL https:\/\/doi.org\/10.1007\/978-3-540-74208-1_41.","DOI":"10.1007\/978-3-540-74208-1_41"},{"key":"238_CR16","doi-asserted-by":"crossref","unstructured":"Dan Gutfreund & Salil P. Vadhan (2008). Limitations of\nHardness vs. Randomness under Uniform Reductions. In Approximation,\nRandomization and Combinatorial Optimization. Algorithms\nand Techniques, 11th International Workshop, APPROX, and 12th\nInternational Workshop, RANDOM, volume 5171 of Lecture Notes\nin Computer Science, 469\u2013482. URL https:\/\/doi.org\/10.1007\/978-3-540-85363-3_37.","DOI":"10.1007\/978-3-540-85363-3_37"},{"key":"238_CR17","doi-asserted-by":"crossref","unstructured":"Dan Gutfreund & Emanuele Viola (2004). Fooling Parity Tests\nwith Parity Gates. In Approximation, Randomization, and Combinatorial\nOptimization, Algorithms and Techniques, 7th International\nWorkshop on Approximation Algorithms for Combinatorial Optimization\nProblems, APPROX, and 8th International Workshop on Randomization\nand Computation, RANDOM, volume 3122 of Lecture Notes\nin Computer Science, 381\u2013392. URL https:\/\/doi.org\/10.1007\/978-3-540-27821-4_34.","DOI":"10.1007\/978-3-540-27821-4_34"},{"key":"238_CR18","doi-asserted-by":"crossref","unstructured":"Shuichi Hirahara (2018). Non-Black-Box Worst-Case to Average-\nCase Reductions within NP. In 59th IEEE Annual Symposium on\nFoundations of Computer Science, 247\u2013258. URL https:\/\/doi.org\/10.1109\/FOCS.2018.00032.","DOI":"10.1109\/FOCS.2018.00032"},{"key":"238_CR19","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo (1995). Hard-Core Distributions for Somewhat\nHard Problems. In 36th Annual Symposium on Foundations of Computer\nScience, 538\u2013545. URL https:\/\/doi.org\/10.1109\/SFCS.1995.492584.","DOI":"10.1109\/SFCS.1995.492584"},{"key":"238_CR20","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo & Steven Rudich (1989). Limits on the Provable\nConsequences of One-Way Permutations. In Proceedings of the\n21st Annual ACM Symposium on Theory of Computing, 44\u201361. URL\nhttps:\/\/doi.org\/10.1145\/73007.73012.","DOI":"10.1145\/73007.73012"},{"key":"238_CR21","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo & Avi Wigderson (1997). P = BPP if E\nRequires Exponential Circuits: Derandomizing the XOR Lemma. In\nProceedings of the Twenty-Ninth Annual ACM Symposium on the Theory\nof Computing, 220\u2013229. URL https:\/\/doi.org\/10.1145\/258533.258590.","DOI":"10.1145\/258533.258590"},{"key":"238_CR22","doi-asserted-by":"crossref","unstructured":"Adam R. Klivans & Rocco A. Servedio (2003). Boosting and\nHard-Core Set Construction. Machine Learning 51(3), 217\u2013238. URL\nhttps:\/\/doi.org\/10.1023\/A:1022949332276.","DOI":"10.1023\/A:1022949332276"},{"key":"238_CR23","doi-asserted-by":"crossref","unstructured":"Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan,\nUtkarsh Tripathi & S. Venkitesh (2019). A fixed-depth sizehierarchy\ntheorem for AC0[\u2295] via the coin problem. In Proceedings of\nthe 51st Annual ACM Symposium on Theory of Computing, 442\u2013453.\nURL https:\/\/doi.org\/10.1145\/3313276.3316339.","DOI":"10.1145\/3313276.3316339"},{"key":"238_CR24","doi-asserted-by":"crossref","unstructured":"Chi-Jen Lu, Shi-Chun Tsai & Hsin-Lung Wu (2008). On the\nComplexity of Hardness Amplification. IEEE Trans. Information Theory\n54(10), 4575\u20134586. URL https:\/\/doi.org\/10.1109\/TIT.2008.928988.","DOI":"10.1109\/TIT.2008.928988"},{"key":"238_CR25","unstructured":"Igor Carboni Oliveira, Rahul Santhanam & Srikanth Srinivasan\n(2019). Parity Helps to Compute Majority. In 34th Computational\nComplexity Conference, volume 137, 23:1\u201323:17. URL https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2019.23."},{"key":"238_CR26","doi-asserted-by":"crossref","unstructured":"Alexander Razborov (1987). Lower bounds on the dimension of\nschemes of bounded depth in a complete basis containing the logical\naddition function. Akademiya Nauk SSSR. Matematicheskie Zametki\n41(4), 598\u2013607. English translation in Mathematical Notes of\nthe Academy of Sci. of the USSR, 41(4):333-338, 1987.","DOI":"10.1007\/BF01137685"},{"key":"238_CR27","doi-asserted-by":"crossref","unstructured":"Omer Reingold, Luca Trevisan & Salil P. Vadhan (2004). Notions\nof Reducibility between Cryptographic Primitives. In Theory of\nCryptography, First Theory of Cryptography Conference, TCC, volume\n2951 of Lecture Notes in Computer Science, 1\u201320. URL https:\/\/doi.org\/10.1007\/978-3-540-24638-1_1.","DOI":"10.1007\/978-3-540-24638-1_1"},{"key":"238_CR28","unstructured":"Ronen Shaltiel (2020). Is It Possible to Improve Yao\u2019s XOR Lemma\nUsing Reductions That Exploit the Efficiency of Their Oracle? In\nApproximation, Randomization, and Combinatorial Optimization. Algorithms\nand Techniques, APPROX\/RANDOM 2020, August 17-19,\n2020, Virtual Conference, Jaroslaw Byrka & Raghu Meka, editors,\nvolume 176 of LIPIcs, 10:1\u201310:20. Schloss Dagstuhl - Leibniz-\nZentrum f\u00fcr Informatik. URL https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2020.10."},{"key":"238_CR29","doi-asserted-by":"crossref","unstructured":"Ronen Shaltiel & Emanuele Viola (2010). Hardness Amplification\nProofs Require Majority. SIAM J. Comput. 39(7), 3122\u20133154. URL\nhttps:\/\/doi.org\/10.1137\/080735096.","DOI":"10.1137\/080735096"},{"key":"238_CR30","doi-asserted-by":"crossref","unstructured":"Roman Smolensky (1987). Algebraic Methods in the Theory of Lower\nBounds for Boolean Circuit Complexity. In Proceedings of the 19th Annual\nACM Symposium on Theory of Computing, 77\u201382. URL https:\/\/doi.org\/10.1145\/28395.28404.","DOI":"10.1145\/28395.28404"},{"key":"238_CR31","doi-asserted-by":"crossref","unstructured":"Madhu Sudan, Luca Trevisan & Salil P. Vadhan (2001). Pseudorandom\nGenerators without the XOR Lemma. J. Comput. Syst. Sci.\n62(2), 236\u2013266. URL https:\/\/doi.org\/10.1006\/jcss.2000.1730.","DOI":"10.1006\/jcss.2000.1730"},{"key":"238_CR32","doi-asserted-by":"crossref","unstructured":"Luca Trevisan & Salil P. Vadhan (2007). Pseudorandomness\nand Average-Case Complexity Via Uniform Reductions. Computational\nComplexity 16(4), 331\u2013364. URL https:\/\/doi.org\/10.1007\/s00037-007-0233-x.","DOI":"10.1007\/s00037-007-0233-x"},{"key":"238_CR33","doi-asserted-by":"crossref","unstructured":"Emanuele Viola (2003). Hardness vs. Randomness within Alternating\nTime. In 18th Annual IEEE Conference on Computational Complexity,\n53. URL https:\/\/doi.org\/10.1109\/CCC.2003.1214410.","DOI":"10.1109\/CCC.2003.1214410"},{"key":"238_CR34","unstructured":"Emanuele Viola (2006). The Complexity of Hardness Amplification\nand Derandomization. Ph.D. thesis, Harvard University."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00238-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-023-00238-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00238-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,27]],"date-time":"2023-06-27T17:04:27Z","timestamp":1687885467000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-023-00238-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,23]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["238"],"URL":"https:\/\/doi.org\/10.1007\/s00037-023-00238-9","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,23]]},"assertion":[{"value":"10 April 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 May 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"5"}}