Assouad's dual VC bound. If VCDim X C ≤ d, then VCDim(dualClass C) ≤ 2^(d+1) − 1.
DeclvcDim_dualClass_le
∀ {X : Type u} {C : ConceptClass X Bool} {d : ℕ}, VCDim X C ≤ ↑d → VCDim (↑C) (dualClass C) ≤ ↑(2 ^ (d + 1) - 1)TopicVC dimension
Arguments
| DOI | Author | Date |
|---|---|---|
| MTH.R-2026-6031 | Dhruv Gupta | 2026-09-24T00:00:00Z |
DOIMTH.C-2026-6031
Cite
Verification
- Library
- FLT_Proofs.Complexity.IndependentVC.DualBound
- Statement digest
- b05b78b9ee4b
- First verified
- 2026-09-24T00:00:00Z