RandomizedSubmodTester
A randomized tester making at most q queries, modeled as a finite probability distribution over deterministic decision trees of depth at most q.
Statement
structure RandomizedSubmodTester (n k q : ℕ)- Defined in
- arXiv:2611.02374, Def. 2.5
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Built on 1
- SubmodQueryTreeAn adaptive deterministic query decision tree of depth at most d for testing functions on the Boolean hypercube into {0, ..., k}.
- Used by 1
- randomized_submod_tester_accept_probThe probability that a randomized tester accepts an input function f, given by the expected acceptance over its decision trees.
Read back from the Lean
RandomizedSubmodTester n k q is a structure parameterized by natural numbers n, k, and q. An instance consists of:
1. m : ℕ, a natural number specifying the size of the support;
2. prob : Fin m → ℝ, a probability assigned to each index in Fin m;
3. prob_nonneg : ∀ i : Fin m, 0 ≤ prob i, asserting that every probability is non-negative;
4. prob_sum : ∑ i : Fin m, prob i = 1, asserting that the sum of the probabilities over Fin m equals 1;
5. tree : Fin m → SubmodQueryTree n k q, associating to each index in Fin m a query tree of depth parameter q.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A randomized tester of query complexity q, given by a probability distribution over decision trees of depth q. -/ structure RandomizedSubmodTester (n k q : ℕ) where m : ℕ prob : Fin m → ℝ prob_nonneg : ∀ i, 0 ≤ prob i prob_sum : ∑ i, prob i = 1 tree : Fin m → SubmodQueryTree n k q