AFTD Auto-Formalizing Theoretical Domains

randomized_submod_tester_accept_prob

def

The probability that a randomized tester accepts an input function f, given by the expected acceptance over its decision trees.

Statement

noncomputable def randomized_submod_tester_accept_prob {n k q : ℕ}
    (A : RandomizedSubmodTester n k q) (f : CubeFunc n k) : ℝ
Defined in
arXiv:2611.02374, Def. 2.5
Verified
06 Nov 2026
Axioms
none listed
Built on 3
  • CubeFuncThe type of functions from the n-dimensional Boolean hypercube {0, 1}^n into {0, 1, ..., k}, represented by Fin (k + 1).
  • RandomizedSubmodTesterA randomized tester making at most q queries, modeled as a finite probability distribution over deterministic decision trees of depth at…
  • submod_query_tree_evalEvaluates a query decision tree on a function f by querying coordinates along the tree path until reaching a leaf.

Read back from the Lean

Given natural numbers n, k, and q, a randomized tester A : RandomizedSubmodTester n k q, and a function f : CubeFunc n k, randomized_submod_tester_accept_prob A f is defined as the real number equal to the sum over all i : Fin A.m of A.prob i if submod_query_tree_eval (A.tree i) f is true, and 0 otherwise. In other words, it is the probability that the randomized tester A accepts f, computed as the sum of the probabilities of all deterministic query trees in A that accept f.

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

/-- Acceptance probability of a randomized tester on an input function. -/
noncomputable def randomized_submod_tester_accept_prob {n k q : ℕ}
    (A : RandomizedSubmodTester n k q) (f : CubeFunc n k) : ℝ := ∑ i, if submod_query_tree_eval (A.tree i) f then A.prob i else 0
See it in the graphDiscuss this resultChallenge it