A survey on approximation in parameterized complexity: Hardness and algorithms
Parameterization and approximation are two popular ways of coping with NP-hard
problems. More recently, the two have also been combined to derive many interesting …
problems. More recently, the two have also been combined to derive many interesting …
Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing …
P Manurangsi - Proceedings of the Fourteenth Annual ACM-SIAM …, 2020 - SIAM
We show, assuming the (randomized) Gap Exponential Time Hypothesis (Gap-ETH), that
the following tasks cannot be done in T (k)· N o (k)-time for any function T where N denote …
the following tasks cannot be done in T (k)· N o (k)-time for any function T where N denote …
FPT-approximation for FPT problems
Over the past decade, many results have focused on the design of parameterized
approximation algorithms for W [1]-hard problems. However, there are fundamental …
approximation algorithms for W [1]-hard problems. However, there are fundamental …
The complexity of adversarially robust proper learning of halfspaces with agnostic noise
I Diakonikolas, DM Kane… - Advances in Neural …, 2020 - proceedings.neurips.cc
We study the computational complexity of adversarially robust proper learning of halfspaces
in the distribution-independent agnostic PAC model, with a focus on $ L_p $ perturbations …
in the distribution-independent agnostic PAC model, with a focus on $ L_p $ perturbations …
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 …
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms
We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite
field and parameterized by the input distance bound is W [1]-hard to approximate within any …
field and parameterized by the input distance bound is W [1]-hard to approximate within any …
The complexity of the shortest vector problem
H Bennett - ACM SIGACT News, 2023 - dl.acm.org
Computational problems on point lattices play a central role in many areas of computer
science including integer programming, coding theory, cryptanalysis, and especially the …
science including integer programming, coding theory, cryptanalysis, and especially the …
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 …
Hardness of the (approximate) shortest vector problem: A simple proof via reed-solomon codes
$\newcommand {\NP}{\mathsf {NP}}\newcommand {\GapSVP}{\textrm {GapSVP}} $ We give
a simple proof that the (approximate, decisional) Shortest Vector Problem is $\NP $-hard …
a simple proof that the (approximate, decisional) Shortest Vector Problem is $\NP $-hard …