Constant approximating k-clique is w [1]-hard
B Lin - Proceedings of the 53rd Annual ACM SIGACT …, 2021 - dl.acm.org
For every graph G, let ω (G) be the largest size of complete subgraph in G. This paper
presents a simple algorithm which, on input a graph G, a positive integer k and a small …
presents a simple algorithm which, on input a graph G, a positive integer k and a small …
Almost polynomial factor inapproximability for parameterized k-clique
CS Karthik, S Khot - 37th Computational Complexity Conference …, 2022 - drops.dagstuhl.de
The k-Clique problem is a canonical hard problem in parameterized complexity. In this
paper, we study the parameterized complexity of approximating the k-Clique problem where …
paper, we study the parameterized complexity of approximating the k-Clique problem where …
Baby pih: Parameterized inapproximability of min csp
V Guruswami, X Ren, S Sandeep - arXiv preprint arXiv:2310.16344, 2023 - arxiv.org
The Parameterized Inapproximability Hypothesis (PIH) is the analog of the PCP theorem in
the world of parameterized complexity. It asserts that no FPT algorithm can distinguish a …
the world of parameterized complexity. It asserts that no FPT algorithm can distinguish a …
Constant Approximating Parameterized k-SETCOVER is W[2]-hard
In this paper, we prove that it is W [2]-hard to approximate k-SETCOVER within any constant
ratio. Our proof is built upon the recently developed threshold graph composition technique …
ratio. Our proof is built upon the recently developed threshold graph composition technique …
[PDF][PDF] Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter
tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the …
tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the …
Parameterized Inapproximability Hypothesis under ETH
The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter
tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the …
tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the …
Superpolynomial lower bounds for decision tree learning and testing
We establish new hardness results for decision tree optimization problems, adding to a line
of work that dates back to Hyafil and Rivest in 1976. We prove, under the randomized …
of work that dates back to Hyafil and Rivest in 1976. We prove, under the randomized …
Applications of random algebraic constructions to hardness of approximation
In this paper, we show how one may (efficiently) construct two types of extremal
combinatorial objects whose existence was previously conjectural.• Panchromatic Graphs …
combinatorial objects whose existence was previously conjectural.• Panchromatic Graphs …
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
Abstract Parameterized Inapproximability Hypothesis (PIH) is a central question in the field
of parameterized complexity. PIH asserts that given as input a 2-CSP on k variables and …
of parameterized complexity. PIH asserts that given as input a 2-CSP on k variables and …
Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH
S Li, B Lin, Y Liu - arXiv preprint arXiv:2402.09825, 2024 - arxiv.org
In this paper we present a new gap-creating randomized self-reduction for parameterized
Maximum Likelihood Decoding problem over $\mathbb {F} _p $($ k $-MLD $ _p $). The …
Maximum Likelihood Decoding problem over $\mathbb {F} _p $($ k $-MLD $ _p $). The …