A finite-bit learner for , the full Boolean class on
DefinitionReplParity_Supplement_pnLearnerfinite-bit-modellearning-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1pac-learningreplicability
is the class of all functions , written as -bit truth tables. A sample point is identified with the labeled example over , where is the -th standard basis vector; learning is parity learning with the marginal supported on the standard basis, since .
Given a total function on the base mission's machine inputs , the learner runs on the sample and a seed of bits, and reads the output as or as the truth table given by its bits.
This is the learner object of statements 1 and 3 of Theorem 5.3.
Formalization Note Sample points are encoded with the base mission's fixed example encoding, of length , which is polynomial in the dimension.
Definition code
import Mathlib
import Definitions.Def_ReplParity_Vec
import Definitions.Def_ReplParity_runLearner
set_option autoImplicit false
namespace ReplParity
namespace Supplement
/-- A labeled point `(i, b)` of `[n] × {0, 1}` as the lifted example `(e_i, b)` over `𝔽ⁿ₂`
(§2.1, p.11: "The map i ↦ e_i embeds [n] into 𝔽ⁿ₂"). -/
def toExample {n : ℕ} (p : Fin n × ZMod 2) : Example n :=
(Pi.single p.1 1, p.2)
/-- **A finite-bit learner for `P_n`.** Shen, Zhong, *Replicable Parity Learning: Cubic Sample
Complexity and a Geometric Characterization*, STOC 2027 submission (manuscript sha256 40424491…),
§2.1, p.11 (PDF p.13): "Let P_n be the class of all functions [n] → {0, 1}, represented by n-bit
truth tables. The map i ↦ e_i embeds [n] into 𝔽ⁿ₂, and every function on [n] is the restriction of
a parity under this map … So learning P_n is the special case of parity learning in which the
marginal distribution is supported on the standard basis."
`pnLearner A n ε δ ρ` runs the total function `A` (a machine of the base mission's finite-bit model,
input `ReplParity.LInput`) on the sample `S` of labeled points of `[n]`, each written as the example
`(e_i, b)` over `𝔽ⁿ₂`, and on the seed `r`. The output is `⊥` (`none`) or the truth table
`Fin n → ZMod 2` read from the output bits (`ReplParity.learnerOutput`).
**Formalization Note.** The encoding of a sample point `(i, b)` is the base mission's
`exampleBits (e_i, b)`, fixed independently of any learner; its length `n + 1` is polynomial in the
dimension, so polynomial time is unaffected. -/
def pnLearner (A : LInput → Option (List Bool)) (n : ℕ) (ε δ ρ : ℚ) {m R : ℕ}
(S : Fin m → Fin n × ZMod 2) (r : Fin R → Bool) : Option (Fin n → ZMod 2) :=
learnerOutput A n ε δ ρ (fun i => toExample (S i)) r
end Supplement
end ReplParity
Source
Shen, Zhong, Replicable Parity Learning: Cubic Sample Complexity and a Geometric Characterization, STOC 2027 submission (manuscript sha256 40424491d00eef39c790dd41b7557e0ffdf9de2d14d95ddcd611aeacb0f77a50), §2.1 "The full Boolean class on a known finite domain", p.11 (PDF p.13)