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

Karthik C. S., Dániel Marx, Marcin Pilipczuk +1

Assuming the Exponential Time Hypothesis (ETH), a result of Marx (ToC'10) implies that there is no $f(k)\cdot n^{o(k/\log k)}$ time algorithm that can solve 2-CSPs with $k$ constra…