{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:04:19Z","timestamp":1775282659673,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,3,1]],"date-time":"2011-03-01T00:00:00Z","timestamp":1298937600000},"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":[[2011,3]]},"DOI":"10.1007\/s00037-011-0003-7","type":"journal-article","created":{"date-parts":[[2011,4,18]],"date-time":"2011-04-18T12:53:46Z","timestamp":1303131226000},"page":"145-171","source":"Crossref","is-referenced-by-count":8,"title":["Complexity of Hard-Core Set Proofs"],"prefix":"10.1007","volume":"20","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","published-online":{"date-parts":[[2011,4,19]]},"reference":[{"key":"3_CR1","unstructured":"Noga Alon & Joel H. Spencer (2000). The Probabilistic Method. Wiley, New York, 2nd edition."},{"issue":"4","key":"3_CR2","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L\u00e1szl\u00f3 Babai","year":"1993","unstructured":"Babai L\u00e1szl\u00f3, Fortnow Lance, Nisan Noam, Wigderson Avi (1993) BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity 3(4): 307\u2013318","journal-title":"Computational Complexity"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"Boaz Barak, Moritz Hardt & Satyen Kale (2009). The uniform hardcore lemma via approximate Bregman projections. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, 1193\u20131200.","DOI":"10.1137\/1.9781611973068.129"},{"issue":"2","key":"3_CR4","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1006\/inco.1995.1136","volume":"121","author":"Yoav Freund","year":"1995","unstructured":"Freund Yoav (1995) Boosting a Weak Learning Algorithm by Majority. Information and Computation 121(2): 256\u2013285","journal-title":"Information and Computation"},{"key":"3_CR5","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BF01200426","volume":"2","author":"Mikael Goldmann","year":"1992","unstructured":"Goldmann Mikael, Hastad Johan, Razborov Alexander A. (1992) Majority Gates VS. General Weighted Threshold Gates. Computational Complexity 2: 277\u2013300","journal-title":"General Weighted Threshold Gates. Computational Complexity"},{"issue":"2","key":"3_CR6","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0022-0000(93)90001-D","volume":"46","author":"Andras Hajnal","year":"1993","unstructured":"Hajnal Andras, Maass Wolfgang, Pudlak Pavel, Szegedy Mario, Turan Gyorgy (1993) Threshold Circuits of Bounded Depth. Journal of Computer System Sciences 46(2): 129\u2013154","journal-title":"Journal of Computer System Sciences"},{"issue":"4","key":"3_CR7","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1137\/S0097539705447281","volume":"35","author":"Alexander Healy","year":"2006","unstructured":"Healy Alexander, Salil Vadhan P., Viola Emanuele (2006) Using Nondeterminism to Amplify Hardness. SIAM Journal of Computing 35(4): 903\u2013931","journal-title":"SIAM Journal of Computing"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Thomas Holenstein (2005). Key agreement from weak bit agreement. In Proceedings of the 37th ACM Symposium on Theory of Computing, 664\u2013673.","DOI":"10.1145\/1060590.1060689"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Russell 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"},{"key":"3_CR10","unstructured":"Russell Impagliazzo & Avi Wigderson (1997). P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. In Proceedings of the 29th ACM Symposium on Theory of Computing, 220\u2013229."},{"issue":"3","key":"3_CR11","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1023\/A:1022949332276","volume":"51","author":"Adam R Klivans","year":"2003","unstructured":"Klivans Adam R, Servedio Rocco A (2003) Boosting and Hard-Core Set Construction. Machine Learning 51(3): 217\u2013238","journal-title":"Machine Learning"},{"key":"3_CR12","unstructured":"Chi-Jen Lu, Shi-Chun Tsai & Hsin-Lung Wu (2007). On the Complexity of Hard-Core Set Constructions. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming, 183\u2013194."},{"issue":"10","key":"3_CR13","doi-asserted-by":"crossref","first-page":"4575","DOI":"10.1109\/TIT.2008.928988","volume":"54","author":"Chi-Jen Lu","year":"2008","unstructured":"Lu Chi-Jen, TsaiShi-Chun. Wu Hsin-Lung (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":"3_CR14","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.jcss.2004.01.001","volume":"69","author":"Ryan O\u2019Donnell","year":"2004","unstructured":"O\u2019Donnell Ryan (2004) Hardness amplification within NP. Journal of Computer System Sciences 69(1): 68\u201394","journal-title":"Journal of Computer System Sciences"},{"issue":"12","key":"3_CR15","first-page":"1980","volume":"1","author":"Gilles Pisier","year":"1981","unstructured":"Pisier Gilles (1981) Remarques sur un resultat non publi\u00e9 de B. Maurey. Seminaire Analyse fonctionnelle 1(12): 1980\u20131981","journal-title":"Maurey. Seminaire Analyse fonctionnelle"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Ronen Shaltiel, Emanuele Viola (2008). Hardness amplification proofs require majority. In Proceedings of the 40th annual ACM symposium on Theory of computing, 589\u2013598.","DOI":"10.1145\/1374376.1374461"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Roman Smolensky (1987). Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the 19th annual ACM symposium on Theory of computing, 77\u201382.","DOI":"10.1145\/28395.28404"},{"issue":"2","key":"3_CR18","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1006\/jcss.2000.1730","volume":"62","author":"Madhu Sudan","year":"2001","unstructured":"Sudan Madhu, Trevisan Luca, Vadhan Salil (2001) Pseudorandom generators without the XOR lemma. Journal of Computer System Sciences 62(2): 236\u2013266","journal-title":"Journal of Computer System Sciences"},{"key":"3_CR19","unstructured":"M\u00e1ri\u00f3 Szegedy (1989). Algebraic methods in lower bounds for computational models with limited communication. Ph.D. thesis."},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"Jun Tarui (1991). Degree complexity of Boolean functions and its applications to relativized separations. In Proceedings of the 6th Annual IEEE Conference on Structure in Complexity Theory, 382\u2013390.","DOI":"10.1109\/SCT.1991.160282"},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"Luca Trevisan (2003). List-Decoding Using The XOR Lemma. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 126\u2013135.","DOI":"10.1109\/SFCS.2003.1238187"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"Luca Trevisan (2005). On uniform amplification of hardness in NP. In Proceedings of the 37th ACM Symposium on Theory of Computing, 31\u201338.","DOI":"10.1145\/1060590.1060595"},{"key":"3_CR23","first-page":"436","volume":"48","author":"P\u00e1l Tur\u00e1n","year":"1941","unstructured":"Tur\u00e1n P\u00e1l (1941) On an extremal problem in graph theory. Matematikai \u00e9s Fizikai Lapok 48: 436\u2013452","journal-title":"Matematikai \u00e9s Fizikai Lapok"},{"key":"3_CR24","unstructured":"Emanuele Viola (2006). The complexity of hardness amplification and derandomization. Ph.D. thesis."},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"Andrew C. Yao (1982). Theory and application of trapdoor functions. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 80\u201391.","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0003-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-011-0003-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0003-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T03:46:10Z","timestamp":1560138370000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-011-0003-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["3"],"URL":"https:\/\/doi.org\/10.1007\/s00037-011-0003-7","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3]]}}}