{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T02:26:27Z","timestamp":1787279187697,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":66,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"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":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649771","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"24-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis"],"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, 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, 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\/0000-0002-5894-822X","authenticated-orcid":false,"given":"Kewen","family":"Wu","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Fateme Abbasi Sandip Banerjee Jaroslaw Byrka Parinya Chalermsook Ameet Gadekar Kamyar Khodamoradi D\u00e1niel Marx Roohani Sharma and Joachim Spoerhase. 2023. Parameterized Approximation Schemes for Clustering with General Norm Objectives. FOCS.","DOI":"10.1109\/FOCS57990.2023.00085"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1171321"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.82"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.1997.1472"},{"key":"e_1_3_2_1_5_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. isbn:978-0-521-42426-4 http:\/\/www.cambridge.org\/catalogue\/catalogue.asp?isbn=9780521424264"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446810"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585214"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3444942"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00032"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2981561"},{"key":"e_1_3_2_1_15_1","volume-title":"The Complexity of Satisfiability of Small Depth Circuits","author":"Calabro Chris","unstructured":"Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. 2009. The Complexity of Satisfiability of Small Depth Circuits. In Parameterized and Exact Computation, Jianer Chen and Fedor V. Fomin (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 75\u201385. isbn:978-3-642-11269-0"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.74"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1882"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2304.07516"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/070687153"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1127211"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.42"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.14"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_3_2_1_24_1","first-page":"128","article-title":"Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover","volume":"23","author":"Dinur Irit","year":"2016","unstructured":"Irit Dinur. 2016. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electron. Colloquium Comput. Complex., 23 (2016), 128.","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374418"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2018.36"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446962"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792228228"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.3390\/a13060146"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39890-5_1"},{"key":"e_1_3_2_1_34_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_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/090778274"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00020"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.179"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Venkatesan Guruswami Bingkai Lin Xuandi Ren Yican Sun and Kewen Wu. 2023. Parameterized Inapproximability Hypothesis under ETH. arxiv:2311.16587.","DOI":"10.1145\/3618260.3649771"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX"},{"key":"e_1_3_2_1_41_1","unstructured":"Venkatesan Guruswami Xuandi Ren and Sai Sandeep. 2023. Baby PIH: Parameterized Inapproximability of Min CSP. arXiv preprint arXiv:2310.16344."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.003"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.6"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3325116"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.24"},{"key":"e_1_3_2_1_48_1","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. 990\u2013999","author":"Bingkai Lin Kawarabayashi","year":"2020","unstructured":"Ken-ichi Kawarabayashi and Bingkai Lin. 2020. A nearly 5\/3-approximation FPT Algorithm for Min-k-Cut. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. 990\u2013999."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1255-7"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938645"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212622"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.81"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451016"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.90"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch126"},{"key":"e_1_3_2_1_56_1","unstructured":"Bingkai Lin Xuandi Ren Yican Sun and Xiuhan Wang. 2023. Improved Hardness of Approximating k-Clique under ETH. FOCS."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.134"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00079"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.4230\/OASIcs.SOSA.2019.15"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.5"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl"},{"key":"e_1_3_2_1_62_1","volume-title":"On the Parameterized Intractability of Determinant Maximization. In 33rd International Symposium on Algorithms and Computation (ISAAC","author":"Ohsaka Naoto","year":"2022","unstructured":"Naoto Ohsaka. 2022. On the Parameterized Intractability of Determinant Maximization. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022)."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5628"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90081-7"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2018.28"},{"key":"e_1_3_2_1_66_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)."}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649771","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649771","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:52Z","timestamp":1750291432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649771"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":66,"alternative-id":["10.1145\/3618260.3649771","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649771","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}