{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:46:56Z","timestamp":1781077616208,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","funder":[{"name":"NSF (National Science Foundation)","award":["CCF-2228287, CCF-2211972, CCF-2145474"],"award-info":[{"award-number":["CCF-2228287, CCF-2211972, CCF-2145474"]}]},{"name":"Simons Institute for the Theory of Computing, University of California Berkeley","award":["Simons Investigator Award"],"award-info":[{"award-number":["Simons Investigator Award"]}]},{"name":"Alfred P. Sloan Foundation","award":["Sloan Research Fellowship"],"award-info":[{"award-number":["Sloan Research Fellowship"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718130","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"2136-2144","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7926-3396","authenticated-orcid":false,"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[{"name":"University of California at Berkeley, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3444-6380","authenticated-orcid":false,"given":"Bingkai","family":"Lin","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5450-3446","authenticated-orcid":false,"given":"Xuandi","family":"Ren","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0370-1676","authenticated-orcid":false,"given":"Yican","family":"Sun","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-7464-2071","authenticated-orcid":false,"given":"Kewen","family":"Wu","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01277956"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.82"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.1997.1472"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780631"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446810"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9889-1"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.74"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCSS.2006.04.007"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","unstructured":"Yijia Chen Yi Feng Bundit Laekhanukit and Yanlin Liu. 2025. Simple Combinatorial Construction of the k^o(1)-Lower Bound for Approximating the Parameterized k-Clique. 263\u2013280. https:\/\/doi.org\/10.1137\/1.9781611978315.21 arxiv:https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1.9781611978315.21. 10.1137\/1.9781611978315.21","DOI":"10.1137\/1.9781611978315.21"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.42"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.CH112"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2018.36"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"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.3390\/a13060146"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X"},{"key":"e_1_3_2_1_19_1","unstructured":"Venkatesan Guruswami Bingkai Lin Xuandi Ren Yican Sun and Kewen Wu. 2024. Almost Optimal Time Lower Bound for Approximating Parameterized Clique CSP and More under ETH. arxiv:2404.08870. arxiv:2404.08870"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649771"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2024.27"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/261342.571216"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2022.6"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335315"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451016"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.90"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00025"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.134"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.5"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4086\/TOC.2010.V006A005"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734042"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","unstructured":"Karthik C. S. D\u00e1niel Marx Marcin Pilipczuk and U\u00e9verton Souza. 2024. Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof. 383\u2013395. https:\/\/doi.org\/10.1137\/1.9781611977936.35 arxiv:https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1.9781611977936.35. 10.1137\/1.9781611977936.35","DOI":"10.1137\/1.9781611977936.35"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718130","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:39:39Z","timestamp":1750693179000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718130"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":35,"alternative-id":["10.1145\/3717823.3718130","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718130","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}