On the VC-dimension and boolean functions with long runs

References

• Alon , N. 1983 . On the density of sets of vectors . Discrete Math. , 46 : 199 – 202 .
   Google Scholar
• Alon , N. , Ben-David , S. , Cesa-Bianchi , N. and Haussler , D. 1997 . Scale-sensitive dimensions, uniform convergence and learnability . J. ACM , 44 ( 4 ) : 616 – 631 .
   Google Scholar
• Anthony , M. and Bartlett , P. L. 1999 . Neural Network Learning—Theoretical Foundations , Cambridge University Press .
   Google Scholar
• Anthony , M. , Brightwell , G. and Cooper , C. 1995 . The Vapnik-Chervonenkis Dimension of a Random Graph 616 – 631 .
   Google Scholar
• Arratia , R. , Goldstein , L. and Gordon , L. 1990 . Poisson approximation and the chen-stein method . Statistical Science , 5 : 403 – 434 .
   Google Scholar
• Barbour , A. D. and Chryssaphinou , O. 2001 . Compound poisson approximation: a user’s guide . The Annals of Applied Probability , 11 ( 3 ) : 964 – 1002 .
   Google Scholar
• Bollobás , B. 1986 . Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability , Cambridge University Press .
   Google Scholar
• Boucheron , S. , Bousquet , O. and Lugosi , G. 2004 . Introduction to Statistical Learning Theory , Edited by: Bousquet , O. , Luxburg , U. V. and Rsch , G. 169 – 207 . Springer . ???
   Google Scholar
• Chernoff , H. 1952 . A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations . Ann. Math. Stat. , 23 : 493 – 507 .
   Google Scholar
• Frankl , P. 1983 . On the trace of finite sets . Journal of Combinatorial Theory (A) , 34 : 41 – 45 .
   Google Scholar
• Frankl , P. 1987 . “ The shifting technique in extremal set theory ” . In Surveys in combinatorics , Edited by: Whitehead , C. 81 – 110 . Cambridge University Press . in
   Google Scholar
• Haussler , D. 1995 . Sphere packing numbers for subsets of the boolean n-cube with bounded Vapnik-Chervonenkis dimension . Journal of Combinatorial Theory, Series A , 69 : 217 – 232 .
   Web of Science ®Google Scholar
• Haussler , D. and Long , P. M. 1995 . A generalization of Sauer’s lemma . Journal of Combinatorial Theory (A) , 71 ( 2 ) : 219 – 240 .
   Google Scholar
• Haussler , D. and Welzl , E. 1987 . Epsilon-nets and simplex range queries . Discrete Computational Geometry , 2 : 127 – 151 .
   Google Scholar
• Pach , J. and Agarwal , P. K. 1995 . Combinatorial Geometry , Wiley-Interscience Series
   Google Scholar
• Pollard , D. 1984 . Convergence of Stochastic Processes , Springer-Verlag .
   Google Scholar
• Ratsaby , J. June 2006 . “ Complexity of contrained VC-classes ” . In Discrete Applied Mathematics June , accepted
   Google Scholar
• Sauer , N. 1972 . On the density of families of sets . J. Combinatorial Theory (A) , 13 : 145 – 147 .
   Google Scholar
• Shelah , S. 1972 . A combinatorial problem; stability and order for models and theories in infinitary languages . Pacific Journal of Mathematics , 41 : 247 – 261 .
   Google Scholar
• Vapnik , V. 1998 . Statistical Learning Theory , Wiley .
   Google Scholar
• Vapnik , V. N. and Chervonenkis , A. Y. 1971 . On the uniform convergence of relative frequencies of events to their probabilities . Theory Probab. Apl , 16 : 264 – 280 .
   Web of Science ®Google Scholar