Expand description
DEEP-ALI out-of-domain sampling error.
ε_DEEP = L⁺ · factor / |F|, with k = trace domain size and
factor = max(max_deg · (k + max_combo − 1) + (k − 1), (c + 1) · k + max_combo − 1).
The first term is ethSTARK’s X^i · h_i(X^d) quotient split, matching
soundcalc/circuits/deep_ali.py. The second is Plonky3’s own quotient split into
c committed power-of-two chunks, which the first term only
dominates when c ≤ max_deg. soundcalc divides by |F| − k − D; the difference is
negligible.
The caller supplies the exact chunk count. For degree d and z = is_zk, this is
c = 2^z · next_power_of_two(max(d + z, 2) − 1), including both ZK adjustments.
The list size L⁺ enters linearly here, following soundcalc.
[2024/1553] Theorem 2 (eps_2) instead uses L² ≈ (m/ρ)², which is
a few bits more conservative in the list-decoding regime; ALI/DEEP
don’t bind at the LDR optimum in practice (see fri::best_ldr_m), so
the difference does not currently affect reported bounds.
Functions§
- deep_
ali_ error -log2(ε_DEEP)in bits. Returns 0 bits if inputs are degenerate or the trace size cannot be represented byu64.