The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter
tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the …

Computational problems on point lattices play a central role in many areas of computer
science including integer programming, coding theory, cryptanalysis, and especially the …

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 …

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 …

$\newcommand {\NP}{\mathsf {NP}}\newcommand {\GapSVP}{\textrm {GapSVP}} $ We give
a simple proof that the (approximate, decisional) Shortest Vector Problem is $\NP $-hard …

We connect the problem of properly PAC learning decision trees to the parameterized
Nearest Codeword Problem (k-NCP). Despite significant effort by the respective …

Abstract The Gap Exponential Time Hypothesis rules out FPT algorithms providing (nearly)
tight inapproximability results for a host of fundamental problems in parameterized …

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 …