Parameters and scales for the oracle learner
DefinitionCNFLearning873_Valiant_Supplement_OracleParameterscnf-learningcombinatoricsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
All displayed logarithms here are base two. For the algorithm of pp.27–30, set
There are at most integer draws; use rejection limit . Explicit numerical scales represent the sample, oracle-call, query-size and time conclusions; a polynomial envelope is . The good-sample event says every Valiant survivor has violation probability at most . No asymptotic bound is assumed by any definition. The theorem domains have , positive accuracy and confidence parameters below one.
Definition code
import Definitions.Def_CNFLearning873_Valiant_Learner
noncomputable section
namespace CNFLearning873.Valiant.Supplement
/-- All logarithms in the algorithm's displayed parameters are base two. -/
def radius (n : ℕ) : ℝ := n / log₂ n ^ 2
def rounds (n k d : ℕ) (ε δ : ℝ) : ℕ :=
Nat.ceil (100 * (k : ℝ) * d * n * log₂ ((n : ℝ) / (ε * δ)))
def learningSamples (n k d : ℕ) (ε δ : ℝ) : ℕ :=
Nat.ceil (10 ^ 6 * (k : ℝ) ^ 2 * d * (n / ε) * log₂ ((n : ℝ) / (ε * δ)) ^ 4)
def drawsBound (n ℓ : ℕ) : ℕ := 100 * n * ℓ ^ 2 + n * ℓ
def rejectionLimit (n ℓ : ℕ) (δ : ℝ) : ℕ :=
Nat.ceil (log₂ (3 * (drawsBound n ℓ : ℝ) / δ))
/-- Explicit polynomial envelope; its degree and coefficient are quantified in the theorems. -/
def polynomialScale (n : ℕ) (ε δ : ℝ) (p : ℕ) : ℝ :=
(1 + (n : ℝ) + 1 / ε + log₂ (1 / δ)) ^ p
def sampleScale65 (n : ℕ) (ε δ : ℝ) : ℝ :=
(n : ℝ) / ε * log₂ ((n : ℝ) / (ε * δ)) ^ 4
def oracleExponent (n : ℕ) : ℝ := (n : ℝ) / log₂ n
def timeExponent (n : ℕ) : ℝ :=
(n : ℝ) * log₂ (log₂ n) / Real.sqrt (log₂ n)
def queryScale (n k : ℕ) (ε δ : ℝ) : ℝ :=
(n : ℝ) ^ k + n * log₂ ((n : ℝ) / (ε * δ))
/-- The good-learning-sample event of Lemma 6.7. -/
def GoodSamples {n T : ℕ} (F : CNF n) (h : (solutions F).Nonempty)
(k ℓ : ℕ) (ε : ℝ) (xs : Fin T → Assignment n) : Prop :=
∀ c ∈ output k xs, q F h c ≤ ε / (1000 * (ℓ : ℝ) * log₂ n ^ 2)
end CNFLearning873.Valiant.Supplement
Source
Weiming Feng, Yixiao Yu, Yiyao Zhang, STOC 2027 submission #873 (October 2026), Theorem 6.5, Complexity paragraph, and Lemma 6.7, printed pp.27–30 = 1-based PDF pp.27–30; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/873.pdf