{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:54:14Z","timestamp":1725490454602},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540734192"},{"type":"electronic","value":"9783540734208"}],"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-73420-8_18","type":"book-chapter","created":{"date-parts":[[2007,8,25]],"date-time":"2007-08-25T10:58:43Z","timestamp":1188039523000},"page":"183-194","source":"Crossref","is-referenced-by-count":6,"title":["On the Complexity of Hard-Core Set Constructions"],"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":"18_CR1","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"The probabilistic method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.: The probabilistic method, 2nd edn. Wiley-Interscience, New York (2000)","edition":"2"},{"issue":"4","key":"18_CR2","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":"18_CR3","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/BF01200426","volume":"2","author":"M. Goldmann","year":"1992","unstructured":"Goldmann, M., H\u00e5stad, J., Razborov, A.: Majority gates vs. general weighted threshold gates. Computational Complexity\u00a02, 277\u2013300 (1992)","journal-title":"Computational Complexity"},{"doi-asserted-by":"crossref","unstructured":"Hajnal, A., Maass, W., Pudl\u00e1k, P., Szegedy, M., Tur\u00e1n, G.: Threshold circuits of bounded depth. In: Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, pp. 99\u2013110 (1987)","key":"18_CR4","DOI":"10.1109\/SFCS.1987.59"},{"issue":"4","key":"18_CR5","doi-asserted-by":"publisher","first-page":"903","DOI":"10.1137\/S0097539705447281","volume":"35","author":"A. Healy","year":"2006","unstructured":"Healy, A., Vadhan, S., Viola, E.: Using nondeterminism to amplify hardness. SIAM Journal on Computing\u00a035(4), 903\u2013931 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR6","first-page":"664","volume-title":"Proceedings of the 37th ACM Symposium on Theory of Computing","author":"T. Holenstein","year":"2005","unstructured":"Holenstein, T.: Key agreement from weak bit agreement. In: Proceedings of the 37th ACM Symposium on Theory of Computing, pp. 664\u2013673. ACM Press, New York (2005)"},{"key":"18_CR7","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":"18_CR8","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)"},{"issue":"3","key":"18_CR9","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1023\/A:1022949332276","volume":"51","author":"A. Klivans","year":"2003","unstructured":"Klivans, A., Servedio, R.A.: Boosting and hard-core sets. Machine Learning\u00a051(3), 217\u2013238 (2003)","journal-title":"Machine Learning"},{"key":"18_CR10","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":"18_CR11","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)"},{"issue":"2","key":"18_CR12","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":"18_CR13","first-page":"77","volume-title":"Proceedings of the 19th ACM Symposium on Theory of Computing","author":"R. Smolensky","year":"1987","unstructured":"Smolensky, R.: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In: Proceedings of the 19th ACM Symposium on Theory of Computing, pp. 77\u201382. ACM Press, New York (1987)"},{"unstructured":"Szegedy, M.: Algebraic methods in lower bounds for computational models with limited communication. Ph.D. thesis, University of Chicago (1989)","key":"18_CR14"},{"key":"18_CR15","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1109\/SCT.1991.160282","volume-title":"Proceedings of the 6th Annual IEEE Conference on Structure in Complexity Theory","author":"J. Tarui","year":"1991","unstructured":"Tarui, J.: Degree complexity of boolean functions and its applications to relativized separations. In: Proceedings of the 6th Annual IEEE Conference on Structure in Complexity Theory, pp. 382\u2013390. IEEE Computer Society Press, Los Alamitos (1991)"},{"key":"18_CR16","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1109\/SFCS.2003.1238187","volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science","author":"L. Trevisan","year":"2003","unstructured":"Trevisan, L.: List decoding using the XOR lemma. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 126\u2013135. IEEE Computer Society Press, Los Alamitos (2003)"},{"key":"18_CR17","first-page":"31","volume-title":"Proceedings of the 37th ACM Symposium on Theory of Computing","author":"L. Trevisan","year":"2005","unstructured":"Trevisan, L.: On uniform amplification of hardness in NP. In: Proceedings of the 37th ACM Symposium on Theory of Computing, pp. 31\u201338. ACM Press, New York (2005)"},{"unstructured":"Viola, E.: The Complexity of Hardness Amplification and Derandomization. Ph.D. thesis, Harvard University (2006)","key":"18_CR18"},{"key":"18_CR19","first-page":"80","volume-title":"Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science","author":"A. Yao","year":"1982","unstructured":"Yao, A.: 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","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73420-8_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T10:26:06Z","timestamp":1558261566000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73420-8_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540734192","9783540734208"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73420-8_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}