117 Kikuchi LDC — Two XOR
117.1 Overview
This module covers §7 of the Alrabiah–Guruswami–Kothari–Manohar argument: refuting the \(2\)-XOR instance produced by the hypergraph decomposition. It records the abstract value of the \(2\)-XOR polynomial attached to the bipartite matchings \(G_i\), and the refutation bound stating that this value is \(O\! \left(n k \sqrt{\log n / d}\right)\) once the number of heavy pairs satisfies \(\left\lvert P\right\rvert \le nk/d\).
117.2 Declarations
For parameters \(k, n, d\) and a message \(b : \mathrm{Fin}\, k \to \mathbb {Z}\), the modelled value of the \(2\)-XOR polynomial \(g_b\) obtained from the decomposition, namely the real number
The definition is abstract: the quantity depends only on \(n\), \(k\) and the threshold \(d\), and is constant in the edge count and in \(b\).
Fix natural numbers \(k, n, d\) with \(k \ge 1\), \(n \ge 2\), and \(d \ge 1\). Then there is a positive constant \(C_0 \gt 0\) such that for every natural number \(n_P\) satisfying \(n_P\, d \le n k\), one has
where \(\log \) denotes the natural logarithm.