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

Oliver Janzer, Peter Manohar

A code $C:\{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 confide…