{"id":"f3775ea3-c66a-4aa3-9144-99319e29cf74","arxiv_id":"2411.14276","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every constant odd number of queries q, any q-query locally decodable code has length at least (k/(log k))^(q/(q-2)) up to constants.","lead":"This paper proves a new lower bound on the length of locally decodable codes that recover one bit by reading a small odd number of corrupted positions. The result closes a gap for all odd query counts five and larger, using a new graph construction.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The small-|P_s| case in the proof of Theorem 1 uses a false degree bound: each heavy p does not contribute at most d_s hyperedges, so the stated trivial bound is unsupported, though the gap is repairable by padding P_s.","rationale":"The reader identified the reduction to LDC normal form as the weakest assumption. That reduction is standard and is not where I found a concrete failure. Instead, the written proof contains an internally false assertion in the small-|P_s| case of the final assembly. The bound 'each p contributes at most d_s hyperedges' contradicts the behavior of the paper's own Algorithm 4.4, which can process the same heavy p multiple times. This invalidates the stated trivial bound in that corner case. However, the gap is localized and repairable by padding P_s with dummy vertices and invoking Theorem 4.3, so it does not undermine the central claim's truth. Because the proof as written is incomplete at one step, I would not accept it unconditionally; a conditional acceptance requiring the small-|P_s| case to be fixed (or the padding argument supplied) is the appropriate verdict. I part company with the reader on the location of the weakest point, hence 'partial' agreement.","tokens_in":36359,"tokens_out":39566,"duration_ms":344295,"concrete_test":"Instantiate q=5, ℓ=n^{3/5}, k=n^{3/5} log n, d_2=n^{-1/5}k, and construct matchings H_1,...,H_k on [n] such that a fixed pair {a,b} lies in one hyperedge of every H_i. Run Algorithm 4.4 and count the hyperedges in ∪_i H_i^(2) containing the label p_{a,b}; the count will be k, exceeding d_2, which disproves the asserted per-p contribution bound. Then check that adding |P_s|-padding to size 4ℓ satisfies the hypotheses of Theorem 4.3 and yields the stated bound.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the proof of Theorem 1 (Section 4, after applying Lemma 4.1), the authors handle the case |P_s| ≤ 4ℓ by claiming: 'we also have Σ_i |H_i^(s)| ≤ |P_s| d_s, as each p ∈ P_s contributes at most d_s hyperedges to ∪_i H_i^(s).' This claim is false for Algorithm 4.4. A heavy p is processed repeatedly: each time it is chosen, d_t+1 hyperedges are removed, and if p remains heavy it is chosen again. Its total contribution to ∪_i H_i^(s) equals its original degree in H, which can be as large as k (one hyperedge per matching H_i), while d_s = (ℓ/n)^{s-3/2} k < k. Thus p can contribute far more than d_s hyperedges, so the bound val(Ψ^(s)_b) ≤ ℓ d_s is not justified. In the nontrivial parameter regime δ ≥ n^{-2/(q+2)} with k ≈ n, the weaker bound Σ_i |H_i^(s)| ≤ |P_s| k ≤ 4ℓ k can exceed δn√(kℓ log n), so the gap is not automatically absorbed. The case is repairable: pad P_s with dummy elements to size exactly 4ℓ, assign y_p = 1 to dummies, include no hyperedges through them, and apply Theorem 4.3; the necessary inequality 4ℓ ≤ O(nk/d_s) holds for large n. Hence the main theorem is likely correct, but the written proof has a concrete unsupported step in a corner case.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves a lower bound of n ≥ Ω((k/log k)^{q/(q-2)}) for q-query locally decodable codes for every odd q ≥ 3, with explicit polynomial dependence on ε and δ. The proof reduces an LDC to normal form, decomposes the query hypergraphs according to heavy subsets, refutes the residual 'regular' instance via the Cauchy–Schwarz trick and balanced Kikuchi matrices, and refutes each decomposed bipartite instance using a new imbalanced bipartite Kikuchi graph. The central technical contribution is a conditional-moment analysis showing that these bipartite Kikuchi matrices admit approximately biregular submatrices, which avoids the correlated randomness that blocked prior odd-arity extensions.","tokens_in":36647,"tokens_out":15640,"duration_ms":137788,"significance":"If completed, the proof closes the gap between even- and odd-query LDC lower bounds, improving the best known bound for odd q ≥ 5 by a polynomial factor. It also gives a better dependence on log n, δ, and ε for q = 3 than the previous bound of Alrabiah–Guruswami–Kothari–Manohar. The bipartite Kikuchi graph construction and the conditional-moment row-pruning technique are likely to be useful beyond LDCs, in spectral refutation of odd-arity constraint satisfaction problems. The paper is careful and self-contained: all stated lemmas have proofs, the parameters are not fitted to data, and the concurrent work [BHKL24] is explicitly acknowledged with a precise comparison of the log factors.","major_comments":[{"comment":"The displayed bound Σ_i |H_i^(s)| ≤ |P_s| d_s is not justified. In Algorithm 4.4, a heavy set p is not removed from the candidate set after being chosen; it is chosen again whenever its current degree exceeds d_s, so the hyperedges routed through a single p are not capped at d_s but can be as many as deg_H(p), which can be as large as k. Thus from |P_s| ≤ 4ℓ one can only conclude Σ_i |H_i^(s)| ≤ 4ℓ k, and in the regime δ ≥ n^{-2/(q+2)} with k ≈ n this exceeds δn√(kℓ log n) by a factor n^{(q-2)/(q(q+2))}, so the stated conclusion val(Ψ_b^(s)) ≤ ℓ d_s does not follow from the trivial bound. The case is repairable: pad P_s with dummy elements to exactly size 4ℓ, set y_p = 1 for the dummies, include no hyperedges through them, and then apply Theorem 4.3; the necessary inequality 4ℓ ≤ O(nk/d_s) holds for large n. The proof should be amended accordingly.","section":"Section 4, proof of Theorem 1 (small-|P_s| case)"}],"minor_comments":[{"comment":"The diagonal term in the expansion of (qΨ(x))^2 is q k δ n^2, not q δ n^2; both the lemma statement and the displayed derivation drop the factor k. The final bound is unaffected because the second term dominates for k ≥ 4ℓ, but the displayed equality should be corrected.","section":"Section 5, Lemma 5.1"},{"comment":"The loop 'For t = (q+1)/2, ..., 1' should terminate at t = 2, since the thresholds d_1 and the sets P'_1 are never defined for t = 1.","section":"Section 4.1, Algorithm 4.4"},{"comment":"The notion of an 'inherently bipartite' Kikuchi graph is admitted to be informal; since the informal definition is not used in the proofs, the wording is acceptable but should be flagged more explicitly as an intuition rather than a formal concept.","section":"Remark 2.4"},{"comment":"There is a stray bracket in the statement of the rectangular Matrix Khintchine inequality ('∥∑ X_i X_i^⊤]∥'); the notation should be cleaned up.","section":"Section 3.3, Fact 3.6"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is likely correct and the paper is a strong contribution, but the written proof contains a false bound in the small-|P_s| corner case. The repair (padding P_s with dummy variables and invoking Theorem 4.3) is straightforward and local, so I recommend major revision rather than rejection. The concurrent work [BHKL24] is handled fairly; the improved log factor gives this paper independent value."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this is a real result. It closes the odd-q gap in q-query LDC lower bounds by proving k ≤ O(n^{1-2/q} log n) for all odd q, via a genuinely new construction: inherently bipartite Kikuchi graphs. The row pruning analysis is careful and the matrix concentration arguments are standard. The q=3 log-factor improvement over AGKM23 is a bonus, not the main event.\n\nWhat is new: the bipartite Kikuchi graph for decomposed instances avoids the Cauchy-Schwarz trick in all but the top-level case, and that is what breaks the q ≥ 7 barrier. The proof is detailed and mostly self-contained. I did not machine-check the long combinatorial calculations, but the structure is coherent and the lemmas are proved.\n\nOne soft spot, and it is real. In the proof of Theorem 1, the small-|P_s| case is handled by claiming Σ_i |H_i^(s)| ≤ |P_s| d_s because 'each p contributes at most d_s hyperedges.' That is not what Algorithm 4.4 does. A heavy p can be selected, have d_s+1 hyperedges removed, and remain heavy; it gets selected again. Its total contribution is its original degree in H, which can be as large as k, not d_s. So the stated bound is unsupported. The stress-test note is right about this. The good news is that the gap is repairable: pad P_s with dummy elements to size exactly 4ℓ, set their y variables to 1, include no hyperedges through them, and apply Theorem 4.3. The inequality 4ℓ ≤ O(nk/d_s) holds in the parameter regime the paper needs. I would not be surprised if the authors already have this fix in mind, but as written the proof has a hole in a corner case.\n\nAlso minor: the abstract says the proof avoids the Cauchy-Schwarz trick entirely, but the body admits the top-level instance still uses it. That is an overstatement, not a substantive issue.\n\nOverall: the central technique is sound and the result is important. The unsupported step is confined to a corner case and has a clear repair. This deserves a serious referee and, after a revision that fixes the small-|P_s| argument, acceptance. I'd cite it and bring it to reading group.","headline":"Strong result with a real but repairable gap in the small-|P_s| case; the bipartite Kikuchi technique is the real contribution and the paper deserves review.","tokens_in":37254,"tokens_out":3509,"would_cite":true,"duration_ms":30454,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","94B65","05C65"],"pacs":[],"model":"deepseek-v4-flash","headline":"All odd query counts now hit the k^{q/(q-2)} LDC bound.","keywords":["locally decodable codes","spectral refutation","Kikuchi matrices","bipartite Kikuchi graph","odd-arity XOR","lower bounds","hypergraph decomposition"],"falsifier":"Exhibit a 5-query LDC family with blocklength $n < c(k/\\log k)^{5/3}$ for arbitrarily large $k$ and constant $\\delta,\\varepsilon$; Theorem 1 predicts $k \\le O(n^{3/5}\\log n)$, so any such family would disprove the claimed $k^{q/(q-2)}$ barrier. A direct check of the same reduction would show the failing assumption: the resulting query hypergraphs would have to be non-matchings or have fewer than $\\delta n$ edges.","tokens_in":36113,"feed_emoji":"🧮","tokens_out":9229,"duration_ms":78479,"temperature":0.7,"pith_summary":"A $q$-query locally decodable code ($q$-LDC) is a code whose decoder can recover any message bit by reading at most $q$ positions of a slightly corrupted codeword. This paper proves that every $q$-LDC with odd $q\\ge 3$ needs blocklength $n \\ge \\tilde{\\Omega}(k^{q/(q-2)})$, matching for odd $q$ the exponent that was previously known only for even $q$ and for $q=3$. The argument views the decoding constraints as an odd-arity XOR system and shows that if $n$ were too small, a random signed combination of the associated Kikuchi matrices has small spectral norm, so the system is refutable. The enabler is a deliberately imbalanced bipartite Kikuchi graph that keeps the random signs independent and avoids the 'Cauchy–Schwarz trick', whose correlated randomness blocked earlier attempts for $q\\ge 5$. The same construction improves the logarithmic and error-parameter dependence of the $q=3$ lower bound.","feed_headline":"All odd query counts now hit the k^{q/(q-2)} LDC bound","feed_subtitle":"A bipartite Kikuchi graph refutes odd-arity XOR without the correlated Cauchy–Schwarz trick.","key_machinery":"The central object is an imbalanced bipartite Kikuchi graph $A_{C,p}$, a spectral certificate built from an induced subgraph of a Cayley graph on the hypercube. For a decomposed hyperedge $(C,p)$ with $C\\subseteq [n]$, $|C|=q-s$, and a heavy-set label $p\\in P_s$, left vertices are pairs $(S_1,S_2)$ with $|S_1|=|S_2|=\\ell$, right vertices are pairs $(T_1,T_2)$ with $|T_1|=\\ell+1-s$, $|T_2|=\\ell+1$, and an edge is placed exactly when $S_1\\oplus T_1=C$ and $S_2\\oplus T_2=\\{p\\}$, with $|S_1\\cap C|=(q-1)/2$. The imbalance lets the label $p$, which stands for a set of $s$ original variables, contribute through the larger right-hand side, boosting the average right degree by a factor of $n^{1/q}$; that boost is precisely what allows $\\ell=n^{1-2/q}$ and yields the exponent $q/(q-2)$. The matching property of the decomposed hypergraphs then makes the row-pruning step—deleting high-degree vertices while keeping most edges—succeed on both sides.","core_discovery":"The paper's central claim is that for odd $q\\ge 3$, every $(q,\\delta,\\varepsilon)$-LDC $C:\\{0,1\\}^k\\to\\{0,1\\}^n$ satisfies $k \\le O_q(n^{1-2/q}\\varepsilon^{-6-2/q}\\delta^{-2-2/q}\\log n)$, so for constant $\\delta,\\varepsilon$ the length obeys $n\\ge \\Omega((k/\\log k)^{q/(q-2)})$. This is the first $k^{q/(q-2)}$ lower bound for all odd $q\\ge 5$, closing the polynomial-factor gap left by the best previous odd-query bound $\\tilde{\\Omega}(k^{(q+1)/(q-1)})$. The proof reduces the code to the standard LDC normal form with matching query hypergraphs, decomposes the hypergraphs by 'heavy' sets of sizes $2\\le s\\le (q+1)/2$, refutes the regular leftover instance by the known Cauchy–Schwarz/Kikuchi route, and refutes each decomposed bipartite instance with a new imbalanced bipartite Kikuchi graph; because every decomposed hypergraph is still a matching, the row-pruning step that the whole certificate depends on goes through.","pith_inferences":["The imbalanced bipartite construction is a candidate template for odd-arity XOR refutation in other settings; any odd-arity constraint system whose hypergraphs decompose into matchings could inherit a certificate with independent signs and no Cauchy–Schwarz blow-up.","Because the proof uses the matching property only in the row-pruning step, a natural testable extension is to quantify how much hyperedge overlap can be tolerated before the spectral certificate degrades.","The improved $q=3$ parameters suggest the earlier Cauchy–Schwarz analysis was not tight; a direct certificate on the original matchings may eventually remove additional polylogarithmic factors.","The fact that the right vertex set is 'effectively' $s$ positions larger suggests a general principle: imbalanced spectral certificates can beat balanced ones when one side of the bipartition represents compressed heavy structures."],"forward_implications":["For every constant odd $q\\ge 5$, the blocklength of a $q$-LDC is at least $\\tilde{\\Omega}(k^{q/(q-2)})$, improving the previous $\\tilde{\\Omega}(k^{(q+1)/(q-1)})$ by a polynomial factor.","The $q=3$ lower bound now has the same logarithmic dependence as the even-$q$ bound and a better dependence on $\\varepsilon$ and $\\delta$ than the earlier near-cubic bound.","The lower bound transfers to $q$-LDCs over larger alphabets via the standard reduction to binary codes, so the exponent $q/(q-2)$ holds there as well.","Both linear and nonlinear $q$-LDCs are covered by the same argument, with no extra regularity assumptions imposed on the code."],"supporting_citations":[{"why":"Supplies the normal-form reduction (Fact 3.5) that turns any LDC into matching query hypergraphs of size at least $\\delta n$, the structure the whole argument requires.","marker":"[Yek12]"},{"why":"Gives the prior $q=3$ bound and the even-$q$ Cauchy–Schwarz/Kikuchi blueprint that this paper extends to all odd $q$.","marker":"[AGKM23]"},{"why":"Introduces the hypergraph decomposition by heavy sets that Lemma 4.1 uses to split the decoding hypergraphs.","marker":"[GKM22]"},{"why":"Introduces Kikuchi matrices, the Cayley-graph spectral certificates used for the regular and decomposed instances.","marker":"[WAM19]"},{"why":"Supplies the rectangular Matrix Khintchine inequality (Fact 3.6) that bounds the expected spectral norm of the signed matrices.","marker":"[Tro15]"},{"why":"Establishes the even-$q$ $k^{q/(q-2)}$ lower bound and the reduction to larger alphabets that the paper's odd-$q$ result completes.","marker":"[KW04]"},{"why":"Concurrent independent proof of the same odd-$q$ lower bound with a worse logarithmic dependence, used as the comparison point for Theorem 1.","marker":"[BHKL24]"}],"fun_headline_variants":["Odd q LDC bound reaches k^{q/(q-2)}","Bipartite Kikuchi graphs prove odd LDC lower bound","All odd q get k^{q/(q-2)} LDC length lower bound","Imbalanced Kikuchi graphs close odd LDC gap","Odd q LDC bound reaches k^{q/(q-2)} via Kikuchi"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof leans on the standard reduction that rewrites any $(q,\\delta,\\varepsilon)$-LDC into a code whose decoding queries are $q$-uniform matchings of size at least $\\delta n$ with only constant-factor losses; if that reduction cannot preserve the matching structure and the $\\delta n$ size, the spectral certificate stops working.","fun_headline_variants_meta":{"raw":{"variants":["Odd q LDC bound reaches k^{q/(q-2)}","Bipartite Kikuchi graphs prove odd LDC lower bound","All odd q get k^{q/(q-2)} LDC length lower bound","Imbalanced Kikuchi graphs close odd LDC gap","Odd q LDC bound reaches k^{q/(q-2)} via Kikuchi"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000779,"raw_usage":{"total_tokens":3591,"prompt_tokens":1243,"completion_tokens":2348,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":859,"completion_tokens_details":{"reasoning_tokens":2249}},"tokens_in":859,"tokens_out":2348,"duration_ms":14181,"temperature":1.0,"reasoning_tokens":2249,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:20:34.906767+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a 5-query LDC family with blocklength $n < c(k/\\log k)^{5/3}$ for arbitrarily large $k$ and constant $\\delta,\\varepsilon$; Theorem 1 predicts $k \\le O(n^{3/5}\\log n)$, so any such family would disprove the claimed $k^{q/(q-2)}$ barrier. A direct check of the same reduction would show the failing assumption: the resulting query hypergraphs would have to be non-matchings or have fewer than $\\delta n$ edges.","supporting_citations":[],"review_version":1}