Near Optimal Constant Inapproximability under ETH for Fundamental Problems in Parameterized Complexity
Open Access
- 15 June 2025
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 2118-2129
Abstract
No abstract availableFunding Information
- National Science Foundation (2227876, 2239160, 2313372, 2443697)
- Simons Foundation (825876)
- Ministry of Education and Science of Bulgaria ()
This publication has 56 references indexed in Scilit:
- On the Parameterized Intractability of Determinant MaximizationAlgorithmica, 2024
- Applications of Random Algebraic Constructions to Hardness of Approximation2022
- Unique Decoding of Explicit $\varepsilon$-balanced Codes Near the Gilbert-Varshamov Bound2020
- Approximating Constraint Satisfaction Problems on High-Dimensional Expanders2019
- A Tight Lower Bound for Planar Steiner OrientationAlgorithmica, 2019
- Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives2011
- Random sampling and approximation of MAX-CSPsJournal of Computer and System Sciences, 2003
- Polynomial time approximation schemes for dense instances of minimum constraint satisfactionRandom Structures & Algorithms, 2003
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001