Lune

FOCS2025Top-tier venue

A kq/q-2 Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs

Oliver Janzer, Peter Manohar

Abstract

A code C:{0,1}k→{0,1}n\mathcal{C}:\{0,1\}^{k} \rightarrow\{0,1\}^{n} is a q-query locally decodable code (q-LDC) if one can recover any chosen bit bib_{i} of the message b∈{0,1}kb \in\{0,1\}^{k} with good confidence by querying a corrupted string x~\tilde{x} of the codeword x=C(b)x=\mathcal{C}(b) in at most q coordinates. For 2 queries, the Hadamard code is a 2-LDC of length n=2kn=2^{k}, and this code is in fact essentially optimal [1], [2]. For q≥3q \geq 3, there is a large gap in our understanding: the best constructions achieve n=exp⁡(ko(1))n=\exp \left(k^{o(1)}\right), while prior to the recent work of [3], the best lower bounds were n≥Ω~(kqq−2)n \geq \tilde{\Omega}\left(k^{\frac{q}{q-2}}\right) for q even and n≥Ω~(kq+1q−1)n \geq \tilde{\Omega}\left(k^{\frac{q+1}{q-1}}\right) for q odd. The recent work of [3] used techniques from semirandom XOR refutation to prove a lower bound of n≥Ω~(k3)n \geq \tilde{\Omega}\left(k^{3}\right) for q = 3, thus achieving the “ kqq−2k^{\frac{q}{q-2}} bound” for an odd value of q. However, their proof does not extend to any odd q≥5q \geq 5. In this paper, we prove a q-LDC lower bound of n≥Ω~(kqq−2)n \geq \tilde{\Omega}\left(k^{\frac{q}{q-2}}\right) 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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random cites Strongly refuting all semi-random Boolean CSPs
  • A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation cites Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
  • A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation cites A simple and sharper proof of the hypergraph Moore bound
  • A simple and sharper proof of the hypergraph Moore bound cites Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
  • Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies cites A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
  • An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes cites Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
  • An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes cites A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
  • An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes cites A simple and sharper proof of the hypergraph Moore bound
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust DaisiesGuy Goldberg, Tom Gur, Sidhant SaraogiSTOC 2026 · 5 citations

Builds on9

  1. Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than randomVenkatesan Guruswami, Pravesh K. Kothari, Peter ManoharSTOC 2022 · 18 citations
  2. A simple and sharper proof of the hypergraph Moore boundJun-Ting Hsieh, Pravesh K. Kothari, Sidhanth MohantySODA 2023 · 13 citations
  3. A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP RefutationOmar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, Peter ManoharSTOC 2023 · 9 citations
  4. Strongly refuting all semi-random Boolean CSPsJackson Abascal, Venkatesan Guruswami, Pravesh K. KothariSODA 2021 · 7 citations
  5. An Exponential Lower Bound for Linear 3-Query Locally Correctable CodesPravesh K. Kothari, Peter ManoharSTOC 2024 · 7 citations

Related papers

  1. Improved Lower Bounds for all Odd-Query Locally Decodable CodesArpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari, Andrew D. LinFOCS 2025 · 1 citation
  2. Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear CodesElena Grigorescu, Vinayak M. Kumar, Peter Manohar, Geoffrey MonSTOC 2026 · 4 citations
  3. Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow CyclesOmar Alrabiah, Venkatesan GuruswamiFOCS 2024 · 2 citations
  4. A Stronger Bound for Linear 3-LCCTal YankovitzFOCS 2024 · 1 citation
  5. Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for DesignsPravesh K. Kothari, Peter ManoharFOCS 2024 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines