Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

DOI10.4230/LIPIcs.ICALP.2018.17zbMath1499.68150arXiv1803.09717OpenAlexW2963364229MaRDI QIDQ5002683

Suprovat Ghoshal, Arnab Bhattacharyya, Pasin Manurangsi, C. S. Karthik

Publication date: 28 July 2021

Full work available at URL: https://arxiv.org/abs/1803.09717

zbMATH Keywords

shortest vector problem inapproximability parameterized complexity minimum distance problem even set problem Gap-ETH

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (4)

On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic ⋮ Imperfect gaps in Gap-ETH and PCPs ⋮ Parameterized complexity of small weight automorphisms and isomorphisms ⋮ To close is easier than to open: dual parameterization to \(k\)-median

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Fundamentals of parameterized complexity
Parameterized complexity of generalized domination problems
The LLL algorithm. Survey and applications
Factoring polynomials with rational coefficients
The hardness of approximate optima in lattices, codes, and systems of linear equations
Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
Approximating CVP to within almost-polynomial factors is NP-hard
Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
Lattice problems and norm embeddings
A Deterministic Reduction for the Gap Minimum Distance Problem
Integer Programming with a Fixed Number of Variables
Hardness of approximating the shortest vector problem in lattices
New lattice based cryptographic constructions
Lattice-based Cryptography
On the inherent intractability of certain coding problems (Corresp.)
The intractability of computing the minimum distance of a code
The hardness of the closest vector problem with preprocessing
On the hardness of learning sparse parities
Hardness of approximating the minimum distance of a linear code
The Parametrized Complexity of Some Fundamental Problems in Coding Theory
Parameterized Algorithms
Lattice-Based Cryptography
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
On lattices, learning with errors, random linear codes, and cryptography

This page was built for publication: Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH