submod_query_tree_eval
def
Evaluates a query decision tree on a function f by querying coordinates along the tree path until reaching a leaf.
Statement
def submod_query_tree_eval {n k d : ℕ} (T : SubmodQueryTree n k d) (f : CubeFunc n k) : Bool- Defined in
- arXiv:2611.02374, Def. 2.5
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Built on 2
- CubeFuncThe type of functions from the n-dimensional Boolean hypercube {0, 1}^n into {0, 1, ..., k}, represented by Fin (k + 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
The function submod_query_tree_eval evaluates a query tree T : SubmodQueryTree n k d on an input function f : (Fin n → Bool) → Fin (k + 1), returning a Bool. It is defined by recursion on the tree T:
- If T is a leaf node leaf b, it returns the boolean label b.
- If T is a query node query x next, it evaluates f at the hypercube point x : Fin n → Bool to obtain an index f x : Fin (k + 1), and then recursively evaluates the child tree next (f x) on 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
/-- Evaluate a query decision tree on a function from the hypercube. -/ def submod_query_tree_eval {n k d : ℕ} (T : SubmodQueryTree n k d) (f : CubeFunc n k) : Bool := match T with | .leaf b => b | .query x next => submod_query_tree_eval (next (f x)) f