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

DOI10.1137/23M1573021MaRDI QIDQ6621748zbMATH OpenFDO

Authors Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João L. Ribeiro

Publication date 21 October 2024

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/23M1573021

zbMATH Keywords

approximationminimum distance problemparameterized hardnessshortest vector problem

Mathematics Subject Classification ID

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

Cites work

• (Gap/S)ETH hardness of SVP
• A birthday repetition theorem and complexity of approximating dense CSPs
• A Deterministic Reduction for the Gap Minimum Distance Problem
• A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
• Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
• Fundamentals of parameterized complexity
• Hardness of approximating the minimum distance of a linear code
• Hardness of approximating the shortest vector problem in lattices
• scientific article; zbMATH DE number 3147923 (Why is no real title available?)
• scientific article; zbMATH DE number 1775383 (Why is no real title available?)
• scientific article; zbMATH DE number 7829251 (Why is no real title available?)
• scientific article; zbMATH DE number 7788447 (Why is no real title available?)
• 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 algorithms
• Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
• Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all _p norms
• Parameterized Intractability of Even Set and Shortest Vector Problem
• Parameterized intractability of even set and shortest vector problem from Gap-ETH
• PRIMES is in P
• Tensor-based hardness of the shortest vector problem to within almost polynomial factors
• 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 Parametrized Complexity of Some Fundamental Problems in Coding Theory
• 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 Q6621748)