{"id":"2bcf94f4-31a9-433b-aacc-a5197e89fbec","arxiv_id":"1909.01986","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For every constant gamma >= 1, k-Even Set is W[1]-hard to approximate under randomized reductions, and for every p > 1, k-SVP in the l_p norm is W[1]-hard to approximate to some constant factor.","lead":"This paper proves that two classic parameterized problems, k-Even Set and k-Shortest Vector Problem, are W[1]-hard under randomized reductions, answering open questions from Downey and Fellows' 1999 book. If the standard W[1] != FPT conjecture holds, neither problem admits fixed-parameter tractable algorithms, even allowing constant-factor approximation.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.2's WLOG number-theoretic condition lacks a proof; padding via universal and isolated vertices likely repairs it, but the paper should spell this out.","rationale":"The reader identified the correct weakest point: the unproved WLOG in Theorem 4.2. My stress test agrees that this is the most load-bearing unstated assumption in the manuscript. However, the concern does not appear to be fatal: standard padding constructions can adjust k by adding universal vertices and n by adding isolated vertices, and the required inequalities are then satisfiable with FPT-bounded output size. Therefore the central claim remains intact, but the paper should contain the explicit padding argument before the reduction is fully rigorous. I checked the surrounding steps at a high level: the GAPLDS construction, the color-coding step, the GAPMLD reduction, the locally suffix dense code construction, and the Khot-style SVP reduction all appear internally consistent modulo minor typographical issues. The conditional verdict is appropriate: the manuscript should be accepted once the WLOG in Theorem 4.2 is justified in writing.","tokens_in":43519,"tokens_out":45797,"duration_ms":458107,"concrete_test":"Write out the padding explicitly: given a k-Clique instance (G,k), choose Delta in {0,...,5} with 6 | (k+Delta)+1, add Delta universal vertices connected to everything, and add N isolated vertices so that ceil((n+N)/6^{(k+Delta)+6}) > (k+Delta+6)! * (gamma * (k+Delta)^2)^{(k+Delta)^2}. Then verify two things: (i) the padded graph has a (k+Delta)-clique if and only if G has a k-clique, and (ii) with h = (k+Delta+6)! * (gamma * (k+Delta)^2)^{(k+Delta)^2} and s = binom(k+Delta,2), the conditions h <= common-neighbor bound and h/ell >= gamma^s s^s needed by Claim 4.4 hold. If both checks pass, Theorem 4.2 is fully justified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the proof of Theorem 4.2, the reduction from k-Clique to GAPBSMD_gamma asserts, without proof, that we may assume 6 | k+1 and ceil(n/6^{k+6}) > (k+6)! * (gamma * k^2)^{k^2}. This is load-bearing because it is exactly what lets the reduction set h = (k+6)! * (gamma * k^2)^{k^2}, invoke Lin's Theorem 4.3, and satisfy the hypothesis of Claim 4.4. If this WLOG transformation were impossible, the W[1]-hardness of GAPBSMD, and therefore the rest of the reduction chain to k-Even Set and k-SVP, would collapse. The paper does not provide the padding or parameter-adjustment argument. On inspection, the assertion is very plausible: one can add at most five universal vertices connected to all old and new vertices to make k+1 divisible by 6 while preserving the existence of a k-clique, and one can add isolated vertices to inflate n to the required bound. Thus the gap is a missing proof detail rather than a demonstrated flaw, but it should still be made explicit in the manuscript.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":43743,"tokens_out":31801,"duration_ms":303764,"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":[{"comment":"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.","section":"Section 4.1, proof of Theorem 4.2"},{"comment":"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.","section":"Sections 3.5, 7.1, 7.2 (Claim 7.7)"},{"comment":"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.","section":"Section 4.2, proof of Theorem 4.5"},{"comment":"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.","section":"Section 4.1, Claim 4.4"}],"minor_comments":[{"comment":"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.","section":"Section 7.1, proof of Theorem 7.2"},{"comment":"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.","section":"Section 5.2, proof of Theorem 5.4"},{"comment":"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.","section":"Section 7.2.2, intermediate lattice"},{"comment":"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.","section":"Lemma 6.4"},{"comment":"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.","section":"Theorem 4.9 and notation"}],"recommendation":"major_revision","confidential_remarks":"The core reduction architecture is sound and the results are significant, but the paper needs a careful revision round: the WLOG padding argument in Theorem 4.2 must be supplied, and the GAPNVP definition must be aligned with the scaled NO property actually used in the SVP section. I do not see grounds for rejection, but I would not accept the manuscript in its current form because two load-bearing proof steps are not fully justified as written."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper closes two questions that have been open since Downey--Fellows: k-Even Set and k-SVP are W[1]-hard to approximate under randomized reductions. The main results are real, and the proof architecture is sound. The chain from k-Clique through Lin's one-sided biclique, the new BSMD and sparse nearest codeword problems, to the final inapproximability results is detailed and mostly self-contained. The introduction of locally suffix dense codes is a genuine technical contribution, and the BCH code construction fits nicely into the parameterized setting.\n\nThe biggest soft spot is Theorem 4.2. The proof says \"without loss of generality\" that 6 | k+1 and ceil(n/6^{k+6}) > (k+6)! (gamma k^2)^{k^2}, but never gives the padding argument. This is load-bearing because the reduction to GAPBSMD uses those conditions to invoke Lin's theorem and set h. The good news is that the gap is not a demonstrated flaw. You can pad the k-Clique instance by adding at most five universal vertices to adjust k modulo 6, and add isolated vertices to inflate n, while preserving whether a k-clique exists. The reduction is FPT and the parameter stays O(k). The paper should spell this out; as written it is a missing proof detail, not a fatal error.\n\nThe other noted issue is Lemma 7.4, the BCH lattice gadget, which is used as a black box from Khot. That is acceptable for a paper of this scope, but a referee might ask for a self-contained proof or at least a more precise statement of the probability and vector bounds.\n\nOn the evidence side: the reductions are explicit and the correctness proofs are careful. The randomized nature of the reductions is standard for SVP hardness and for the DMS-style locally dense code construction, so that is not a flaw. The paper is honest about its limitations, including the fact that k-SVP in l_1 remains open and that for l_p with p != 2 the gap is only some constant depending on p.\n\nThe citation pattern looks healthy. The paper relies on Lin's recent work and on Khot and DMS, but the new intermediates and gadgets are constructed and proved inside the paper. I do not see circularity.\n\nWho is this for? Anyone working on parameterized complexity of coding and lattice problems. It settles two questions that have been kicked around for two decades, so it will get read. I recommend accepting this for peer review. The main revision should be to spell out the padding argument in Theorem 4.2 and, ideally, to make the BCH lattice lemma more self-contained. After that, I expect it to be accepted.","headline":"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.","tokens_in":44386,"tokens_out":2232,"would_cite":true,"duration_ms":25708,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q27","94B05","11H06"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["parameterized complexity","W[1]-hardness","minimum distance problem","k-Even Set","shortest vector problem","locally suffix dense codes","nearest codeword problem","randomized reductions"],"falsifier":"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.","tokens_in":43312,"feed_emoji":"","tokens_out":15153,"duration_ms":134005,"temperature":0.7,"pith_summary":"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.","feed_headline":"Even Set and Shortest Vector are W[1]-hard to approximate","feed_subtitle":"If W[1]≠FPT, no fixed-parameter algorithm can solve or approximate either problem.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the W[1]-hardness of approximating the one-sided biclique problem, the starting point of the entire reduction chain.","marker":"[Lin18]"},{"why":"Raised the parameterized complexity of k-MDP and k-SVP and established exact W[1]-hardness of the inhomogeneous counterparts that this paper upgrades to approximation hardness.","marker":"[DFVW99]"},{"why":"Contributes the gadget reduction from nearest codeword to minimum distance and the locally dense code concept adapted here into locally suffix dense codes.","marker":"[DMS03]"},{"why":"Contributes the BCH lattice reduction from nearest vector to shortest vector, reused with parameterized adjustments in the SVP half of the paper.","marker":"[Kho05]"},{"why":"Provides the perfect hash families used to color the linear dependent set instance without changing the gap.","marker":"[NSS95]"},{"why":"Supplies the BCH codes used both in the LSDC construction and in the BCH lattice gadget.","marker":"[Hoc59, BR60]"}],"fun_headline_variants":["Even Set and Shortest Vector are W[1]-hard even with constant gaps","Constant-factor approximation W[1]-hard for Even Set and SVP","Even Set and SVP: W[1]-hardness for any constant gap","W[1]-hardness for Even Set and Shortest Vector with constant factors"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Even Set and Shortest Vector are W[1]-hard even with constant gaps","Constant-factor approximation W[1]-hard for Even Set and SVP","Even Set and SVP: W[1]-hardness for any constant gap","W[1]-hardness for Even Set and Shortest Vector with constant factors"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001072,"raw_usage":{"total_tokens":4566,"prompt_tokens":1096,"completion_tokens":3470,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":712,"completion_tokens_details":{"reasoning_tokens":3385}},"tokens_in":712,"tokens_out":3470,"duration_ms":24714,"temperature":1.0,"reasoning_tokens":3385,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:10:43.217535+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}