Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
C. S. Karthik, Dániel Marx, Marcin Pilipczuk, Uéverton S. Souza · Society for Industrial and Applied Mathematics eBooks · 2024
Assuming the Exponential Time Hypothesis (ETH), a result of Marx (ToC’10) implies that there is no time algorithm that can solve 2-CSPs with k constraints (over a domain of arbitrary large size n) for any computable function f. This lower bound is widely used to show that certain parameterized problems cannot be solved in time time (assuming the ETH). The purpose of this note is to give a streamlined proof of this result.