Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914757958696960 |
|---|---|
| author | S., Karthik C. Marx, Dániel Pilipczuk, Marcin Souza, Uéverton |
| author_facet | S., Karthik C. Marx, Dániel Pilipczuk, Marcin Souza, Uéverton |
| contents | 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$ 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)\cdot n^{o(k/\log k)}$ time (assuming the ETH). The purpose of this note is to give a streamlined proof of this result. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_05913 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof S., Karthik C. Marx, Dániel Pilipczuk, Marcin Souza, Uéverton Computational Complexity Data Structures and Algorithms 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$ 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)\cdot n^{o(k/\log k)}$ time (assuming the ETH). The purpose of this note is to give a streamlined proof of this result. |
| title | Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2311.05913 |