Density of smooth Boolean functions
Joel Ratsaby · Applicable Analysis and Discrete Mathematics · 2007
The Sauer-Shelah lemma has been instrumental in the analysis of algorithms in many areas including learning theory, combinatorial geometry, graph theory. Algorithms over discrete structures, for instance, sets of Boolean functions often involve a search over a constrained subset which satisfies some properties. In this paper we study the complexity of classes of functions h of finite VC-dimension which satisfy a local "smoothness" property expressed as having long repeated values around elements of a given sample. A tight upper bound is obtained on the density of such classes. It is shown to possess a sharp threshold with respect to the smoothness parameter.