{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T06:21:05Z","timestamp":1775024465738,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":85,"publisher":"ACM","funder":[{"name":"National Science Foundation","award":["2227876, 2239160, 2313372, 2443697"],"award-info":[{"award-number":["2227876, 2239160, 2313372, 2443697"]}]},{"name":"Simons Foundation","award":["825876"],"award-info":[{"award-number":["825876"]}]},{"name":"Ministry of Education and Science of Bulgaria","award":[""],"award-info":[{"award-number":[""]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718257","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"2118-2129","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Near Optimal Constant Inapproximability under ETH for Fundamental Problems in Parameterized Complexity"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3003-2017","authenticated-orcid":false,"given":"Mitali","family":"Bafna","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9105-364X","authenticated-orcid":false,"family":"Karthik C. S.","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8093-1328","authenticated-orcid":false,"given":"Dor","family":"Minzer","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00021"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00008-4"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225140"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374380"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451099"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00059"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649714"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718197"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133077"},{"key":"e_1_3_2_1_12_1","volume-title":"Rounding semidefinite programming hierarchies via global correlation. In 2011 ieee 52nd annual symposium on foundations of computer science. 472\u2013481","author":"Barak Boaz","unstructured":"Boaz Barak, Prasad Raghavendra, and David Steurer. 2011. Rounding semidefinite programming hierarchies via global correlation. In 2011 ieee 52nd annual symposium on foundations of computer science. 472\u2013481."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10072"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646445"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780631"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585214"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3444942"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.17"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00032"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1166869"},{"key":"e_1_3_2_1_21_1","unstructured":"Michael Chapman and Alexander Lubotzky. 2023. Stability of Homomorphisms Coverings and Cocycles II: Examples Applications and Open problems. arXiv preprint arXiv:2311.06706."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","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. In SOSA.","DOI":"10.1137\/1.9781611978315.21"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1127211"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447584"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00580-x"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.42"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/080730160"},{"key":"e_1_3_2_1_28_1","unstructured":"Konrad K Dabrowski Peter Jonsson Sebastian Ordyniak George Osipov and Magnus Wahlstroem. 2024. Towards a Parameterized Approximation Dichotomy of MinCSP for Linear Equations over Finite Commutative Rings. arXiv preprint arXiv:2410.09932."},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. 747\u2013754","author":"W","unstructured":"W Fernandez de la Vega, Marek Karpinski, Ravi Kannan, and Santosh Vempala. 2005. Tensor decomposition and approximation schemes for constraint satisfaction problems. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. 747\u2013754."},{"key":"e_1_3_2_1_30_1","volume-title":"Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. 53\u201361","author":"Wenceslas","unstructured":"Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu. 2007. Linear programming relaxations of maxcut. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. 53\u201361."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649685"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649780"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2402.01078"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_3_2_1_35_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. Electronic Colloquium on Computational Complexity (ECCC), 23 (2016), 128. http:\/\/eccc.hpi-web.de\/report\/2016\/128","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/100788161"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2018.36"},{"key":"e_1_3_2_1_38_1","unstructured":"Ilan Doron-Arad Ariel Kulik and Pasin Manurangsi. 2024. Fine Grained Lower Bounds for Multidimensional Knapsack. arXiv preprint arXiv:2407.10146."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.3390\/a13060146"},{"key":"e_1_3_2_1_41_1","volume-title":"33rd Symposium on Theoretical Aspects of Computer Science (STACS","author":"Fotakis Dimitris","year":"2016","unstructured":"Dimitris Fotakis, Michail Lampis, and Vangelis Paschos. 2016. Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). 37\u20131."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548459"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Venkatesan Guruswami Bingkai Lin Xuandi Ren Yican Sun and Kewen Wu. 2024. Parameterized Inapproximability Hypothesis under ETH. In STOC.","DOI":"10.1145\/3618260.3649771"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718130"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2024.27"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.36"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2009.v005a008"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00048"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451126"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536458"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.6"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.123"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3325116"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.IPEC.2024.6"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977936.35"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.24"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2024.107"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212622"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.81"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451016"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2022.90"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.CH126"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00025"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS.2025.65"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.134"},{"key":"e_1_3_2_1_68_1","volume-title":"Approximation and Hardness: Beyond P and NP","author":"Manurangsi Pasin","unstructured":"Pasin Manurangsi. 2019. Approximation and Hardness: Beyond P and NP. University of California, Berkeley."},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.5"},{"key":"e_1_3_2_1_70_1","unstructured":"Pasin Manurangsi and Dana Moshkovitz. 2015. Approximating Dense Max 2-CSPs. Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques 396."},{"key":"e_1_3_2_1_71_1","volume-title":"A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. CoRR, abs\/1607.02986","author":"Manurangsi Pasin","year":"2016","unstructured":"Pasin Manurangsi and Prasad Raghavendra. 2016. A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. CoRR, abs\/1607.02986 (2016), arxiv:1607.02986. arxiv:1607.02986"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.4086\/TOC.2010.V006A005"},{"key":"e_1_3_2_1_73_1","volume-title":"Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms. 176\u2013182","author":"Mathieu Claire","year":"2008","unstructured":"Claire Mathieu and Warren Schudy. 2008. Yet another algorithm for dense max cut: go greedy. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms. 176\u2013182."},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754402"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-023-01205-0"},{"key":"e_1_3_2_1_76_1","volume-title":"International Workshop on Approximation Algorithms for Combinatorial Optimization. 303\u2013316","author":"Gharan Shayan Oveis","year":"2013","unstructured":"Shayan Oveis Gharan and Luca Trevisan. 2013. A new regularity lemma and faster approximation algorithms for low threshold rank graphs. In International Workshop on Approximation Algorithms for Combinatorial Optimization. 303\u2013316."},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195132"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734042"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2015.17"},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2016.3"},{"key":"e_1_3_2_1_82_1","first-page":"3431","article-title":"ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY","volume":"3","author":"Williams Virginia Vassilevska","year":"2018","unstructured":"Virginia Vassilevska Williams. 2018. ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY. In Proc. Int. Cong. of Math.. 3, 3431\u20133472.","journal-title":"Proc. Int. Cong. of Math.."},{"key":"e_1_3_2_1_83_1","volume-title":"Inapproximability within W[1]: the case of Steiner Orientation. CoRR, abs\/1907.06529","author":"Wlodarczyk Michal","year":"2019","unstructured":"Michal Wlodarczyk. 2019. Inapproximability within W[1]: the case of Steiner Orientation. CoRR, abs\/1907.06529 (2019), arxiv:1907.06529. arxiv:1907.06529"},{"key":"e_1_3_2_1_84_1","unstructured":"Grigory Yaroslavtsev. 2014. Going for speed: Sublinear algorithms for dense r-CSPs. arXiv preprint arXiv:1407.7887."},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554836"}],"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.3718257","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:46:49Z","timestamp":1750693609000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718257"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":85,"alternative-id":["10.1145\/3717823.3718257","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718257","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"}}]}}