The canonical distributions and the parameters , of Theorem 6.1
DefinitionLiftSAParity_Supplement_canonDistlocal-distributionsp2o-gran-per-chapterp2o-plan-paperp2o-v1proof-complexitysherali-adams
Let be a CNF formula over blocks of variables.
- For a set of blocks , the canonical distribution is the uniform distribution on
- is the maximum, over sets of at most blocks, of the number of clauses of whose variables all lie in .
- The uniform-extension falsification bound with parameter holds if, for every blockwise partial assignment that falsifies no clause and every set of at most blocks, a uniformly random extension of to falsifies some clause of whose variables all lie in with probability at most .
These are the data of Theorem 6.1, which gives a sufficient condition for to be fooling.
Formalization Note canonDist φ I is defined for every . When no assignment avoids the axioms its values are all , so the hypothesis that is a block -local distribution then fails; this is the paper's remark that at least one such must exist for to be well-defined. maxLocalClauses φ d is and UniformExtFalsifyBound φ d p is item 3.
Definition code
import Mathlib
import Definitions.Def_LiftSAParity_Supplement_IsBlockLocalDist
namespace LiftSAParity
namespace Supplement
open Classical
/-- The blockwise partial assignment `τ` falsifies no clause of `φ` whose variables all lie in its
blocks ("x does not violate axioms of φ", de Rezende–Engström–Shekhovtsov, *Lifting Sherali-Adams
Degree to Unary Sherali-Adams over Parities Size*, manuscript (sha256 cab5a032…), §6.1, p.20). -/
def NoFalsified {n ℓ : ℕ} (φ : CNF (Fin n × Fin ℓ)) {I : Finset (Fin n)}
(τ : BlockAssign n ℓ I) : Prop :=
∀ C ∈ φ, ¬ FalsifiesOn τ C
/-- **The canonical distributions** `D^φ` (§6.1, p.20): "For I ⊆ [n] of size at most d, let us set
D^φ_I to be the uniform distribution on the set {x ∈ {0,1}^{I×[ℓ]} : x does not violate axioms of
φ}."
**Formalization Note** Defined for every `I` (the constraint `|I| ≤ d` enters through
`IsBlockLocalDist φ d (canonDist φ)`). If no `x` satisfies the axioms the values are all `0`, so
`D^φ_I` is not a probability distribution and the hypothesis "D^φ is a d-local distribution"
fails, which is the paper's "there should be at least one x … for D^φ_I to be well-defined". -/
noncomputable def canonDist {n ℓ : ℕ} (φ : CNF (Fin n × Fin ℓ)) (I : Finset (Fin n))
(τ : BlockAssign n ℓ I) : ℝ :=
if NoFalsified φ τ then
1 / ((Finset.univ.filter (fun τ' : BlockAssign n ℓ I => NoFalsified φ τ')).card : ℝ)
else 0
/-- `m` of Theorem 6.1 (p.20): "the maximum number of clauses of φ whose variables all lie in some
set of at most d blocks", i.e. `max_{I ⊆ [n], |I| ≤ d} |{C ∈ φ : vars(C) ⊆ I × [ℓ]}|`. -/
noncomputable def maxLocalClauses {n ℓ : ℕ} (φ : CNF (Fin n × Fin ℓ)) (d : ℕ) : ℕ :=
(Finset.univ.filter (fun I : Finset (Fin n) => I.card ≤ d)).sup
(fun I => (φ.filter (fun C => ∀ l ∈ C, l.1.1 ∈ I)).card)
/-- The hypothesis of Theorem 6.1 (p.20): "every blockwise partial assignment that does not
falsify any clause, when extended uniformly to any set of at most d blocks, falsifies a clause
with probability at most p". For every blockwise `σ` (support `S`) falsifying no clause inside
its blocks and every `I ⊇ S` with `|I| ≤ d`, a uniformly random `τ ∈ {0,1}^{I×[ℓ]}` agreeing with
`σ` falsifies some clause of `φ` whose variables all lie in `I × [ℓ]` with probability `≤ p`. -/
def UniformExtFalsifyBound {n ℓ : ℕ} (φ : CNF (Fin n × Fin ℓ)) (d : ℕ) (p : ℝ) : Prop :=
∀ (S : Finset (Fin n)) (σ : BlockAssign n ℓ S), NoFalsified φ σ →
∀ I : Finset (Fin n), S ⊆ I → I.card ≤ d →
((Finset.univ.filter
(fun τ : BlockAssign n ℓ I => Compat τ σ ∧ ∃ C ∈ φ, FalsifiesOn τ C)).card : ℝ) /
((Finset.univ.filter (fun τ : BlockAssign n ℓ I => Compat τ σ)).card : ℝ) ≤ p
end Supplement
end LiftSAParity
Source
de Rezende, Engström, Shekhovtsov, Lifting Sherali-Adams Degree to Unary Sherali-Adams over Parities Size (manuscript, sha256 cab5a032…), §6.1, p.20 (canonical distributions; Theorem 6.1)