§8.1, pp. 18–19 — the weighted MAX-CUT instance of the Unique Label Cover → MAX-CUT reduction (noise ρ = −p/q, R table copies)
DefinitionOptInapprox_MaxCut_ReductionGraphThe weighted MAX-CUT instance produced from a Unique Label Cover instance by the PCP verifier of §8.1, with natural-number edge weights as allowed in §7.1.
Parameters. (number of copies of each Long Code table), (weight scale) and , , so that the noise rate is .
Vertices. The triples with , and , i.e. copies of the Long Code table of every ; they are numbered with (cubeEquiv).
Edges. For every , every two neighbours of , every and every there is an edge between
of multiplicity
with for a coordinate and for (so the second factor is times the verifier's probability of ). Self-loops, which arise exactly when , and and which no cut can cut, are omitted. The edge list is ordered lexicographically by .
The cut value of a partition is then (up to the omitted self-loops) the acceptance probability of the verifier "pick , then uniformly among the neighbours of , uniform, -biased, accept iff ", where is drawn with probability proportional to ; hence the edge is drawn with probability proportional to , i.e. nearly uniformly.
Relation to the paper. In the paper the Label Cover instance is assumed regular on the side (§8.1, using [38]); then all weights are equal and, for , the instance is exactly the paper's. The -dependent integer weights and the copies are formalization devices: the weights remove the regularity assumption (at the cost of a factor in the soundness analysis), and the copies make the omitted self-loops a fraction at most of the total weight. The lemma rgEdges_loopless certifies that the edge list has no self-loops.
import Mathlib
import Definitions.Def_OptInapprox_MaxCut_Verifier
namespace OptInapprox.MaxCut
noncomputable section
/-- The enumeration of the cube `{-1,1}^M` (points `Fin M → Bool`) by `Fin (2^M)`: the point `x`
gets the number `∑ᵢ [x i] 2^i` (TRUE contributes the bit `1`). -/
def cubeEquiv (M : ℕ) : (Fin M → Bool) ≃ Fin (2 ^ M) :=
(Equiv.arrowCongr (Equiv.refl (Fin M)) finTwoEquiv.symm).trans finFunctionFinEquiv
/-- The MAX-CUT vertex `(w, r, x)`: the point `x` of the `r`-th copy of the Long Code table of
`w ∈ W`, numbered `(w * R + r) * 2^M + code(x)`. -/
def rgVertex (L : ULC) (R : ℕ) (w : Fin L.nW) (r : Fin R) (x : Fin L.M → Bool) :
Fin (L.nW * R * 2 ^ L.M) :=
finProdFinEquiv (finProdFinEquiv (w, r), cubeEquiv L.M x)
/-- The numerator of the noise weight of `μ` for `ρ = -p/q`: `∏ᵢ (q ± p)`, with `q + p` for a
TRUE (`-1`) coordinate and `q - p` for a FALSE (`1`) coordinate; `muWeight (-p/q) μ` equals
`muNum p q μ / (2q)^M`. -/
def muNum (p q : ℕ) {M : ℕ} (μ : Fin M → Bool) : ℕ :=
∏ i, if μ i then q + p else q - p
/-- The integer weight `⌊K · |W| / deg(v)⌋` attached to the tests through the vertex `v ∈ V`
(approximately proportional to `1/deg(v)`, so that the edge `(v, w)` is picked nearly
uniformly). -/
def rgWeight (L : ULC) (K : ℕ) (v : Fin L.nV) : ℕ :=
K * L.nW / (L.nbrs v).card
/-- The weighted edge list of the MAX-CUT instance produced from the Unique Label Cover instance
`L` by the PCP verifier of §8.1 with `ρ = -p/q` (Long Code tables of the `W`-vertices, each
repeated `R` times): for every `v ∈ V`, neighbours `w, w'` of `v`, copies `r, r' < R`, `x` and
`μ` in the cube, the edge between `(w, r, x ∘ σ_{v,w})` and `(w', r', (x ∘ σ_{v,w'}) μ)` with
multiplicity `rgWeight v * muNum μ`; self-loops (which no cut can cut) are omitted. -/
def rgEdges (L : ULC) (R K p q : ℕ) :
List (Fin (L.nW * R * 2 ^ L.M) × Fin (L.nW * R * 2 ^ L.M)) :=
(List.finRange L.nV).flatMap fun v =>
(List.finRange L.nW).flatMap fun w =>
(List.finRange L.nW).flatMap fun w' =>
if (v, w) ∈ L.E ∧ (v, w') ∈ L.E then
(List.finRange R).flatMap fun r => (List.finRange R).flatMap fun r' =>
(List.finRange (2 ^ L.M)).flatMap fun a => (List.finRange (2 ^ L.M)).flatMap fun b =>
if rgVertex L R w r (compose ((cubeEquiv L.M).symm a) (L.σ v w)) =
rgVertex L R w' r' (coordMul (compose ((cubeEquiv L.M).symm a) (L.σ v w'))
((cubeEquiv L.M).symm b)) then []
else List.replicate (rgWeight L K v * muNum p q ((cubeEquiv L.M).symm b))
(rgVertex L R w r (compose ((cubeEquiv L.M).symm a) (L.σ v w)),
rgVertex L R w' r' (coordMul (compose ((cubeEquiv L.M).symm a) (L.σ v w'))
((cubeEquiv L.M).symm b)))
else []
theorem rgEdges_loopless (L : ULC) (R K p q : ℕ) : ∀ e ∈ rgEdges L R K p q, e.1 ≠ e.2 := by
intro e he
simp only [rgEdges, List.mem_flatMap, List.mem_finRange, true_and] at he
obtain ⟨v, w, w', he⟩ := he
split_ifs at he with h1
· simp only [List.mem_flatMap, List.mem_finRange, true_and] at he
obtain ⟨r, r', a, b, he⟩ := he
split_ifs at he with h2
· simp at he
· rw [List.mem_replicate] at he
rw [he.2]
exact h2
· simp at he
/-- The weighted MAX-CUT instance of §8.1 built from the Unique Label Cover instance `L`
(parameters: `R` copies of each Long Code table, weight scale `K`, noise rate `ρ = -p/q`). -/
def reductionGraph (L : ULC) (R K p q : ℕ) : WMaxCut :=
⟨L.nW * R * 2 ^ L.M, rgEdges L R K p q, rgEdges_loopless L R K p q⟩
end
end OptInapprox.MaxCut