Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all _p norms
From MaRDI portal
Publication:6499250
Cites work
- scientific article; zbMATH DE number 3147923 (Why is no real title available?)
- scientific article; zbMATH DE number 1335879 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 1775383 (Why is no real title available?)
- (Gap/S)ETH hardness of SVP
- A Deterministic Reduction for the Gap Minimum Distance Problem
- A Lower Bound on List Size for List Decoding
- A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
- A birthday repetition theorem and complexity of approximating dense CSPs
- Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
- Discrete Gaussian sampling reduces to CVP and SVP
- Fundamentals of parameterized complexity
- Hardness of approximating the minimum distance of a linear code
- Hardness of approximating the shortest vector problem in lattices
- Inapproximability of the shortest vector problem: toward a deterministic reduction
- Lattice problems and norm embeddings
- On a class of error correcting binary group codes
- On the inherent intractability of certain coding problems (Corresp.)
- Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
- Parameterized Intractability of Even Set and Shortest Vector Problem
- Parameterized algorithms
- Parameterized intractability of even set and shortest vector problem from Gap-ETH
- Tensor-based hardness of the shortest vector problem to within almost polynomial factors
- The Parametrized Complexity of Some Fundamental Problems in Coding Theory
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- The intractability of computing the minimum distance of a code
- The parameterized complexity of the \(k\)-biclique problem
- The shortest vector in a lattice is hard to approximate to within some constant
- Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
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)
