Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
arxiv(2024)
摘要
The Parameterized Inapproximability Hypothesis (PIH), which is an analog of
the PCP theorem in parameterized complexity, asserts that, there is a constant
ε> 0 such that for any computable function
f:ℕ→ℕ, no f(k)· n^O(1)-time algorithm can, on
input a k-variable CSP instance with domain size n, find an assignment
satisfying 1-ε fraction of the constraints. A recent work by
Guruswami, Lin, Ren, Sun, and Wu (STOC'24) established PIH under the
Exponential Time Hypothesis (ETH).
In this work, we improve the quantitative aspects of PIH and prove (under
ETH) that approximating sparse parameterized CSPs within a constant factor
requires n^k^1-o(1) time. This immediately implies that, assuming ETH,
finding a (k/2)-clique in an n-vertex graph with a k-clique requires
n^k^1-o(1) time. We also prove almost optimal time lower bounds for
approximating k-ExactCover and Max k-Coverage.
Our proof follows the blueprint of the previous work to identify a
"vector-structured" ETH-hard CSP whose satisfiability can be checked via an
appropriate form of "parallel" PCP. Using further ideas in the reduction, we
guarantee additional structures for constraints in the CSP. We then leverage
this to design a parallel PCP of almost linear size based on Reed-Muller codes
and derandomized low degree testing.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要