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

arXiv: https://arxiv.org/abs/2311.05913 · HTML: https://mlsanity.com/paper/2311.05913/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2023.

## Built on by (most cited first, 1 of 1)

- [Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy](https://mlsanity.com/paper/2511.08091/) (2025)

## Abstract (arXiv)

Assuming the Exponential Time Hypothesis (ETH), a result of Marx (ToC'10) implies that there is no f(k)· no(k/log k) 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 f(k)· no(k/log k) time (assuming the ETH). The purpose of this note is to give a streamlined proof of this result.