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.
SIAM Symposium on Simplicity in Algorithms (SOSA)
2024-01-08
2024-09-27