{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T18:25:20Z","timestamp":1765045520589,"version":"build-2065373602"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"5","funder":[{"name":"NSF","award":["CCF-2228287 and CCF-2211972"],"award-info":[{"award-number":["CCF-2228287 and CCF-2211972"]}]},{"name":"NSF CAREER","award":["CCF-2145474"],"award-info":[{"award-number":["CCF-2145474"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2025,10,31]]},"abstract":"<jats:p>The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the number of variables, from one where every assignment fails to satisfy an \u025b fraction of constraints for some absolute constant \u025b &gt; 0. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under the Gap Exponential Time Hypothesis (ETH), a very strong assumption with an inherent gap.<\/jats:p>\n          <jats:p>In this work, we prove PIH under the ETH. This is the first proof of PIH from a gap-free assumption. Our proof is self-contained and elementary. We identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a \u201cparallel PCP of proximity\u201d based on the Walsh-Hadamard code.<\/jats:p>","DOI":"10.1145\/3749982","type":"journal-article","created":{"date-parts":[[2025,7,26]],"date-time":"2025-07-26T11:09:17Z","timestamp":1753528157000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Parameterized Inapproximability Hypothesis under ETH"],"prefix":"10.1145","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7926-3396","authenticated-orcid":false,"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[{"name":"University of California Berkeley","place":["Berkeley, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3444-6380","authenticated-orcid":false,"given":"Bingkai","family":"Lin","sequence":"additional","affiliation":[{"name":"Nanjing University","place":["Nanjing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5450-3446","authenticated-orcid":false,"given":"Xuandi","family":"Ren","sequence":"additional","affiliation":[{"name":"University of California Berkeley","place":["Berkeley, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0370-1676","authenticated-orcid":false,"given":"Yican","family":"Sun","sequence":"additional","affiliation":[{"name":"Peking University","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5894-822X","authenticated-orcid":false,"given":"Kewen","family":"Wu","sequence":"additional","affiliation":[{"name":"University of California Berkeley","place":["Berkeley, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","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. In 64th IEEE Annual Symposium on Foundations of Computer Science FOCS 2023 Santa Cruz CA USA November 6-9 2023. IEEE 1377\u20131399. 10.1109\/FOCS57990.2023.00085","DOI":"10.1109\/FOCS57990.2023.00085"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1171321"},{"key":"e_1_3_3_4_2","doi-asserted-by":"crossref","first-page":"836","DOI":"10.1109\/FOCS.2017.82","volume-title":"2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Applebaum Benny","year":"2017","unstructured":"Benny Applebaum. 2017. Exponentially-hard gap-csp and local PRG via local hardcore functions. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 836\u2013847."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.1997.1472"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446810"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585214"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3444942"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00032"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2981561"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_6"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1166869"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1882"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978315.21"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/070687153"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1127211"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03898-8_11"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.42"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.14"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_3_3_26_2","unstructured":"Irit Dinur. 2016. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Technical Report TR16-128. https:\/\/eccc.weizmann.ac.il\/report\/2016\/128"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374418"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2018.36"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446962"},{"key":"e_1_3_3_30_2","first-page":"624","volume-title":"Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014","author":"Dinur I.","year":"2014","unstructured":"I. Dinur and D. Steurer. 2014. Analytical approach to parallel repetition. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014. 624\u2013633."},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792228228"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.3390\/a13060146"},{"key":"e_1_3_3_36_2","first-page":"1","volume-title":"Graph-Theoretic Concepts in Computer Science: 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers 29","author":"Fellows Michael R.","year":"2003","unstructured":"Michael R. Fellows. 2003. Blow-ups, win\/win\u2019s, and crown rules: Some new directions in FPT. In Graph-Theoretic Concepts in Computer Science: 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers 29. Springer, 1\u201312."},{"key":"e_1_3_3_37_2","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","year":"2006","unstructured":"J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer."},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108135252"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1137\/090778274"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0993"},{"key":"e_1_3_3_41_2","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1109\/FOCS.2018.00020","volume-title":"2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Gupta Anupam","year":"2018","unstructured":"Anupam Gupta, Euiwoong Lee, and Jason Li. 2018. Faster exact and approximate algorithms for k-cut. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 113\u2013123."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175483"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","unstructured":"Venkatesan Guruswami Bingkai Lin Xuandi Ren Yican Sun and Kewen Wu. 2025. Almost optimal time lower bound for approximating parameterized clique CSP and more under ETH. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing STOC 2025 Prague Czechia June 23-27 2025 Michal Kouck\u00fd and Nikhil Bansal (Eds.). ACM 2136\u20132144. 10.1145\/3717823.3718130","DOI":"10.1145\/3717823.3718130"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649771"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2020.34"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","unstructured":"Venkatesan Guruswami Xuandi Ren and Sai Sandeep. 2024. Baby PIH: Parameterized inapproximability of Min CSP. In 39th Computational Complexity Conference CCC 2024 July 22-25 2024 Ann Arbor MI USA (LIPIcs) Rahul Santhanam (Ed.). Vol. 300. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik 27:1\u201327:17. 10.4230\/LIPICS.CCC.2024.27","DOI":"10.4230\/LIPICS.CCC.2024.27"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/261342.571216"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.2000.1727"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.003"},{"key":"e_1_3_3_51_2","volume-title":"37th Computational Complexity Conference (CCC 2022)","volume":"234","author":"S. Karthik C.","year":"2022","unstructured":"Karthik C. S. and Subhash Khot. 2022. Almost polynomial factor inapproximability for parameterized k-clique. In 37th Computational Complexity Conference (CCC 2022), Vol. 234."},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3325116"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.24"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335315"},{"key":"e_1_3_3_55_2","doi-asserted-by":"crossref","first-page":"990","DOI":"10.1137\/1.9781611975994.59","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Kawarabayashi Ken-ichi","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. SIAM, 990\u2013999."},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1255-7"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1137\/130938645"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/3212622"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.81"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451016"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.90"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch126"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","unstructured":"Bingkai Lin Xuandi Ren Yican Sun and Xiuhan Wang. 2023. Improved hardness of approximating k-clique under ETH. In 64th IEEE Annual Symposium on Foundations of Computer Science FOCS 2023 Santa Cruz CA USA November 6-9 2023. IEEE 285\u2013306. 10.1109\/FOCS57990.2023.00025","DOI":"10.1109\/FOCS57990.2023.00025"},{"key":"e_1_3_3_64_2","first-page":"2181","volume-title":"Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020","author":"Lokshtanov Daniel","year":"2020","unstructured":"Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. 2020. Parameterized complexity and approximability of directed odd cycle transversal. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, Shuchi Chawla (Ed.). SIAM, 2181\u20132200."},{"key":"e_1_3_3_65_2","first-page":"798","volume-title":"61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020","author":"Lokshtanov Daniel","year":"2020","unstructured":"Daniel Lokshtanov, Saket Saurabh, and Vaishali Surianarayanan. 2020. A parameterized approximation scheme for min k-cut. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, Sandy Irani (Ed.). IEEE, 798\u2013809."},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.4230\/OASIcs.SOSA.2019.15"},{"key":"e_1_3_3_67_2","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1137\/1.9781611975994.5","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Manurangsi Pasin","year":"2020","unstructured":"Pasin Manurangsi. 2020. Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 62\u201381."},{"key":"e_1_3_3_68_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm048"},{"key":"e_1_3_3_69_2","volume-title":"33rd International Symposium on Algorithms and Computation (ISAAC 2022)","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). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.1137\/080734042"},{"key":"e_1_3_3_71_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5628"},{"key":"e_1_3_3_72_2","doi-asserted-by":"publisher","unstructured":"Craig A. Tovey. 1984. A simplified NP-complete satisfiability problem. Discret. Appl. Math. 8 1 (1984) 85\u201389. 10.1016\/0166-218X(84)90081-7","DOI":"10.1016\/0166-218X(84)90081-7"},{"key":"e_1_3_3_73_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2018.28"},{"key":"e_1_3_3_74_2","volume-title":"47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)","author":"W\u0142odarczyk Micha\u0142","year":"2020","unstructured":"Micha\u0142 W\u0142odarczyk. 2020. Parameterized inapproximability for steiner orientation by gap amplification. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3749982","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T13:38:12Z","timestamp":1760017092000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3749982"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,9]]},"references-count":73,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,10,31]]}},"alternative-id":["10.1145\/3749982"],"URL":"https:\/\/doi.org\/10.1145\/3749982","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2025,10,9]]},"assertion":[{"value":"2024-12-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-29","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}