VC Dimension and Distribution-Free Sample-Based Testing
  We consider the problem of determining which classes of functions can be
tested more efficiently than they can be learned, in the distribution-free
sample-based model that corresponds to the standard PAC learning setting. Our
main result shows that while VC dimension by itself does not always provide
tight bounds on the number of samples required to test a class of functions in
this model, it can be combined with a closely-related variant that we call
"lower VC" (or LVC) dimension to obtain strong lower bounds on this sample
complexity.
  We use this result to obtain strong and in many cases nearly optimal lower
bounds on the sample complexity for testing unions of intervals, halfspaces,
intersections of halfspaces, polynomial threshold functions, and decision
trees. Conversely, we show that two natural classes of functions, juntas and
monotone functions, can be tested with a number of samples that is polynomially
smaller than the number of samples required for PAC learning.
  Finally, we also use the connection between VC dimension and property testing
to establish new lower bounds for testing radius clusterability and testing
feasibility of linear constraint systems.
