115 Kikuchi LDC — Main Theorem

115.1 Overview

This module states the two final lower bounds of the Alrabiah–Guruswami–Kothari–Manohar development: the main near-cubic bound for \(3\)-query locally decodable codes, \(k^3 \le n \cdot O(\log ^6 n / (\varepsilon ^{16} \delta ^{16}))\), equivalently \(n = \Omega (k^3 / \mathrm{polylog}\, k)\) for constant \(\delta , \varepsilon \); and the corresponding bound \(k \le n^{1 - 2/q} \cdot O(\log n / (\varepsilon ^4 \delta ^2))\) for \(q\)-query codes with \(q\) even, obtained from the Kikuchi matrix for even arity.

115.2 Declarations

Theorem 115.1 Cubic lower-bound inequality for 3-query locally decodable codes

✓

Let \(k \ge 1\) and \(n \ge 2\) be integers, and let \(\delta , \varepsilon \in (0,1]\). Suppose \(L\) is a normal form \((3,\delta ,\varepsilon )\)-decodable code with message length \(k\) and block length \(n\), whose density parameter equals \(\delta \) and whose advantage parameter equals \(\varepsilon \). Then there exists a real constant \(C \gt 0\) for which

\[ k^3 \; \le \; \frac{n \, C \, (\log n)^6}{\varepsilon ^{16}\, \delta ^{16}} . \]

Here \(C\) is quantified after \(k\), \(n\), \(\delta \), \(\varepsilon \) and the code \(L\) have been fixed, so it is permitted to depend on all of them.

Theorem 115.2 A constant bound on \(k\) of order \(n^{1-2/q}\log n\)

✓

Let \(q\) be an even integer with \(q \ge 2\), let \(k \ge 1\) and \(n \ge 2\) be integers, and let \(\delta , \varepsilon \gt 0\). Then there exists a constant \(C \gt 0\) such that

\[ k \; \le \; n^{\, 1 - 2/q}\cdot \frac{C \, \log n}{\varepsilon ^{4}\, \delta ^{2}}. \]