A kq/q-2 Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
Oliver Janzer, Peter Manohar
Abstract
A code is a q-query locally decodable code (q-LDC) if one can recover any chosen bit of the message with good confidence by querying a corrupted string of the codeword in at most q coordinates. For 2 queries, the Hadamard code is a 2-LDC of length , and this code is in fact essentially optimal [1], [2]. For , there is a large gap in our understanding: the best constructions achieve , while prior to the recent work of [3], the best lower bounds were for q even and for q odd. The recent work of [3] used techniques from semirandom XOR refutation to prove a lower bound of for q = 3, thus achieving the “ bound” for an odd value of q. However, their proof does not extend to any odd . In this paper, we prove a q-LDC lower bound of 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.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
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
Cited by top-tier papers1
Builds on9
- Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than randomVenkatesan Guruswami, Pravesh K. Kothari, Peter ManoharSTOC 2022 · 18 citations
- A simple and sharper proof of the hypergraph Moore boundJun-Ting Hsieh, Pravesh K. Kothari, Sidhanth MohantySODA 2023 · 13 citations
- 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
- Strongly refuting all semi-random Boolean CSPsJackson Abascal, Venkatesan Guruswami, Pravesh K. KothariSODA 2021 · 7 citations
- An Exponential Lower Bound for Linear 3-Query Locally Correctable CodesPravesh K. Kothari, Peter ManoharSTOC 2024 · 7 citations
Related papers
- Improved Lower Bounds for all Odd-Query Locally Decodable CodesArpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari, Andrew D. LinFOCS 2025 · 1 citation
- 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
- Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow CyclesOmar Alrabiah, Venkatesan GuruswamiFOCS 2024 · 2 citations
- A Stronger Bound for Linear 3-LCCTal YankovitzFOCS 2024 · 1 citation
- Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for DesignsPravesh K. Kothari, Peter ManoharFOCS 2024 · 2 citations
