114 Kikuchi LDC — High Value
114.1 Overview
This module records the high-value observation (Lemma 5.1) of the Alrabiah–Guruswami–Kothari–Manohar near-cubic lower bound for \(3\)-query locally decodable codes: if \(C\) is \((3,\delta ,\varepsilon )\)-normally decodable, then the XOR instances \(\psi _b\) attached to \(C\) have large value, \(\mathbb {E}_b[\mathrm{val}(\psi _b)] \ge 2\varepsilon \). It is formalised here in the existential form asserting a single message and assignment on which the XOR polynomial already reaches \(2\varepsilon \).
114.2 Declarations
Let \(L\) be a normal form \((3,\delta ,\varepsilon )\)-decodable code with message length \(k \ge 1\) and block length \(n \ge 1\), and suppose its total number of constraints is positive, \(m \ge 1\). If the advantage parameter satisfies \(\varepsilon \le 1/2\), then there exist a message \(b : \mathrm{Fin}\, k \to \mathbb {Z}\) and an assignment \(x : \mathrm{Fin}\, n \to \mathbb {Z}\), each taking values in \(\{ -1, 1\} \), such that the XOR polynomial of \(L\) satisfies