Pith. sign in

REVIEW 1 major objections 4 minor 22 references

A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs

T0 review · 1 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read All odd query counts now hit the k^{q/(q-2)} LDC bound.

desk verdict 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. read the letter →

arxiv 2411.14276 v2 pith:WJECPUJG submitted 2024-11-21 cs.CC cs.ITmath.IT

Oliver Janzer , Peter Manohar This is my paper · ORCID
classification cs.CCcs.ITmath.IT MSC 68Q1794B6505C65
keywords locallydecodablecodesspectralrefutationKikuchimatricesbipartitegraphodd-arityXORlowerboundshypergraphdecomposition
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 4 minor

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.

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 (1)
  1. [Section 4, proof of Theorem 1 (small-|P_s| case)] 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.
minor comments (4)
  1. [Section 5, Lemma 5.1] 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.
  2. [Section 4.1, Algorithm 4.4] 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.
  3. [Remark 2.4] 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.
  4. [Section 3.3, Fact 3.6] There is a stray bracket in the statement of the rectangular Matrix Khintchine inequality ('∥∑ X_i X_i^⊤]∥'); the notation should be cleaned up.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the spectral derivation is self-contained, with one repairable corner-case correctness gap that is not circular.

full rationale

The derivation is self-contained relative to the claimed theorem. Starting from the standard normal-form reduction (Fact 3.5, cited to Yek12, not to the authors), the proof bounds E_b[val(Phi_b)] from below by εδnk and from above using explicitly proved spectral statements: Theorem 4.2 for the regular q-XOR instance and Theorem 4.3 for the bipartite instances. The Kikuchi matrices, row-pruning lemmas, and Matrix Khintchine applications are proved in Sections 4-6 of this paper; citations to AGKM23, GKM22, KM24a, KM24b, and Yan24 supply methodology, not black-box theorems that assume the target bound. Parameter choices such as ℓ = n^{1-2/q}δ^{-2/q} and the thresholds d_t = (ℓ/n)^{t-3/2}k are chosen to balance inequalities and are not fitted to data. I find no pattern of self-definition, fitted-input-called-prediction, imported uniqueness, or ansatz-smuggling. I do flag a genuine defect in the written proof: in the small |P_s| case of the proof of Theorem 1, the assertion that "each p ∈ P_s contributes at most d_s hyperedges to ∪_i H_i^{(s)}" is not justified under Algorithm 4.4, since a heavy p can be processed repeatedly and contribute up to k hyperedges; this is repairable by padding P_s as noted by the skeptic. That is a correctness gap in a corner case, not a circular step. Remark 2.4's admission that "inherently bipartite" is informal is likewise a limitation, not a circularity. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No empirical or fitted parameters exist; proof parameters l and d_t are analytical choices made to balance terms, not fits to data. The paper relies on standard tools: LDC normal form, Matrix Khintchine, binomial asymptotics, and the matching structure of the decomposed hypergraphs. No new physical or metaphysical entities are introduced; the bipartite Kikuchi graph is a mathematical construction.

assumptions (4)
  • domain assumption Fact 3.5: Reduction to LDC normal form.
    Assumes any (q,delta,epsilon)-LDC can be transformed into one with q-uniform matching query hypergraphs of size at least delta n, losing only constant factors. This is the entry point of the spectral proof.
  • standard math Fact 3.6: Rectangular Matrix Khintchine inequality.
    Used to bound the spectral norm of sums of independent random matrices in Claims 5.5 and 6.4.
  • standard math Fact 3.7: Binomial coefficient asymptotics.
    Used throughout to estimate average degrees and vertex set sizes in Kikuchi matrices.
  • domain assumption Matching structure of query hypergraphs in normal form.
    The row pruning steps in Lemmas 5.4 and 6.3 rely on each H_i being a matching; without this, the conditional first moment bounds and the guaranteed existence of a large approximately regular subgraph would not hold.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs." pith.science (2026). https://pith.science/paper/WJECPUJG

@misc{pith2026241114276,
  author       = {Pith},
  title        = {Pith review of: A $k^\fracqq-2$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WJECPUJG}},
  note         = {Machine review of arXiv:2411.14276}
}
abstract

A code $C \colon \{0,1\}^k \to \{0,1\}^n$ is a $q$-query locally decodable code ($q$-LDC) if one can recover any chosen bit $b_i$ of the message $b \in \{0,1\}^k$ with good confidence by querying a corrupted string $\tilde{x}$ of the codeword $x = C(b)$ in at most $q$ coordinates. For $2$ queries, the Hadamard code is a $2$-LDC of length $n = 2^k$, and this code is in fact essentially optimal. For $q \geq 3$, there is a large gap in our understanding: the best constructions achieve $n = \exp(k^{o(1)})$, while prior to the recent work of [AGKM23], the best lower bounds were $n \geq \tilde{\Omega}(k^{\frac{q}{q-2}})$ for $q$ even and $n \geq \tilde{\Omega}(k^{\frac{q+1}{q-1}})$ for $q$ odd. The recent work of [AGKM23] used techniques from semirandom XOR refutation to prove a lower bound of $n \geq \tilde{\Omega}(k^3)$ for $q = 3$, thus achieving the "$k^{\frac{q}{q-2}}$ bound" for an odd value of $q$. However, their proof does not extend to any odd $q \geq 5$. In this paper, we prove a $q$-LDC lower bound of $n \geq \tilde{\Omega}(k^{\frac{q}{q-2}})$ for any odd $q$. Our key technical idea is the use of an imbalanced bipartite Kikuchi graph, which gives a simpler method to analyze spectral refutations of odd arity XOR without using the standard "Cauchy-Schwarz trick", a trick that typically produces random matrices with nontrivially correlated entries and makes the analysis for odd arity XOR significantly more complicated than even arity XOR.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 20 canonical work pages

  1. [1]

    Near-tight bounds for 3-query locally correctable binary linear codes via rainbow cycles

    [AG24] Omar Alrabiah and Venkatesan Guruswami. Near-tight bounds for 3-query locally correctable binary linear codes via rainbow cycles. In65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30,

    work page 2024

  2. [5]

    Kothari, and Andrew D

    [BHKL24] Arpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari, and Andrew D. Lin. Improved lower bounds for all odd-query locally decodable codes.CoRR, abs/2411.14361,

    arXiv

  3. [6]

    Noisy Tensor Completion via the Sum-of-Squares Hierarchy

    [BM16] Boaz Barak and Ankur Moitra. Noisy Tensor Completion via the Sum-of-Squares Hierarchy. InProceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, volume 49 ofJMLR Workshop and Conference Proceedings, pages 417–445. JMLR.org,

    work page 2016

  4. [10]

    3-query locally decodable codes of subexponential length

    [Efr09] Klim Efremenko. 3-query locally decodable codes of subexponential length. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 39–44. ACM,

    work page 2009

  5. [14]

    On the hardness of information-theoretic multiparty computation

    [IK04] Yuval Ishai and Eyal Kushilevitz. On the hardness of information-theoretic multiparty computation. InAdvances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004, Proceedings, volume 3027 ofLecture Notes in Computer Science, pages 439–455. Springer,

    work page 2004

  6. [16]

    Exponentiallowerboundsforsmooth3-lccsand sharp bounds for designs

    [KM24b] PraveshK.KothariandPeterManohar. Exponentiallowerboundsforsmooth3-lccsand sharp bounds for designs. In65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30,

    work page 2024

  7. [18]

    Strongly refuting random CSPs below the spectral threshold

    [RRS17] Prasad Raghavendra, Satish Rao, and Tselil Schramm. Strongly refuting random CSPs below the spectral threshold. InProceedings of the 49th Annual ACM SIGACT Symposium 30 on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 121–131. ACM,

    work page 2017

  8. [22]

    A stronger bound for linear 3-lcc

    [Yan24] Tal Yankovitz. A stronger bound for linear 3-lcc. In65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30,

    work page 2024

Show all 22 references
  1. [1991]

    Romashchenko

    [Rom06] Andrei E. Romashchenko. Reliable computations based on locally decodable codes. In STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings, volume 3884 ofLecture Notes in Computer Science, pages...

    2006

  2. [1998]

    Allen, Ryan O’Donnell, and David Witmer

    [AOW15] Sarah R. Allen, Ryan O’Donnell, and David Witmer. How to Refute a Random CSP. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 689–708. IEEE Computer Society,

    2015

  3. [2004]

    Kothari and Peter Manohar

    [KM24a] Pravesh K. Kothari and Peter Manohar. An exponential lower bound for linear 3-query locally correctable codes. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 776–787. ACM,

    2024

  4. [2005]

    Onmatrixrigidityandlocallyself-correctablecodes

    [Dvi10] ZeevDvir. Onmatrixrigidityandlocallyself-correctablecodes. In Proceedingsofthe25th AnnualIEEEConferenceonComputationalComplexity,CCC2010,Cambridge,Massachusetts, USA, June 9-12, 2010, pages 291–298. IEEE Computer Society,

    2010

  5. [2006]

    Kothari, and Sidhanth Mohanty

    [HKM23] Jun-Ting Hsieh, Pravesh K. Kothari, and Sidhanth Mohanty. A simple and sharper proofofthehypergraphMoorebound. In Proceedingsofthe2023ACM-SIAMSymposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 2324–2344. SIAM,

    2023

  6. [2007]

    Efficient and error-correcting data structures for membership and polynomial evaluation

    [CGW10] Victor Chen, Elena Grigorescu, and Ronald de Wolf. Efficient and error-correcting data structures for membership and polynomial evaluation. In27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France, volume 5 o...

    2010

  7. [2009]

    Kothari, and Peter Manohar

    [GKM22] Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar. Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. InSTOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 678–689. ACM,

    2022

  8. [2010]

    Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits

    [DS05] Zeev Dvir and Amir Shpilka. Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. InProceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 592–601. ACM,

    2005

  9. [2015]

    Wein, Ahmed El Alaoui, and Cristopher Moore

    [WAM19] Alexander S. Wein, Ahmed El Alaoui, and Cristopher Moore. The Kikuchi Hierarchy and Tensor PCA. In60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1446–1468. IEEE Computer Society,

    2019

  10. [2017]

    Some applications of coding theory in computational complexity.arXiv preprint cs/0409044,

    [Tre04] Luca Trevisan. Some applications of coding theory in computational complexity.arXiv preprint cs/0409044,

    arXiv

  11. [2019]

    Error-correcting data structures

    [Wol09] Ronald de Wolf. Error-correcting data structures. In26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, Proceedings, volume 3 ofLIPIcs, pages 313–324. Schloss Dagstuhl - Leibniz- Zentrum für Info...

    2009

  12. [2021]

    Kothari, and Peter Manohar

    [AGKM23] Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar. A near-cubic lower bound for 3-query locally decodable codes from semirandom CSP refutation. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA,...

    2023

  13. [2023]

    Kothari, Sidhanth Mohanty, David Munhá Correia, and Benny Sudakov

    [HKM+24] Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty, David Munhá Correia, and Benny Sudakov. Small even covers, locally decodable codes and restricted subgraphs of edge-colored kikuchi graphs.CoRR, abs/2401.11590,

    arXiv

  14. [2024]

    [AGK21] Jackson Abascal, Venkatesan Guruswami, and Pravesh K. Kothari. Strongly refuting all semi-random Boolean CSPs. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 454–472. SIAM,

    2021

Pith tools

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