Compression Schemes for VC Classes
A compression scheme of size k for the given class F (of indicators) consists of a compression function and a reconstruction function. For any sample σ labelled by some function f in the class, the compression function produces a subsample τ ⊆ σ of size at most k which then can be mapped by the reconstruction function to a hypothesis (not necessarily in the class) which agrees with the original function f on the original sample σ.