{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:51:06Z","timestamp":1781077866986,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":67,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"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":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384283","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"1335-1348","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Sharp threshold results for computational complexity"],"prefix":"10.1145","author":[{"given":"Lijie","family":"Chen","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ce","family":"Jin","sequence":"additional","affiliation":[{"name":"Tsinghua University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R. Ryan","family":"Williams","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490272"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2017.11"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.8"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897653"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2018.35"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/050628994"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3349616"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0124-0"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706594"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89575"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Noga Alon Raphael Yuster and Uri Zwick. 1995. Color-coding. JACM 42 4 ( 1995 ) 844-856.  Noga Alon Raphael Yuster and Uri Zwick. 1995. Color-coding. JACM 42 4 ( 1995 ) 844-856.","DOI":"10.1145\/210332.210337"},{"key":"e_1_3_2_1_12_1","volume-title":"Computational Complexity-A Modern Approach","author":"Arora Sanjeev","unstructured":"Sanjeev Arora and Boaz Barak . 2009. Computational Complexity-A Modern Approach . Cambridge University Press . http:\/\/www.cambridge.org\/catalogue\/ catalogue.asp?isbn= 9780521424264 Sanjeev Arora and Boaz Barak. 2009. Computational Complexity-A Modern Approach. Cambridge University Press. http:\/\/www.cambridge.org\/catalogue\/ catalogue.asp?isbn= 9780521424264"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2018.12"},{"key":"e_1_3_2_1_16_1","article-title":"Universal classes of hash functions","volume":"18","author":"Lawrence Carter J.","year":"1979","unstructured":"J. Lawrence Carter and Mark N. Wegman . 1979 . Universal classes of hash functions . J. Comput. System Sci. 18 , 2 ( 1979 ), 143-154. J. Lawrence Carter and Mark N. Wegman. 1979. Universal classes of hash functions. J. Comput. System Sci. 18, 2 ( 1979 ), 143-154.","journal-title":"J. Comput. System Sci."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.1"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.70"},{"key":"e_1_3_2_1_19_1","first-page":"1240","article-title":"Hardness Magnification for all Sparse NP Languages","author":"Chen Lijie","year":"2019","unstructured":"Lijie Chen , Ce Jin , and Ryan Williams . 2019 . Hardness Magnification for all Sparse NP Languages . In FOCS. 1240 - 1255 . Lijie Chen, Ce Jin, and Ryan Williams. 2019. Hardness Magnification for all Sparse NP Languages. In FOCS. 1240-1255.","journal-title":"FOCS."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2019.30"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316333"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2016.1"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.39"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.19"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268765"},{"key":"e_1_3_2_1_26_1","volume-title":"Computational complexity-a conceptual perspective","author":"Goldreich Oded","unstructured":"Oded Goldreich . 2008. Computational complexity-a conceptual perspective . Cambridge University Press . Oded Goldreich. 2008. Computational complexity-a conceptual perspective. Cambridge University Press."},{"key":"e_1_3_2_1_27_1","volume-title":"Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation","author":"Goldreich Oded","year":"2000","unstructured":"Oded Goldreich , Salil Vadhan , and Avi Wigderson . 2011. Simplified derandomization of BPP using a hitting set generator . In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation . Springer , 59-67. Preliminary version in ECCC, TR00-004, 2000 . Oded Goldreich, Salil Vadhan, and Avi Wigderson. 2011. Simplified derandomization of BPP using a hitting set generator. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. Springer, 59-67. Preliminary version in ECCC, TR00-004, 2000."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591808"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261556"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00032"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2018.5"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2017.7"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2016.18"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2015.236"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230630"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792282965"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45687-2_29"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335314"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1048045"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380832"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80060-1"},{"key":"e_1_3_2_1_43_1","first-page":"168","article-title":"Improved Two-Source Extractors, and Afine Extractors for Polylogarithmic Entropy","author":"Li Xin","year":"2016","unstructured":"Xin Li . 2016 . Improved Two-Source Extractors, and Afine Extractors for Polylogarithmic Entropy . In FOCS. 168 - 177 . Xin Li. 2016. Improved Two-Source Extractors, and Afine Extractors for Polylogarithmic Entropy. In FOCS. 168-177.","journal-title":"FOCS."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0069-5"},{"key":"e_1_3_2_1_45_1","first-page":"734","article-title":"Simple strategies for large zero-sum games with applications to complexity theory","author":"Lipton Richard J.","year":"1994","unstructured":"Richard J. Lipton and Neal E. Young . 1994 . Simple strategies for large zero-sum games with applications to complexity theory . In STOC. 734 - 740 . Richard J. Lipton and Neal E. Young. 1994. Simple strategies for large zero-sum games with applications to complexity theory. In STOC. 734-740.","journal-title":"STOC."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316396"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2019.102735"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944345.1944346"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188910"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2017.v013a004"},{"key":"e_1_3_2_1_51_1","first-page":"999","volume-title":"On a Boolean function. Doklady of the Academy of Sciences of the USSR 169, 4 ( 1966 ), 765-766. English translation in Soviet Mathematics Doklady 7 : 4","author":"Nechiporuk E. I.","unstructured":"E. I. Nechiporuk . 1966. On a Boolean function. Doklady of the Academy of Sciences of the USSR 169, 4 ( 1966 ), 765-766. English translation in Soviet Mathematics Doklady 7 : 4 , pages 999 - 1000 . E. I. Nechiporuk. 1966. On a Boolean function. Doklady of the Academy of Sciences of the USSR 169, 4 ( 1966 ), 765-766. English translation in Soviet Mathematics Doklady 7 : 4, pages 999-1000."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.32"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2019.27"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00016"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556668"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00110-7"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.65"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188822"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-019-00179-2"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.1984.10036"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"crossref","unstructured":"Salil P. Vadhan. 2012. Pseudorandomness. Foundations and Trends\u00ae in Theoretical Computer Science 7 1-3 ( 2012 ) 1-336.  Salil P. Vadhan. 2012. Pseudorandomness. Foundations and Trends\u00ae in Theoretical Computer Science 7 1-3 ( 2012 ) 1-336.","DOI":"10.1561\/0400000010"},{"key":"e_1_3_2_1_65_1","volume-title":"The Complexity of Boolean Functions","author":"Wegener Ingo","unstructured":"Ingo Wegener . 1987. The Complexity of Boolean Functions . John Wiley & Sons Ltd . Ingo Wegener. 1987. The Complexity of Boolean Functions. John Wiley & Sons Ltd."},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/10080703X"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559903"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384283","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384283","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384283"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":67,"alternative-id":["10.1145\/3357713.3384283","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384283","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}