Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof

Summary

Abstract 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.