Theorem 8.9, depth-two case — monotone coin formulas of size exp(O(1/epsilon))
ProvedSemAC02.Supplement.theorem_8_9_depth_two_coin_formulasFor all sufficiently small , there is a monotone AND/OR formula of depth at most two, in the source's normal form, solving the -coin problem with error at most and tree size at most
where is an absolute constant chosen before . The two coin biases are and .
This is the depth-two instance of Theorem 8.9 in Hard Instances for Strong Semantic Proof Systems. It is a supporting base case for the full fixed-depth theorem, not a claim about depths greater than two. The displayed inverse is exactly the theorem's exponent at .
Formalization Note: IsReduced expresses the paper's circuit normal form, size counts tree nodes, and bernProb is the finite product-probability sum. The bias threshold and exponent constant are existential constants as in the source.
import Mathlib import Definitions.Def_SemAC02_Circ import Definitions.Def_SemAC02_bernProb import Definitions.Def_SemAC02_IsCoinDistinguisher
namespace SemAC02.Supplement
theorem theorem_8_9_depth_two_coin_formulas :
∃ A ε₀ : ℝ, 0 < ε₀ ∧ ∀ ε : ℝ, 0 < ε → ε < ε₀ →
∃ (m : ℕ) (T : Circ (Fin m)), IsMonotoneCirc T ∧ IsReduced T ∧ T.depth ≤ 2 ∧
(T.treeSize : ℝ) ≤ Real.exp (A*ε⁻¹) ∧
IsCoinDistinguisher ε (1/10) (fun x => T.eval x) := by sorry
end SemAC02.Supplement