Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all \(\ell_{p}\) norms

Linear codes (general theory) (94B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Fundamentals of parameterized complexity
The hardness of approximate optima in lattices, codes, and systems of linear equations
Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
PRIMES is in P
The shortest vector in a lattice is hard to approximate to within some constant
Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
Lattice problems and norm embeddings
A Deterministic Reduction for the Gap Minimum Distance Problem
On a class of error correcting binary group codes
Hardness of approximating the shortest vector problem in lattices
On the inherent intractability of certain coding problems (Corresp.)
The intractability of computing the minimum distance of a code
The Parameterized Complexity of the k -Biclique Problem
Hardness of approximating the minimum distance of a linear code
The Parametrized Complexity of Some Fundamental Problems in Coding Theory
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH
Parameterized Intractability of Even Set and Shortest Vector Problem
Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
(Gap/S)ETH hardness of SVP
Parameterized Algorithms
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all \(\ell_p\) norms

This page was built for publication: Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all \(\ell_{p}\) norms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6621748)