k-Fold unions of low-dimensional concept classes
We show that 2 is the minimum VC dimension of a concept class whose k-fold union has VC dimension Omega(k log k). (C) 2009 Elsevier B.V. All rights reserved.
concept class vc dimension combinatorial problems union of concepts intersection of concepts