Parameterized Intractability of Even Set and Shortest Vector Problem

DOI10.1145/3444942zbMath1499.68149arXiv1909.01986OpenAlexW2977536198MaRDI QIDQ5056405

Bingkai Lin, Édouard Bonnet, László Egri, Dániel Marx, Pasin Manurangsi, Suprovat Ghoshal, Karthik C. S., Arnab Bhattacharyya

Publication date: 8 December 2022

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

shortest vector probleminapproximabilityparameterized complexityeven setminimum distance problem

Mathematics Subject Classification ID

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

Related Items (1)

Parameterized complexity of small weight automorphisms and isomorphisms

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