Lemma 8.11 — amplification by conjunction
ProvedSemAC02.Supplement.lemma_8_11_amplificationac0-2-fregecoin-problemproof-complexitysemantic-proof-systemssupporting-lemma
Fix . For all sufficiently small and every integer , there is a monotone AND-rooted formula on some inputs, in the paper's normal form, of depth at most and tree size at most , where depends only on , with acceptance probability at least under and at most under .
This is Lemma 8.11 of the source, used between Lemmas 8.10 and 8.12. The asymptotic size constant is absorbed into the exponent constant , chosen before and . The explicit finite sum bernProb represents the product probability; IsReduced gives the source's normal-form convention; size is the number of tree nodes. The statement includes and retains an AND root.
Preamble
import Mathlib import Definitions.Def_SemAC02_Circ import Definitions.Def_SemAC02_bernProb
Formal statement
namespace SemAC02.Supplement
theorem lemma_8_11_amplification (d : ℕ) (hd : 2 ≤ d) :
∃ A ε₀ : ℝ, 0 < ε₀ ∧ ∀ ε : ℝ, 0 < ε → ε < ε₀ → ∀ t : ℕ, 1 ≤ t →
∃ m : ℕ, 1 ≤ m ∧ ∃ T : Circ (Fin m), IsMonotoneCirc T ∧ IsReduced T ∧
(∃ cs, T = Circ.and cs) ∧ T.depth ≤ d ∧
(T.treeSize : ℝ) ≤ (t : ℝ) * Real.exp (A * ε ^ (-1 / ((d : ℝ) - 1))) ∧
(4 / 5 : ℝ) ^ t ≤ bernProb (1 / 2) (fun x => T.eval x) ∧
bernProb (1 / 2 - ε) (fun x => T.eval x) ≤ (1 / 5 : ℝ) ^ t := by sorry
end SemAC02.Supplement
Source
Alekseev, Gryaznov, Itsykson, Pitassi, Robere, Tzameret, Hard Instances for Strong Semantic Proof Systems: CNFs for Depth-Four PC and Deep Instances for AC0[2]-Frege, Lemma 8.11 (Amplification by conjunction), printed p.66, proof at p.67 in the public source https://www.doc.ic.ac.uk/~itzamere/Reslin_Simplification.pdf. The mission-pinned PDF has a different hash; the public source statement and proof have been checked.