Pith. sign in

REVIEW 4 major objections 5 minor 55 references

Parameterized Intractability of Even Set and Shortest Vector Problem

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that $k$-Even Set and $k$-Shortest Vector Problem are $\mathrm{W}[1]$-hard to approximate under randomized reductions, closing two open questions from the founding book of parameterized complexity unless…

desk verdict Resolves two long-standing parameterized open questions with a careful reduction chain; one missing padding argument in Theorem 4.2 should be fixed but looks easily repairable. read the letter →

arxiv 1909.01986 v1 pith:H3IRMDTX submitted 2019-09-04 cs.CC

Arnab Bhattacharyya , Édouard Bonnet , László Egri , Suprovat Ghoshal , Karthik C. S. , Bingkai Lin , Pasin Manurangsi , Dániel Marx This is my paper · ORCID
classification cs.CC MSC 68Q1768Q2794B0511H06
keywords parameterizedcomplexityW[1]-hardnessminimumdistanceproblemk-EvenSetshortestvectorlocallysuffixdensecodesnearestcodewordrandomizedreductions
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to settle two long-open questions from the founding book of parameterized complexity: whether the $k$-Even Set problem (deciding if a binary linear code has distance at most $k$) and the $k$-Shortest Vector Problem in $\ell_p$ lattices admit fixed-parameter tractable algorithms. Its answer, under the standard hypothesis $\mathrm{W}[1] \neq \mathrm{FPT}$ and using randomized reductions, is no. Specifically, it proves that the gap version of $k$-Even Set is $\mathrm{W}[1]$-hard for every constant approximation factor $\gamma \ge 1$, and that $k$-SVP in $\ell_p$ for any $p>1$ is $\mathrm{W}[1]$-hard to approximate to some constant factor depending on $p$. A sympathetic reader should care because these were among the few remaining open questions from the original 1999 agenda of the field, and $\mathrm{W}[1]$-hardness means no $f(k)\cdot \mathrm{poly}(n)$ algorithm exists unless the parameterized hierarchy collapses.

What carries the argument

The argument is carried by a chain of gap-retaining reductions anchored in $\mathrm{W}[1]$-hardness of approximating the One-Sided Biclique problem. Three objects do the heavy lifting. The first is a Vandermonde embedding of the vertices of a bipartite graph into vectors over a large field: it turns a graph with a planted complete bipartite subgraph into a set of field vectors with a small linearly dependent subset, while sparse linear dependencies in the NO case force dense subgraphs. The second is the locally suffix dense code (LSDC), a systematic binary linear code near the sphere-packing bound whose restriction to any affine subspace with a short prefix is dense; a random suffix lands close to some codeword with probability $d^{-\Theta(d)}$, and this lets the DMS gadget reduction work with a distance that depends only on the parameter $k$ rather than on the input length. The third is the BCH lattice gadget, an integer lattice built from BCH codes, together with a random homogeneous linear constraint that annihilates the unwanted short vectors in NO instances of the nearest-vector problem while preserving a witness in YES instances.

What would settle it

Locate the 'without loss of generality' sentence in the proof of Theorem 4.2 and attempt to make the padding explicit. If there is a value of $k$ for which no polynomial-time transformation preserves the parameter and satisfies both $6 \mid k+1$ and $\lceil n/6^{k+6}\rceil > (k+6)!\,(\gamma k^2)^{k^2}$, then the $\mathrm{W}[1]$-hardness of $\mathrm{GAPBSMD}$, and with it the Even Set chain, is not established by this proof.

Watch

Extended reading notes

Core claim

The central claim is a pair of $\mathrm{W}[1]$-hardness results proved through one interconnected reduction chain. For the coding side, the paper shows that $\mathrm{GAPMDP}_\gamma$, the promise version of $k$-Even Set (equivalently, Minimum Distance of a binary linear code), is $\mathrm{W}[1]$-hard under randomized reductions for every constant $\gamma \ge 1$: it is hard to distinguish a code of distance at most $k$ from one of distance greater than $\gamma k$. For the lattice side, it shows that $\mathrm{GAPSVP}_{p,\gamma_p}$, the gap version of $k$-SVP in the $\ell_p$ norm, is $\mathrm{W}[1]$-hard under randomized reductions for every $p>1$ with some constant $\gamma_p>1$ depending only on $p$. These two results are obtained by first proving constant-factor $\mathrm{W}[1]$-hardness for the inhomogeneous problems $k$-Nearest Codeword and $k$-Nearest Vector, then reducing those to the homogeneous forms using locally suffix dense codes and a BCH lattice construction respectively. If $\mathrm{W}[1] \neq \mathrm{FPT}$, neither problem has a fixed-parameter algorithm even when the allowed approximation gap is a constant.

Load-bearing premise

The load-bearing premise is that any $k$-Clique instance can be padded, with the parameter $k$ essentially unchanged, so that $6 \mid k+1$ and the input size satisfies a certain largeness inequality; the paper states this as 'without loss of generality' but does not give the padding construction.

Editorial extensions

If this is right

  • If $\mathrm{W}[1] \neq \mathrm{FPT}$, no fixed-parameter algorithm can approximate $k$-Even Set to any constant factor; even the promise version separating distance $\le k$ from distance $>\gamma k$ is hard for every $\gamma \ge 1$.
  • If $\mathrm{W}[1] \neq \mathrm{FPT}$, no fixed-parameter algorithm can approximate $k$-Shortest Vector Problem in the $\ell_p$ norm for any $p>1$ to within the constant $\gamma_p$ established in the paper.
  • The same chain makes the intermediate problems $k$-Nearest Codeword, $k$-Nearest Vector, $k$-Linear Dependent Set, and $k$-Odd Set $\mathrm{W}[1]$-hard to approximate to constant factors, going beyond the exact $\mathrm{W}[1]$-hardness previously known for the first two.
  • Because the reductions are randomized one-sided error FPT reductions, the hardness is conditional not only on $\mathrm{W}[1] \neq \mathrm{FPT}$ but on the availability of randomized reductions; a deterministic version remains open.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Extension: if a field analogue of the LSDC exists over $\mathbb{F}_p$ for fixed $p>2$, the same reduction would likely make $k$-MDP over that field $\mathrm{W}[1]$-hard; the paper explicitly leaves this open, so searching for such codes near the sphere-packing bound is a concrete next step.
  • Extension: because the paper cannot amplify the $k$-SVP gap when $p \neq 2$, a norm-preserving tensor construction for $\ell_p$ lattices would upgrade its single-constant hardness to every constant factor; this is not attempted in the paper.
  • Extension: the constant-factor hardness of $\mathrm{GAPMLD}$ over every fixed prime field may transfer to other parameterized linear-algebraic problems such as syndrome decoding; this connection is not explored in the paper.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper proves W[1]-hardness, under randomized reductions, of the gap versions of the parameterized Minimum Distance Problem over F2 (k-Even Set) for every constant approximation factor, and of the parameterized Shortest Vector Problem in the l_p norm for every p > 1 up to some constant factor. The proof is a chain of fixed-parameter reductions starting from Lin's W[1]-hardness for gap k-Biclique, passing through a newly introduced Bipartite Subgraph with Minimum Degree problem (GAPBSMD), gap Linear Dependent Set (GAPLDS), colored GAPLDS, gap Maximum Likelihood Decoding (GAPMLD), and gap Sparse Nearest Codeword (GAPSNC). A new combinatorial object, Locally Suffix Dense Codes, is constructed from BCH codes and used to adapt the Dumer-Micciancio-Sudan reduction to the parameterized setting, with tensor products amplifying the gap. In parallel, GAPMLD over F_p is reduced to gap Nearest Vector Problem, and then Khot's BCH-lattice reduction is adapted to yield gap Shortest Vector Problem in l_p for p > 1. The main theorems (Theorem 6.1 and Theorem 7.1) would resolve two longstanding open questions of Downey and Fellows and rule out FPT approximation algorithms under the W[1] not-equal FPT hypothesis.

Significance. If the proof is correct, this is a substantial result: it settles two open questions that have been listed in Downey and Fellows' books and repeatedly restated in the parameterized complexity literature. The reduction chain is a significant technical contribution, introducing the intermediate problems GAPBSMD, GAPLDS, and GAPSNC and showing how to transplant the DMS and Khot reductions into the fixed-parameter regime. The paper is careful to state the randomized reduction model, including one-sided success probabilities, and provides detailed correctness arguments for most steps. I found no circularity: the proof starts from the standard W[1]-complete k-Clique problem and builds new gadgets inside the paper. At the same time, several load-bearing points are either asserted without proof or stated with a weaker definition than the proof actually uses; these are repairable without changing the architecture of the proof, but they need to be fixed before the results can be considered fully verified.

major comments (4)
  1. [Section 4.1, proof of Theorem 4.2] The assertion 'Without loss of generality, we can assume that 6 | k+1 and ceil(n/6^{k+6}) > (k+6)! * (gamma * k^2)^{k^2}' is load-bearing because it is exactly what allows the reduction to invoke Lin's Theorem 4.3 and to set h to the required value. No padding or parameter-adjustment argument is given. The claim is plausible and repairable: one can add at most five universal vertices to force 6 | k+1 and add isolated vertices to inflate n until the ceiling bound holds, while preserving the existence or non-existence of a k-clique in a parameter-preserving way. However, as written, this WLOG step is an unproved gap in the central reduction chain and must be spelled out explicitly.
  2. [Sections 3.5, 7.1, 7.2 (Claim 7.7)] The formal definition of GAPNVP (Section 3.5) quantifies only over x in Z^m with a fixed target vector y, but the proof of Theorem 7.2 and especially Claim 7.7 use a strictly stronger NO guarantee: that every nonzero integer multiple w*y is far from the lattice. This is not a cosmetic distinction: for a standard NVP NO instance it is possible that 2y belongs to the lattice even though y is far from it. Claim 7.7 would fail for such an instance. The proof of Theorem 7.2 actually establishes the stronger scaled property, so the fix is to either extend the GAPNVP definition to include all scalar multiples w in the NO case, or explicitly state and prove this stronger promise in Theorem 7.2 and then use it in Lemma 7.3. As written, the NVP-to-SVP step is not justified by the definitions given in the paper.
  3. [Section 4.2, proof of Theorem 4.5] In the NO case, the proof takes an arbitrary linearly dependent set W and claims that every vertex u in X has at least h neighbors in Y and every vertex v in Y has at least s neighbors in X. This is only justified for a minimal dependent set, or more precisely for the support of a linear dependence using nonzero coefficients: a non-minimal dependent set may contain a vertex whose incident vectors all receive coefficient zero, and then the degree lower bound can fail. The proof should be repaired by passing to a minimal dependent subset; the counting bound then goes through, since |W| is at least the size of that subset.
  4. [Section 4.1, Claim 4.4] The stated hypothesis h/ell >= gamma * s^s is too weak for the claimed conclusion. From |EW| >= h*(h/ell)^{1/s}, the hypothesis gives (h/ell)^{1/s} >= gamma^{1/s} * s, which yields only |EW| >= gamma^{1/s} * h * s, not |EW| >= gamma * h * s. The proof needs the stronger hypothesis h/ell >= gamma^s * s^s. The parameter choice in Theorem 4.2 does satisfy this stronger inequality, so the main theorem is not endangered, but Claim 4.4 as stated and proved is mathematically incorrect and must be corrected.
minor comments (5)
  1. [Section 7.1, proof of Theorem 7.2] The displayed construction of A' has inconsistent dimensions: the second block row should be a matrix that selects x when multiplied by x' = x o z, but the text writes 'Idn 0n×n', which does not have the required m columns. The YES-case norm expression should be for A'x' - y', not just A'x'. The line 'A′x′ + qz = w·y′' is also garbled and should read e.g. Ax + qz = w·y. These typos make this important reduction difficult to verify and should be rewritten carefully.
  2. [Section 5.2, proof of Theorem 5.4] The column vector is written as e_{c^{-1}(w)}, which is not meaningful since c maps W to [k]; it should be e_{c(w)}. In addition, the equation 'for all i in [d]' in the NO-case analysis should quantify over colors, i.e., i in [k], not over the field-extension dimension d.
  3. [Section 7.2.2, intermediate lattice] The text says 'Let h be the smallest power of 2 such that h >= max{2n, (10^10 l)^{2 eta}}', but Lemma 7.4 and the BCH construction require h+1 to be a power of two. The intended statement is presumably that h+1 is a power of two. The assumptions that l and r are integers are also made without comment; the authors should explain the choice of eta (or a scaling argument) that justifies these integrality assumptions for every p > 1.
  4. [Lemma 6.4] The statement contains a typo, 'd ∈ /C6', and the proof does not explicitly show m >= q. The claimed inequality does follow from h >= max{2q, 10 d log d}, but the verification should be included because the systematic-prefix construction needs m >= q.
  5. [Theorem 4.9 and notation] Theorem 4.9 states that the reduction outputs an instance of 'GAPLDS_γ' but the text and subsequent usage indicate that the output should be GAPLDS_col_γ. Several other notation inconsistencies (e.g., the meaning of s' in Lemma 6.5) should be cleaned up in revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the derivation chain consists of explicit reductions from Lin's independently published biclique hardness, with only a missing WLOG padding argument that is a correctness concern, not circularity.

full rationale

Walking the derivation chain from k-Clique (via [Lin18]) through GAPBSMD, GAPLDS, GAPMLD, GAPSNC, and GAPMDP, and separately through GAPNVP and GAPSVP, every step is a proved reduction with explicit completeness and soundness arguments. The load-bearing starting point, Theorem 4.3, is Bingkai Lin's published JACM theorem; although one co-author is shared with the present paper, it is an independent, externally verified result whose assumptions do not include the target claims, so it is real evidence and does not constitute circular self-citation. The reformulation of Lin's one-sided biclique guarantee as GAPBSMD is not a mere renaming: Claim 4.4 and the parameter setting in Theorem 4.2 supply the missing inference. The GAPLDS Vandermonde gadget, the color-coding merge, the GAPMLD reductions, the locally suffix dense code construction from BCH codes, and the adaptations of the DMS and Khot reductions are all constructed and verified inside the paper. The one passage that deserves a correctness flag rather than a circularity flag is the unproved WLOG in Section 4.1, where the paper states 'Without loss of generality, we can assume that 6 | k+1 and ceil(n/6^{k+6}) > (k+6)! * (gamma * k^2)^{k^2}' without giving the padding argument; this is plausibly repairable by adding a bounded number of universal and isolated vertices, but the paper should spell it out. There are also apparent typos in the matrix and parameter definitions of Theorem 7.2 (k' is set to 2k but later written as m+n). None of these issues make any claimed result equivalent to its inputs by construction, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 3 invented entities

All new mathematical objects are explicitly constructed and proved within the paper. The proof relies on standard background results (BCH codes, perfect hash families, tensor product distance) and on recent hardness results (Lin 2018, Khot 2005) that are cited and used as black boxes. No free parameters are fitted to data; all constants are derived from the input or chosen straightforwardly.

assumptions (5)
  • standard math BCH codes with parameters as in Theorem 3.8 exist and can be constructed in polynomial time (Hocquenghem 1959, Bose-Ray-Chaudhuri 1960).
    Used to construct locally suffix dense codes in Lemma 6.4 and BCH lattices in Section 7.2.1.
  • domain assumption Lin's Theorem 4.3: W[1]-hardness of approximating One-Sided Biclique, from Lin 2018.
    Starting point of the entire reduction chain; provides gap hardness of One-Sided Biclique.
  • domain assumption Khot's Lemma 4.3 (restated as Lemma 7.4): BCH lattice gadget returns a center with many good vectors.
    Key gadget for the NVP-to-SVP reduction; not proved in this paper.
  • standard math Perfect hash family construction of Naor et al. 1995 (Theorem 4.7).
    Used to color the LDS instance.
  • standard math Tensor product of codes has distance equal to the product of distances (Proposition 6.6).
    Used for gap amplification of MDP hardness.
invented entities (3)
  • Locally Suffix Dense Codes (LSDC) independent evidence
    purpose: Gadget to reduce Sparse Nearest Codeword to Minimum Distance Problem while keeping the parameter small.
    Explicit probabilistic construction from BCH codes in Lemma 6.4; existence is proved in the paper.
  • Sparse Nearest Codeword Problem (GAPSNC) independent evidence
    purpose: Intermediate promise problem bridging Gap MLD and Gap MDP.
    Defined in Section 3.4, reduced from MLD and to MDP; hardness proved in Section 6.
  • Bipartite Subgraph with Minimum Degree (BSMD) independent evidence
    purpose: Graph-theoretic intermediate to translate One-Sided Biclique hardness to Linear Dependent Set.
    Defined in Section 3.2, hardness proved in Section 4.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Parameterized Intractability of Even Set and Shortest Vector Problem." pith.science (2026). https://pith.science/paper/H3IRMDTX

@misc{pith2026190901986,
  author       = {Pith},
  title        = {Pith review of: Parameterized Intractability of Even Set and Shortest Vector Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/H3IRMDTX}},
  note         = {Machine review of arXiv:1909.01986}
}
abstract

The $k$-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb F_2$, which can be stated as follows: given a generator matrix $\mathbf A$ and an integer $k$, determine whether the code generated by $\mathbf A$ has distance at most $k$, or in other words, whether there is a nonzero vector $\mathbf{x}$ such that $\mathbf A \mathbf{x}$ has at most $k$ nonzero coordinates. The question of whether $k$-Even Set is fixed parameter tractable (FPT) parameterized by the distance $k$ has been repeatedly raised in 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 $k$-Even Set is W[1]-hard under randomized reductions. We also consider the parameterized $k$-Shortest Vector Problem (SVP), in which we are given a lattice whose basis vectors are integral and an integer $k$, and the goal is to determine whether the norm of the shortest vector (in the $\ell_p$ norm for some fixed $p$) is at most $k$. Similar to $k$-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 $p > 1$, $k$-SVP is W[1]-hard to approximate (under randomized reductions) to some constant factor.

Figures

Figures reproduced from arXiv: 1909.01986 by the authors.

Figure 1
Figure 1. The figure provides an overview of our reduction from [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. The figure provides an overview of our reduction from [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

55 extracted references · 51 canonical work pages

  1. [1]

    Sanjeev Arora, L \' a szl \' o Babai, Jacques Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci. , 54(2):317--331, 1997

    work page 1997

  2. [2]

    A public-key cryptosystem with worst-case/average-case equivalence

    Mikl \' o s Ajtai and Cynthia Dwork. A public-key cryptosystem with worst-case/average-case equivalence. In STOC , pages 284--293, 1997

    work page 1997

  3. [3]

    Generating hard instances of lattice problems (extended abstract)

    Mikl \' o s Ajtai. Generating hard instances of lattice problems (extended abstract). In STOC , pages 99--108, 1996

    work page 1996

  4. [4]

    The shortest vector problem in _2 is NP -hard for randomized reductions (extended abstract)

    Mikl \' o s Ajtai. The shortest vector problem in _2 is NP -hard for randomized reductions (extended abstract). In STOC , pages 10--19, 1998

    work page 1998

  5. [5]

    A simple deterministic reduction for the gap minimum distance of code problem

    Per Austrin and Subhash Khot. A simple deterministic reduction for the gap minimum distance of code problem. IEEE Trans. Information Theory , 60(10):6636--6645, 2014

    work page 2014

  6. [6]

    (gap/s)eth hardness of SVP

    Divesh Aggarwal and Noah Stephens - Davidowitz. (gap/s)eth hardness of SVP . In STOC , pages 228--238, 2018

    work page 2018

  7. [7]

    On the hardness of learning sparse parities

    Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, and Rishi Saket. On the hardness of learning sparse parities. In ESA , pages 11:1--11:17, 2016

    work page 2016

  8. [8]

    On the quantitative hardness of CVP

    Huck Bennett, Alexander Golovnev, and Noah Stephens - Davidowitz. On the quantitative hardness of CVP . In FOCS , pages 13--24, 2017

    work page 2017

Show all 55 references
  1. [9]

    Berlekamp, Robert J

    Elwyn R. Berlekamp, Robert J. McEliece, and Henk C. A. van Tilborg. On the inherent intractability of certain coding problems (corresp.). IEEE Trans. Information Theory , 24(3):384--386, 1978

    1978

  2. [10]

    R. C. Bose and Dwijendra K. Ray - Chaudhuri. On a class of error correcting binary group codes. Information and Control , 3(1):68--79, 1960

    1960

  3. [11]

    Fomin, Danny Hermelin, and Magnus Wahlstr \" o m

    Marek Cygan, Fedor V. Fomin, Danny Hermelin, and Magnus Wahlstr \" o m. Randomization in parameterized complexity (dagstuhl seminar 17041). Dagstuhl Reports , 7(1):103--128, 2017

    2017

  4. [12]

    Open problems for fpt school 2014

    Marek Cygan, Fedor Fomin, Bart MP Jansen, Lukasz Kowalik, Daniel Lokshtanov, D \'a niel Marx, Marcin Pilipczuk, and Saket Saurabh. Open problems for fpt school 2014. 2014

    2014

  5. [13]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms . Springer, 2015

    2015

  6. [14]

    Approximating the SVP to within a factor (1+1/ dim ^ ) is NP -hard under randomized reductions

    Jin - yi Cai and Ajay Nerurkar. Approximating the SVP to within a factor (1+1/ dim ^ ) is NP -hard under randomized reductions. J. Comput. Syst. Sci. , 59(2):221--239, 1999

    1999

  7. [15]

    A deterministic reduction for the gap minimum distance problem

    Qi Cheng and Daqing Wan. A deterministic reduction for the gap minimum distance problem. IEEE Trans. Information Theory , 58(11):6935--6941, 2012

    2012

  8. [16]

    Downey and Michael R

    Rodney G. Downey and Michael R. Fellows. Parameterized Complexity . Monographs in Computer Science. Springer, 1999

    1999

  9. [17]

    Downey and Michael R

    Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity . Texts in Computer Science. Springer, 2013

    2013

  10. [18]

    Downey, Michael R

    Rodney G. Downey, Michael R. Fellows, Alexander Vardy, and Geoff Whittle. The parametrized complexity of some fundamental problems in coding theory. SIAM J. Comput. , 29(2):545--570, 1999

    1999

  11. [19]

    Demaine, Gregory Gutin, D \' a niel Marx, and Ulrike Stege

    Erik D. Demaine, Gregory Gutin, D \' a niel Marx, and Ulrike Stege. 07281 open problems -- structure theory and FPT algorithmcs for graphs, digraphs and hypergraphs. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, 08.07. - 13.07.2007 , 2007

    2007

  12. [20]

    Approximating SVP _ to within almost-polynomial factors is NP -hard

    Irit Dinur. Approximating SVP _ to within almost-polynomial factors is NP -hard. Theor. Comput. Sci. , 285(1):55--71, 2002

    2002

  13. [21]

    Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover

    Irit Dinur. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. ECCC , 23:128, 2016

    2016

  14. [22]

    Approximating CVP to within almost-polynomial factors is NP -hard

    Irit Dinur, Guy Kindler, Ran Raz, and Shmuel Safra. Approximating CVP to within almost-polynomial factors is NP -hard. Combinatorica , 23(2):205--243, 2003

    2003

  15. [23]

    Hardness of approximating the minimum distance of a linear code

    Ilya Dumer, Daniele Micciancio, and Madhu Sudan. Hardness of approximating the minimum distance of a linear code. IEEE Trans. Information Theory , 49(1):22--37, 2003

    2003

  16. [24]

    Fellows, Jiong Guo, D \' a niel Marx, and Saket Saurabh

    Michael R. Fellows, Jiong Guo, D \' a niel Marx, and Saket Saurabh. Data reduction and problem kernels (dagstuhl seminar 12241). Dagstuhl Reports , 2(6):26--50, 2012

    2012

  17. [25]

    Fomin and D \' a niel Marx

    Fedor V. Fomin and D \' a niel Marx. FPT suspects and tough customers: Open problems of downey and fellows. In Hans L. Bodlaender, Rod Downey, Fedor V. Fomin, and D \' a niel Marx, editors, The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fel...

    2012

  18. [26]

    Golovach, Jan Kratochv \' l, and Ondrej Such \' y

    Petr A. Golovach, Jan Kratochv \' l, and Ondrej Such \' y . Parameterized complexity of generalized domination problems. Discrete Applied Mathematics , 160(6):780--792, 2012

    2012

  19. [27]

    Approximating shortest lattice vectors is not harder than approximating closest lattice vectors

    Oded Goldreich, Daniele Micciancio, Shmuel Safra, and Jean - Pierre Seifert. Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Inf. Process. Lett. , 71(2):55--61, 1999

    1999

  20. [28]

    On promise problems: A survey

    Oded Goldreich. On promise problems: A survey. In Theoretical Computer Science, Essays in Memory of Shimon Even , pages 254--290, 2006

    2006

  21. [29]

    Codes correcteurs d’erreurs

    Alexis Hocquenghem. Codes correcteurs d’erreurs. Chiffres , 2:147–156, September 1959

    1959

  22. [30]

    Tensor-based hardness of the shortest vector problem to within almost polynomial factors

    Ishay Haviv and Oded Regev. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In STOC , pages 469--477, 2007

    2007

  23. [31]

    D. S. Johnson. Handbook of theoretical computer science. volume A (Algorithms and Complexity), chapter 2, A catalog of complexity classes, pages 67--161. Elseveir, 1990

    1990

  24. [32]

    Hardness of approximating the shortest vector problem in lattices

    Subhash Khot. Hardness of approximating the shortest vector problem in lattices. J. ACM , 52(5):789--808, 2005

    2005

  25. [33]

    Karthik C. S. , Bundit Laekhanukit, and Pasin Manurangsi. On the parameterized complexity of approximating dominating set. J. ACM , 66(5):33:1--33:38, 2019

    2019

  26. [34]

    Integer programming with a fixed number of variables

    Hendrik Willem Lenstra. Integer programming with a fixed number of variables. Math. Oper. Res. , 8(4):538--548, 1983

    1983

  27. [35]

    The parameterized complexity of the k-biclique problem

    Bingkai Lin. The parameterized complexity of the k-biclique problem. J. ACM , 65(5):34:1--34:23, 2018

    2018

  28. [36]

    Factoring polynomials with rational coefficients

    Arjen Klaas Lenstra, Hendrik Willem Lenstra, and L \'a szl \'o Lov \'a sz. Factoring polynomials with rational coefficients. Mathematische Annalen , 261(4):515--534, 1982

    1982

  29. [37]

    Parameterized complexity of CSP for infinite constraint languages

    Ruhollah Majdoddin. Parameterized complexity of CSP for infinite constraint languages. CoRR , abs/1706.10153, 2017

    2017 arXiv

  30. [38]

    Complexity of lattice problems: a cryptographic perspective , volume 671

    Daniele Micciancio and Shafi Goldwasser. Complexity of lattice problems: a cryptographic perspective , volume 671. Springer Science & Business Media, 2012

    2012

  31. [39]

    The shortest vector in a lattice is hard to approximate to within some constant

    Daniele Micciancio. The shortest vector in a lattice is hard to approximate to within some constant. SIAM J. Comput. , 30(6):2008--2035, 2000

    2008

  32. [40]

    The hardness of the closest vector problem with preprocessing

    Daniele Micciancio. The hardness of the closest vector problem with preprocessing. IEEE Trans. Information Theory , 47(3):1212--1215, 2001

    2001

  33. [41]

    Inapproximability of the shortest vector problem: Toward a deterministic reduction

    Daniele Micciancio. Inapproximability of the shortest vector problem: Toward a deterministic reduction. Theory of Computing , 8(1):487--512, 2012

    2012

  34. [42]

    Locally dense codes

    Daniele Micciancio. Locally dense codes. In CCC , pages 90--97, 2014

    2014

  35. [43]

    Lattice-based cryptography

    Daniele Micciancio and Oded Regev. Lattice-based cryptography. In Post-quantum cryptography , pages 147--191. Springer, 2009

    2009

  36. [44]

    A birthday repetition theorem and complexity of approximating dense CSP s

    Pasin Manurangsi and Prasad Raghavendra. A birthday repetition theorem and complexity of approximating dense CSP s. CoRR , abs/1607.02986, 2016

    2016 arXiv

  37. [45]

    Schulman, and Aravind Srinivasan

    Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995 , pages 182--191, 1995

    1995

  38. [46]

    Nguyen and Brigitte Vall \' e e, editors

    Phong Q. Nguyen and Brigitte Vall \' e e, editors. The LLL Algorithm - Survey and Applications . Information Security and Cryptography. Springer, 2010

    2010

  39. [47]

    New lattice based cryptographic constructions

    Oded Regev. New lattice based cryptographic constructions. In STOC , pages 407--416, 2003

    2003

  40. [48]

    On lattices, learning with errors, random linear codes, and cryptography

    Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In STOC , pages 84--93, 2005

    2005

  41. [49]

    Lattice-based cryptography

    Oded Regev. Lattice-based cryptography. In CRYPTO , pages 131--141, 2006

    2006

  42. [50]

    The learning with errors problem (invited survey)

    Oded Regev. The learning with errors problem (invited survey). In CCC , pages 191--204, 2010

    2010

  43. [51]

    Lattice problems and norm embeddings

    Oded Regev and Ricky Rosen. Lattice problems and norm embeddings. In STOC , pages 447--456, 2006

    2006

  44. [52]

    Approximating the number of error locations within a constant ratio is NP -complete

    Jacques Stern. Approximating the number of error locations within a constant ratio is NP -complete. In AAECC , pages 325--331, 1993

    1993

  45. [53]

    Algorithmic complexity in coding theory and the minimum distance problem

    Alexander Vardy. Algorithmic complexity in coding theory and the minimum distance problem. In STOC , pages 92--109, 1997

    1997

  46. [54]

    The intractability of computing the minimum distance of a code

    Alexander Vardy. The intractability of computing the minimum distance of a code. IEEE Trans. Information Theory , 43(6):1757--1766, 1997

    1997

  47. [55]

    Another NP -complete partition problem and the complexity of computing short vectors in a lattice

    Peter van Emde-Boas. Another NP -complete partition problem and the complexity of computing short vectors in a lattice . Report. Department of Mathematics. University of Amsterdam. Department, Univ., 1981

    1981

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.