Manuscript Oai119-A@1 · Oai119-A.tex · section · fdff7292

The frozen instance and its entire kernel

Stages 3 and 6: the complete finite certificate › The frozen instance and its entire kernel · lines 737–778

Oai119-A@1#eq:frozen, Oai119-A@1#eq:fourmatrix, Oai119-A@1#eq:lossgap

Fix

n = 2, ρ_{0} = \frac{1}{2}, ε_{0} = \frac{1}{4}, s_{0} = H (ρ_{0}) = \frac{3}{2}, C_{0} = 1 - s_{0} .

Order the cube as

v_{1} = (1, 1), v_{2} = (1, - 1), v_{3} = (- 1, 1), v_{4} = (- 1, - 1) .

The complete noise matrix is

K_{ρ_{0}} = \frac{1}{16} 9331391331931339 .

Its row and column sums are one. The joint law of $(X, Y)$ is $K_{ρ_{0}} /4$ .

For Boolean $f$ , define its Hellinger loss and its gap from the coordinate bound by

L (f) = H (E f) - E H (T_{ρ_{0}} f), Γ (f) = C_{0} - L (f) .

Concavity of $H$ and mean preservation imply $L (f) \geq 0$ .

Displayed formulas in this passage

Oai119-A@1#eq:frozen · line 740
$n = 2, ρ_{0} = \frac{1}{2}, ε_{0} = \frac{1}{4}, s_{0} = H (ρ_{0}) = \frac{3}{2}, C_{0} = 1 - s_{0} .$
Oai119-A@1#eq:fourmatrix · line 753
$K_{ρ_{0}} = \frac{1}{16} 9331391331931339 .$
Oai119-A@1#eq:lossgap · line 770
$L (f) = H (E f) - E H (T_{ρ_{0}} f), Γ (f) = C_{0} - L (f) .$
unlabeled · line 748
$v_{1} = (1, 1), v_{2} = (1, - 1), v_{3} = (- 1, 1), v_{4} = (- 1, - 1) .$