CISPA
Browse
cispa_all_3626.pdf (930.28 kB)

Parameterized Intractability of Even Set and Shortest Vector Problem

Download (930.28 kB)
journal contribution
posted on 2023-11-29, 18:06 authored by Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, C. S. Karthik, Bingkai Lin, Pasin Manurangsi, Dániel MarxDániel Marx
The -Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over , which can be stated as follows: given a generator matrix and an integer , determine whether the code generated by has distance at most , or, in other words, whether there is a nonzero vector such that has at most nonzero coordinates. The question of whether -Even Set is fixed parameter tractable (FPT) parameterized by the distance has been repeatedly raised in the literature; in fact, it is one of the few remaining open questions from the seminal book of Downey and Fellows [1999]. In this work, we show that -Even Set is W[1]-hard under randomized reductions. We also consider the parameterized -Shortest Vector Problem (SVP), in which we are given a lattice whose basis vectors are integral and an integer , and the goal is to determine whether the norm of the shortest vector (in the norm for some fixed ) is at most . Similar to -Even Set, understanding the complexity of this problem is also a long-standing open question in the field of Parameterized Complexity. We show that, for any , -SVP is W[1]-hard to approximate (under randomized reductions) to some constant factor.

History

Preferred Citation

Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, C. Karthik, Bingkai Lin, Pasin Manurangsi and Dániel Marx. Parameterized Intractability of Even Set and Shortest Vector Problem. In: Journal of the ACM. 2021.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Legacy Posted Date

2022-04-29

Journal

Journal of the ACM

Pages

1 - 40

Open Access Type

  • Gold

Sub Type

  • Article

BibTeX

@article{cispa_all_3626, title = "Parameterized Intractability of Even Set and Shortest Vector Problem", author = "Bhattacharyya, Arnab and Bonnet, Édouard and Egri, László and Ghoshal, Suprovat and Karthik, C. S. and Lin, Bingkai and Manurangsi, Pasin and Marx, Dániel", journal="{Journal of the ACM}", year="2021", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC