{"id":"4a6ee640-8954-4caf-866f-9a38cc84cda2","arxiv_id":"2411.14361","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For every odd q ≥ 3, any q-query binary locally decodable code with constant distance satisfies k ≤ O~(n^(1-2/q)), the first bound of this form for q ≥ 5.","lead":"This paper proves that any binary locally decodable code that reads an odd number of bits q must use blocklength at least roughly k^(q/(q-2)) up to logarithmic factors, matching the known even-query bound. It introduces a new hypergraph regularity condition that makes spectral methods work without absolute co-degree bounds, a technique likely to be reusable in other Kikuchi matrix arguments.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.20's 'otherwise' case asserts d_{t+g} ≤ n^{1−2(f+g)/q}d_t without support from condition (2); for q−t even this inequality fails, leaving Lemma 4.15 unproven as written, though a direct repair exists.","rationale":"Lemma 5.1, the reader's flagged step, is correct; I verified the extremal argument in §5.1 including the t0/t>q/2 case split and the use of Lemma 5.6. The real weakness is the internal proof of Lemma 4.20, on which the heavy-vertex pruning of Lemma 4.15 depends. The false inequality appears exactly in the case q−t even that arises for odd q, but the intended bound can be recovered by applying condition (2) at r=t+|Z2|, so the central claim is not threatened. Since the manuscript as written has a genuine gap in a central lemma (and a second algebra slip in Lemma 4.16), the appropriate verdict is CONDITIONAL rather than unconditional ACCEPT: the authors should patch the case split and restate Lemma 4.16's bound.","tokens_in":35239,"tokens_out":54469,"duration_ms":467309,"concrete_test":"Re-derive Lemma 4.20 for q=7, t=1, |Z1|=|Z2|=3: check whether condition (2) at r=t+g=3 supports d_3 ≤ n^{−5/7}d_1. It gives d_3 ≤ n^{−3/7}d_1, so the written chain fails. Then verify the repaired route: condition (2) at r=t+|Z2|=4 gives d_4 ≤ n^{−5/7}d_1, which is the bound needed for the partial-derivative estimate. If this check passes, Lemma 4.15 can be restored.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In Lemma 4.20, when |Z2| = ceil((q−t)/2), the proof sets g=|Z2|−1, f=|Z1|+1 and uses d_{t+|Z2|} ≤ d_{t+g} ≤ n^{1−2(f+g)/q}d_t. The second inequality is not a consequence of condition (2) of Definition 2.6 in the q−t even case. Example: q=7, t=1, |Z1|=|Z2|=3 gives f+g=6, so the claim is d_3 ≤ n^{−5/7}d_1, but condition (2) at r=t+g=3 yields only d_3 ≤ n^{−3/7}d_1. Since d_4 ≤ d_3, the displayed chain does not produce the needed d_4 ≤ n^{−5/7}d_1. The gap is repairable: for q−t even, condition (2) applies directly at r=t+|Z2|=(q+t)/2 and gives exactly the needed bound (or stronger), so Lemma 4.20's statement is likely true; however, the written proof of the degree-concentration step (Lemma 4.15) is incomplete without this case split. A separate algebra slip in Lemma 4.16 (stated √(kℓ n d_t) vs the proof's √(kℓ) n d_t) also needs correction, though it does not change the final theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that every odd-query binary locally decodable code with constant distance satisfies k <= O-tilde(n^{1-2/q}), matching the known even-q bound up to polylogarithmic factors. For q=3 this recovers the AGKM23 bound; for q>=5 it is the first polynomial improvement. The proof introduces a notion of t-approximate strong regularity for the hypergraph of local decoding sets, proves that every hypergraph can be decomposed into such pieces, and then uses Kikuchi-matrix spectral bounds together with a polynomial concentration argument to refute the associated q-XOR instance. A separate combinatorial argument covers linear codes via weakly rainbow even covers. The main theorem (Theorem 1.1, restated as Theorem 4.1) is shown by reducing a hypothetical LDC to a q-XOR instance whose expected value over random signs is bounded from above and below, leading to a contradiction when k is too large.","tokens_in":1689,"tokens_out":1685,"duration_ms":286334,"significance":"If the proof can be completed, this is a significant result: it resolves the odd-q bottleneck identified in AGKM23, matches the best even-q upper bounds on k, and introduces a genuinely useful conceptual relaxation from absolute co-degree bounds to relative ones. The greedy regularity decomposition and the relative-bound formulation are elegant and likely to be reused elsewhere. The paper is clearly written overall and the high-level architecture is convincing, but the proof is not machine-checked and one load-bearing concentration step is not valid as written.","major_comments":[{"comment":"The 'otherwise' case in the proof of Lemma 4.20 is not established, and the displayed bound is false as a consequence of the stated hypotheses. The proof asserts d_{t+|Z2|} <= d_{t+g} <= n^{1-2(f+g)/q} d_t with g=|Z2|-1 and f=|Z1|+1. The second inequality would require condition (2) of Definition 2.6 at r=t+g to give exponent at least 1-2(f+g)/q, but it does not. For q=7, t=1, |Z1|=|Z2|=3, condition (2) at r=3 gives only d_3 <= n^{-3/7} d_1, while the asserted chain needs d_4 <= n^{-5/7} d_1. For q-t odd the problem is worse: with q=5, t=2, the data d_1=n, d_2=d_3=d_4=n^{3/5}, d_5=1 satisfies all three conditions of Definition 2.6, yet for |Z1|=1, |Z2|=2 the claimed 'In particular' bound would require d_4 <= n^{-1/5} d_2, which is violated. Since Lemma 4.15's n^{-100q} tail bound is derived from exactly these derivative estimates via Fact 3.6, Lemma 4.15 is unproven as written, and this is load-bearing for Lemmas 4.6 and 4.16 and hence for Theorem 1.1. The partition structure of approximate strong regularity may supply extra information, but the current proof does not use it; the lemma either needs a corrected proof with a genuine case split or needs a strengthened definition of 'good index'.","section":"Section 4.2, Lemma 4.20"},{"comment":"The statement and proof of Lemma 4.16 are inconsistent. The lemma states D^{-1} ||sum_i b_i K_{i,t}||_{infty->1} <= sqrt(k * ell * n * d_t) * O((log n)^{1/2}), but the derivation after Eq. (5), using N/D <= (2n/ell)^{q-t}, gives sqrt(k * ell) * n * d_t * O((log n)^{1/2}) instead. The latter expression is the one used in the proof of Lemma 4.6, so the final theorem is not affected, but the displayed statement is stronger than what the proof establishes and must be corrected.","section":"Section 4.1, Lemma 4.16"},{"comment":"The proof says that the gamma_i satisfy the hypothesis of Lemma 5.1, but Lemma 5.1 is unconditional; the argument only needs the fixed good index t from the approximate strong regularity partition. More importantly, the proof of Lemma 4.15 depends on Lemma 4.20 in the exact regime where Lemma 4.20 is currently false or unproven, so the existence of some good index via Lemma 5.1 does not repair the gap unless the definition of good index is strengthened or the concentration argument is changed.","section":"Section 4.2, proof of Lemma 4.15"}],"minor_comments":[{"comment":"The two cases in Deg(s,s') are labeled 'if t is even' and 'if t is odd', but the expressions use (q-t)/2, which is not an integer when q is odd and t is even. The intended condition is clearly the parity of q-t, as in Definition 4.11 and in Figure 3; please fix the typo.","section":"Definition 4.17"},{"comment":"The sentence claiming that the methods extend to finite alphabets of size n^{o(1)} is stated without proof. If this is not part of the main theorem, mark it explicitly as a remark or conjecture rather than an asserted consequence.","section":"Section 1, finite-alphabet remark"},{"comment":"In the comparison for the case Z1=empty, the phrase 'if and only if ... or ...' should read 'if and only if ... , i.e. ...'; the 'or' introduces a false alternative.","section":"Lemma 4.20 proof"},{"comment":"The tie-breaking in Step 1 of the proof is unspecified. Since different choices of a maximizing t0 can lead to different returned indices (e.g., in the q=5 example with gamma_1=1, gamma_2=gamma_3=gamma_4=3/5, gamma_5=0, both t=1 and t=2 maximize gamma_t+2t/q), the proof should specify a deterministic rule. This is not merely cosmetic: one of the tied choices returns an index for which Lemma 4.20's bound fails.","section":"Lemma 5.1 proof"},{"comment":"The bound 'the number of (C,C') that contribute is at most n d_t' is correct but worth a short justification, since the current sentence compresses the argument that C in H_i gives at most one choice of the group and then at most d_t choices of C'.","section":"Section 4.2, Eq. (7)"}],"recommendation":"major_revision","confidential_remarks":"The theorem is very likely true and the framework is promising, but the written proof of the central degree-concentration lemma (Lemma 4.15 via Lemma 4.20) has a genuine gap that is not merely a local typo: the stated derivative bounds are false under the current Definition 2.6. This is fixable either by strengthening the definition of a good index or by a more careful case analysis in Lemma 4.20, so I recommend major revision rather than rejection. The authors should also clarify the relationship to the concurrent work [JM24] and fix the Lemma 4.16 statement/proof mismatch."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on the odd-query LDC paper. The main theorem—k ≤ O~(n^{1−2/q}) for every odd q ≥ 3—is the real thing. It closes a gap that has been open for two decades, and it does so with a new idea: replacing absolute co-degree bounds with relative ones via t-approximate strong regularity. The good-index lemma and the greedy decomposition are clean, and the Kikuchi-matrix machinery is deployed with care. The paper earns its claims.\n\nI verified the main line: the Cauchy-Schwarz trick, the quadratic-form representation, the Matrix Khintchine step, and the decomposition all check out. The proof is long but organized.\n\nNow the soft spots. The stress-test note is right about Lemma 4.20. In the 'otherwise' case, when q−t is even, the chain d_{t+|Z2|} ≤ d_{t+g} ≤ n^{1−2(f+g)/q} d_t uses a bound that condition (2) does not supply. For q=7, t=1, |Z1|=|Z2|=3, condition (2) at r=3 only gives d_3 ≤ n^{−3/7}d_1, not n^{−5/7}d_1, and d_4 ≤ d_3 doesn't bridge the gap. The fix is direct: apply condition (2) at r=t+|Z2|=(q+t)/2, which is within the allowed range and gives exactly the needed exponent. So Lemma 4.20 is true, but the written proof is incomplete as is. Any referee should ask for that case split.\n\nThere is also a small typo in Lemma 4.16: the statement says √(kℓ n d_t), while the proof and the downstream use in Lemma 4.6 require √(kℓ) n d_t. Cosmetic, but should be fixed.\n\nThe informal claim about non-binary alphabets is clearly flagged as omitted, so I don't count it against them.\n\nBottom line: the central argument holds together; the identified gap is real but repairable, and the result is important. This deserves a serious referee. I'd send it to review with a request to fix Lemma 4.20 and clean up Lemma 4.16. I'd also bring it to reading group.","headline":"Genuinely new idea and a likely-right main theorem, but the written proof has a repairable gap in the key concentration lemma.","tokens_in":36095,"tokens_out":4191,"would_cite":true,"duration_ms":34496,"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":"For every odd q ≥ 3, any binary q-query locally decodable code with constant distance has message length k ≤ O-tilde(n^{1−2/q}).","keywords":["locally decodable codes","query complexity","lower bounds","Kikuchi matrices","approximate strong regularity","co-degree","weak rainbow even covers","semirandom CSP refutation"],"falsifier":"A counterexample to Theorem 1.1 would be a binary 5-query locally decodable code with constant distance, blocklength n, and message length k = ω($n^{{3/5}}$ $log^{4}$ n). A cheaper, local falsifier targets the good-index lemma: generate random nonincreasing sequences γ_1 ≥ ... ≥ γ_q for q ∈ {5,7,9}, run the paper's two-step maximization algorithm, and check whether the selected index satisfies all three displayed inequalities; a single violation would break the decomposition.","tokens_in":35050,"feed_emoji":"🧮","tokens_out":7933,"duration_ms":71886,"temperature":0.7,"pith_summary":"This paper proves a lower bound on the blocklength of locally decodable codes with odd query count. For any odd q ≥ 3, a binary q-query locally decodable code with constant distance and blocklength n can encode at most k ≤ O-tilde($n^{{1−2/q}}$) message bits, and if the code is linear the bound improves to O($n^{{1−2/q}}$ $log^{2}$ n). For odd q ≥ 5 this is the first polynomial improvement over the trivial bound obtained by treating the code as a (q+1)-query code, and it matches the best known bound for even q. The proof's key idea is a relaxed hypergraph regularity condition under which spectral arguments on Kikuchi matrices succeed even when co-degrees are large.","feed_headline":"Odd-query LDCs hit n^{1−2/q} lower bound","feed_subtitle":"First polynomial improvement for every odd q ≥ 5, matching the even-q benchmark.","key_machinery":"The load-bearing object is t-approximate strong regularity: a q-uniform hypergraph can be partitioned into pieces, each piece's hyperedges all contain a common t-set, each piece has size between d_t/2 and d_t where d_t is the maximum co-degree of t-sets, and all other co-degrees are bounded relative to d_t by three inequalities that define a good index t. A short extremal lemma shows that for any hypergraph some t is always good. On such a hypergraph the proof builds a level-ℓ Kikuchi graph—vertices are ℓ-subsets of two copies of [n], edges come from pairs of hyperedges intersecting in t vertices, and the quadratic form of its signed adjacency matrix captures the squared value of the q-XOR instance—then shows this graph is nearly regular after deleting a negligible fraction of vertices. The near-regularity is obtained from a polynomial concentration inequality applied to a degree polynomial whose partial derivatives are controlled by exactly the co-degree bounds in the definition of a good index.","core_discovery":"The central claim is Theorem 1.1: every binary q-query locally decodable code of constant distance satisfies k ≤ O($n^{{1−2/q}}$ $log^{4}$ n), and linear codes satisfy k ≤ O($n^{{1−2/q}}$ $log^{2}$ n), for every odd q ≥ 3. The paper establishes this by showing that the query sets of any such code form a hypergraph that can be decomposed, up to negligible loss, into pieces satisfying t-approximate strong regularity, and that on such pieces the associated q-XOR system is highly unsatisfiable. The central step is that the Kikuchi-matrix spectral method only needs co-degrees to be bounded relative to a chosen scale d_t, not in absolute value, so heavy tuples no longer force a reduction to an easier query model.","pith_inferences":["If approximate strong regularity is as portable as it appears, the same relative co-degree condition may yield refutation algorithms for semirandom satisfiability problems whose constraint hypergraphs are far from well-spread, a regime previous Kikuchi-matrix arguments could not enter.","The three inequalities defining a good index arose from exhausting bad scenarios in the Kikuchi graph; a testable extension would be to check whether the same index selection works when q is even or when the alphabet is large, where the even-q arguments might be recovered as a special case.","The log^4 factor likely overcounts: the paper's decomposition loses one log per peeling phase and the concentration step another, so a tighter accounting may reduce the bound to a single logarithm without changing the structural lemmas.","A direct test of the decomposition's optimality is to construct hypergraphs where the greedy peeling removes a constant fraction of edges at each phase; the lemma's O(q log n) pieces would then be tight up to constants, indicating where the log^4 factor in Theorem 1.1 might be intrinsic to the method."],"forward_implications":["Any odd-query binary locally decodable code, linear or not, has message length k ≤ O-tilde(n^{1−2/q}), removing the odd/even gap in the lower-bound trade-off.","The same bound extends to locally decodable codes over any finite alphabet of size up to n^{o(1)}, as the paper notes the method carries over.","The greedy decomposition provides a general structural lemma: any dense q-uniform hypergraph can be partitioned into O(q log n) approximately strongly regular pieces, each kept down to a prescribed error fraction.","For q=3 the theorem recovers the known near-cubic lower bound, so the new argument gives a uniform treatment of all odd q rather than relying on exponential 2-LDC bounds."],"supporting_citations":[{"why":"Introduced the semirandom CSP-refutation connection for 3-LDCs and identified odd q ≥ 5 as an open bottleneck that the present argument removes.","marker":"[AGKM23]"},{"why":"Supplied the Kikuchi-matrix spectral method and row-pruning argument that the main proof adapts to the relative co-degree setting.","marker":"[GKM22]"},{"why":"Provided the Kikuchi-graph framework and the matching-size fact used to compute the average degree of the constructed graph.","marker":"[HKM23]"},{"why":"Gave the even-cover formulation for linear LDCs and the weak rainbow-walk fact used in the linear-case proof.","marker":"[HKM+24]"},{"why":"Established the even-q lower bound k ≤ O-tilde(n^{1−2/q}) that the odd-q result now matches.","marker":"[GKST06]"},{"why":"Provided the even-q quantum lower bound that, together with the previous item, anchors the even-q benchmark.","marker":"[KW04]"},{"why":"Supplied the reduction to normally decodable codes that turns an arbitrary LDC into a union of q-uniform matchings.","marker":"[KT00]"},{"why":"Provided the polynomial concentration inequality used to control heavy vertices in the Kikuchi graph.","marker":"[SS12]"}],"fun_headline_variants":["Odd-query LDCs now match even-q bounds for all q","Improved lower bound for every odd-query LDC","New proof closes odd-query LDC gap for q≥5","Tight bounds for odd-query LDCs via approximate regularity","All odd-query LDCs achieve n^(1-2/q) bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof stands on the lemma that every nonincreasing co-degree sequence has an index t satisfying the three relative inequalities; if that lemma failed for some hypergraph, the decomposition into approximately strongly regular pieces and the subsequent Kikuchi-degree concentration would fall apart.","fun_headline_variants_meta":{"raw":{"variants":["Odd-query LDCs now match even-q bounds for all q","Improved lower bound for every odd-query LDC","New proof closes odd-query LDC gap for q≥5","Tight bounds for odd-query LDCs via approximate regularity","All odd-query LDCs achieve n^(1-2/q) bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001308,"raw_usage":{"total_tokens":5401,"prompt_tokens":1084,"completion_tokens":4317,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":700,"completion_tokens_details":{"reasoning_tokens":4228}},"tokens_in":700,"tokens_out":4317,"duration_ms":32159,"temperature":1.0,"reasoning_tokens":4228,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:18:18.225350+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A counterexample to Theorem 1.1 would be a binary 5-query locally decodable code with constant distance, blocklength n, and message length k = ω($n^{{3/5}}$ $log^{4}$ n). A cheaper, local falsifier targets the good-index lemma: generate random nonincreasing sequences γ_1 ≥ ... ≥ γ_q for q ∈ {5,7,9}, run the paper's two-step maximization algorithm, and check whether the selected index satisfies all three displayed inequalities; a single violation would break the decomposition.","supporting_citations":[],"review_version":1}