Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all _p norms

Cites Work

Fundamentals of parameterized complexity
Title not available (Why is that?)
On a class of error correcting binary group codes
The intractability of computing the minimum distance of a code
Parameterized algorithms
On the inherent intractability of certain coding problems (Corresp.)
Hardness of approximating the minimum distance of a linear code
Lattice problems and norm embeddings
Title not available (Why is that?)
A Deterministic Reduction for the Gap Minimum Distance Problem
Title not available (Why is that?)
The Parametrized Complexity of Some Fundamental Problems in Coding Theory
The hardness of approximate optima in lattices, codes, and systems of linear equations
The shortest vector in a lattice is hard to approximate to within some constant
Title not available (Why is that?)
Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
Hardness of approximating the shortest vector problem in lattices
A Lower Bound on List Size for List Decoding
Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
A birthday repetition theorem and complexity of approximating dense CSPs
The parameterized complexity of the \(k\)-biclique problem
(Gap/S)ETH hardness of SVP
Parameterized intractability of even set and shortest vector problem from Gap-ETH
Parameterized Intractability of Even Set and Shortest Vector Problem
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
Inapproximability of the shortest vector problem: toward a deterministic reduction
Tensor-based hardness of the shortest vector problem to within almost polynomial factors
Discrete Gaussian sampling reduces to CVP and SVP

Cited In (1)

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 Q6499250)