{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:37:04Z","timestamp":1750307824516,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":65,"publisher":"ACM","license":[{"start":{"date-parts":[[2008,5,17]],"date-time":"2008-05-17T00:00:00Z","timestamp":1210982400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2008,5,17]]},"DOI":"10.1145\/1374376.1374461","type":"proceedings-article","created":{"date-parts":[[2008,5,28]],"date-time":"2008-05-28T16:50:20Z","timestamp":1211993420000},"page":"589-598","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Hardness amplification proofs require majority"],"prefix":"10.1145","author":[{"given":"Ronen","family":"Shaltiel","sequence":"first","affiliation":[{"name":"University of Haifa, Haifa, Israel"}]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}]}],"member":"320","published-online":{"date-parts":[[2008,5,17]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/646839.708669"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"e_1_3_2_1_3_1","first-page":"1","volume-title":"NJ, 1990)","author":"Ajtai M.","year":"1993","unstructured":"M. Ajtai . Approximate counting with uniform constant-depth circuits. In Advances in computational complexity theory (New Brunswick , NJ, 1990) , pages 1 -- 20 . Amer. Math. Soc., Providence, RI , 1993 .]] M. Ajtai. Approximate counting with uniform constant-depth circuits. In Advances in computational complexity theory (New Brunswick, NJ, 1990), pages 1--20. Amer. Math. Soc., Providence, RI, 1993.]]"},{"key":"e_1_3_2_1_4_1","first-page":"184","volume-title":"Proceedings of the Sixteenth Annual Conference on Computational Complexity","author":"Alon N.","year":"2001","unstructured":"N. Alon and R. Beigel . Lower bounds for approximations by low degree polynomials over $z_m$ . In Proceedings of the Sixteenth Annual Conference on Computational Complexity , pages 184 -- 187 . IEEE, June 18 --21 2001 .]] N. Alon and R. Beigel. Lower bounds for approximations by low degree polynomials over $z_m$. In Proceedings of the Sixteenth Annual Conference on Computational Complexity, pages 184--187. IEEE, June 18--21 2001.]]"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215346"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/90326.90342"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000004"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446974"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2005.03.008"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1764891.1764903"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00171-T"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-001-8195-x"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01262928"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/552556"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250855"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.17"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2005.07.011"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11682462_52"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90001-D"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28629-5_24"},{"key":"e_1_3_2_1_27_1","volume-title":"Computational limitations of small-depth circuits","author":"J.","year":"1987","unstructured":"J. H\\rastad. Computational limitations of small-depth circuits . MIT Press , 1987 .]] J. H\\rastad. Computational limitations of small-depth circuits. MIT Press, 1987.]]"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01272517"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447281"},{"key":"e_1_3_2_1_30_1","volume-title":"20th Annual Conference on Computational Complexity, June 12--15","author":"IEEE.","year":"2005","unstructured":"IEEE. Proceedings of the 20th Annual Conference on Computational Complexity, June 12--15 2005 .]] IEEE. Proceedings of the 20th Annual Conference on Computational Complexity, June 12--15 2005.]]"},{"key":"e_1_3_2_1_31_1","volume-title":"22nd Annual Conference on Computational Complexity, June 13--16","author":"IEEE.","year":"2007","unstructured":"IEEE. Proceedings of the 22nd Annual Conference on Computational Complexity, June 13--16 2007 .]] IEEE. Proceedings of the 22nd Annual Conference on Computational Complexity, June 13--16 2007.]]"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796290"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.13"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374460"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1780"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022949332276"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/646977.759877"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30576-7_3"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/002\/13"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.17"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/2391495.2391532"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.10.009"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"C.-J.\n      Lu S.-C.\n      Tsai and \n      H.-L.\n      Wu\n    .\n  On the complexity of hard-core set constructions\n  . In L. Arge C. Cachin T. Jurdzinski and A. Tarlecki editors ICALP volume \n  4596\n   of \n  Lecture Notes in Computer Science pages \n  183\n  --\n  194\n  . \n  Springer 2007\n  .]]   C.-J. Lu S.-C. Tsai and H.-L. Wu. On the complexity of hard-core set constructions. In L. Arge C. Cachin T. Jurdzinski and A. Tarlecki editors ICALP volume 4596 of Lecture Notes in Computer Science pages 183--194. Springer 2007.]]","DOI":"10.1007\/978-3-540-73420-8_18"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/972639.972643"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.01.001"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"issue":"4","key":"e_1_3_2_1_49_1","first-page":"598","article-title":"Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function","volume":"41","author":"Razborov A. A.","year":"1987","unstructured":"A. A. Razborov . Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function . Mat. Zametki , 41 ( 4 ): 598 -- 607 , 623, 1987 .]] A. A. Razborov. Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Mat. Zametki, 41(4):598--607, 623, 1987.]]","journal-title":"Mat. Zametki"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059516"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0218-9"},{"key":"e_1_3_2_1_53_1","volume-title":"Unpublished manuscript","author":"Shaltiel R.","year":"2005","unstructured":"R. Shaltiel , E. Viola , and A. Wigderson . Unpublished manuscript , 2005 .]] R. Shaltiel, E. Viola, and A. Wigderson. Unpublished manuscript, 2005.]]"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946354"},{"key":"e_1_3_2_1_57_1","series-title":"Quad","first-page":"347","volume-title":"Complexity of computations and proofs","author":"Trevisan L.","year":"2004","unstructured":"L. Trevisan . Some applications of coding theory in computational complexity. In Complexity of computations and proofs , volume 13 of Quad . Mat., pages 347 -- 424 . Dept. Math., Seconda Univ. Napoli , Caserta, 2004 .]] L. Trevisan. Some applications of coding theory in computational complexity. In Complexity of computations and proofs, volume 13 of Quad. Mat., pages 347--424. Dept. Math., Seconda Univ. Napoli, Caserta, 2004.]]"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060595"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0233-x"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0187-1"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.16"},{"key":"e_1_3_2_1_62_1","volume-title":"Harvard University","author":"Viola E.","year":"2006","unstructured":"E. Viola . The Complexity of Hardness Amplification and Derandomization. PhD thesis , Harvard University , 2006 . http:\/\/www.eccc.uni-trier.de\/.]] E. Viola. The Complexity of Hardness Amplification and Derandomization. PhD thesis, Harvard University, 2006. http:\/\/www.eccc.uni-trier.de\/.]]"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.16"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.15"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.95"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.49"}],"event":{"name":"STOC '08: Symposium on Theory of Computing","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Victoria British Columbia Canada","acronym":"STOC '08"},"container-title":["Proceedings of the fortieth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1374376.1374461","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1374376.1374461","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:49Z","timestamp":1750255069000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1374376.1374461"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5,17]]},"references-count":65,"alternative-id":["10.1145\/1374376.1374461","10.1145\/1374376"],"URL":"https:\/\/doi.org\/10.1145\/1374376.1374461","relation":{},"subject":[],"published":{"date-parts":[[2008,5,17]]},"assertion":[{"value":"2008-05-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}