Quantitative extraction of tight ladders from trees

How deep a sequential fat-shattering tree is needed to force an ε-tight uniform (k,δ)-ladder? The target extracts the ladder from a (t,2δ+ε)-tree for k≥1 and δ,ε>0.

Why it matters and what counts as progress

Why it matters: A better extraction bound improves a combinatorial tool in quantitative learning theory.

What counts as progress: A bound t≤(1/ε)^(O(k/ε²)) or better with a proved extraction argument, retaining the distinct tightness and tree-margin parameters.

How the problem developed

23 Jul 2026 · Quantitative result [1]
G. Conant and C. Terry Gave a new proof with improved bounds for extracting tight thresholds from trees of large sequential fat-shattering dimension, resolving an open problem tied to correcting a prior claimed result.

AI contribution

Encoding orders and trees in real-valued functions

G Conant, C Terry

For k≥1 and δ,ε>0, Theorem 1.14 extracts an ε-tight uniform (k,δ)-ladder from a (t,2δ+ε)-tree at some depth t≤(1/ε)^(O(k/ε²)), avoiding a multicolored Ramsey step.

AI involvementAI-centered

ImportanceNotable

Technical verificationFormal (human)

Human understandingFull