{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T11:41:57Z","timestamp":1787312517052,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"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":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451016","type":"proceedings-article","created":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T21:26:13Z","timestamp":1623792373000},"page":"1749-1756","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Constant approximating k-clique is w[1]-hard"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3444-6380","authenticated-orcid":false,"given":"Bingkai","family":"Lin","sequence":"first","affiliation":[{"name":"Nanjing University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"On the parameterized complexity of k-SUM. CoRR, abs\/1311.3054","author":"Abboud Amir","year":"2013","unstructured":"Amir Abboud, Kevin Lewi, and Ryan Williams. 2013. On the parameterized complexity of k-SUM. CoRR, abs\/1311.3054, 2013."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167174"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195129"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9889-1"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.74"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_10"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1127211"},{"key":"e_1_3_2_1_12_1","unstructured":"Irit Dinur. 2016. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover.. In Electronic Colloquium on Computational Complexity (ECCC). 23"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Rodney G Downey and Michael R Fellows. 1999. Parameterized Complexity. Springer-Verlag.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_3_2_1_15_1","volume-title":"Fundamentals of parameterized complexity. 4","author":"Downey Rodney G","unstructured":"Rodney G Downey and Michael R Fellows. 2013. Fundamentals of parameterized complexity. 4, Springer."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797325375"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.3390\/a13060146"},{"key":"e_1_3_2_1_19_1","unstructured":"Michael R Fellows Jiong Guo D\u00e1niel Marx and Saket Saurabh. [n.d.]. Data reductions and problem kernels. In Dahstuhl Seminar."},{"key":"e_1_3_2_1_20_1","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer."},{"key":"e_1_3_2_1_21_1","volume-title":"Lecture Notes on Linearity","author":"Goldreich Oded","year":"2016","unstructured":"Oded Goldreich. 2016. Lecture Notes on Linearity (Group Homomorphism) Testing. 2016."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/SMJCAT000027000003000737000001"},{"key":"e_1_3_2_1_23_1","unstructured":"M. T. Hajiaghayi R. Khandekar and G. Kortsarz. 2013. Fixed Parameter Inapproximability for Clique and SetCover in Time Super-exponential in OPT. CoRR abs\/1310.2711 2013."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548522"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_1_26_1","volume-title":"Extremal combinatorics: with applications in computer science","author":"Jukna Stasys","unstructured":"Stasys Jukna. 2011. Extremal combinatorics: with applications in computer science. Springer Science & Business Media."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_1_28_1","volume-title":"SOSA","author":"Karthik C.S.","year":"2021","unstructured":"C.S. Karthik and Inbal Livni-Navon. 2021. On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes. SOSA, 2021."},{"key":"e_1_3_2_1_29_1","volume-title":"Solvability of systems of polynomial equations over finite fields. A talk given by Neeraj Kayal at the Simons Institute for the Theory of Computing","author":"Kayal Neeraj","year":"2017","unstructured":"Neeraj Kayal. 2014. Solvability of systems of polynomial equations over finite fields. A talk given by Neeraj Kayal at the Simons Institute for the Theory of Computing, Berkeley, CA [Accessed: 2017\/20\/7], 2014. Pages 1."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840733"},{"key":"e_1_3_2_1_31_1","first-page":"5","article-title":"On the Parameterized Complexity of Approximating Dominating Set","volume":"66","author":"Laekhanukit Bundit","year":"2019","unstructured":"Bundit Laekhanukit, C.S. Karthik, and Pasin Manurangsi. 2019. On the Parameterized Complexity of Approximating Dominating Set. Journal of the ACM (JACM), 66, 5, 2019. Pages 33.","journal-title":"Journal of the ACM (JACM)"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212622"},{"key":"e_1_3_2_1_33_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Lin Bingkai","year":"2019","unstructured":"Bingkai Lin. 2019. A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.134"},{"key":"e_1_3_2_1_35_1","volume-title":"A birthday repetition theorem and complexity of approximating dense CSPs. arXiv preprint arXiv:1607.02986","author":"Manurangsi Pasin","year":"2016","unstructured":"Pasin Manurangsi and Prasad Raghavendra. 2016. A birthday repetition theorem and complexity of approximating dense CSPs. arXiv preprint arXiv:1607.02986, 2016."},{"key":"e_1_3_2_1_36_1","first-page":"1","article-title":"Parameterized complexity and approximation algorithms","volume":"51","author":"Marx D\u00e1niel","year":"2008","unstructured":"D\u00e1niel Marx. 2008. Parameterized complexity and approximation algorithms. Comput. J., 51, 1, 2008. Pages 60\u201378.","journal-title":"Comput. J."},{"key":"e_1_3_2_1_37_1","volume-title":"47th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Micha\u0142 W\u0142","year":"2020","unstructured":"Micha\u0142 W\u0142 odarczyk. 2020. Parameterized Inapproximability for Steiner Orientation by Gap Amplification. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132612"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451016","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451016","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:01:44Z","timestamp":1750183304000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451016"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":38,"alternative-id":["10.1145\/3406325.3451016","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451016","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}