On the VC-dimension and boolean functions with long runs

DOI10.1080/09720529.2007.10698116MaRDI QIDQ3637825zbMATH OpenOpenAlexFDO

Authors Joel Ratsaby

Publication date 14 July 2009

Published in Journal of Discrete Mathematical Sciences and Cryptography (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/09720529.2007.10698116

zbMATH Keywords

Boolean functionsPoisson approximationVapnik-Chervonenkis dimension

Mathematics Subject Classification ID

Boolean functions (06E30) Combinatorial probability (60C05)

Recommendations

• Density of smooth Boolean functions
• VC-dimensions of random function classes
• Exact VC-dimension of Boolean monomials
• Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions
• Constrained versions of Sauer's Lemma

Cites work

• -nets and simplex range queries
• A combinatorial problem; stability and order for models and theories in infinitary languages
• A generalization of Sauer's lemma
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Advanced Lectures on Machine Learning
• Compound Poisson approximation: A user's guide
• Convergence of stochastic processes
• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 1332320 (Why is no real title available?)
• Neural Network Learning
• On the density of families of sets
• On the density of sets of vectors
• On the trace of finite sets
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Scale-sensitive dimensions, uniform convergence, and learnability
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
• The Vapnik-Chervonenkis dimension of a random graph

Cited in

(9)

• Exact VC-dimension of Boolean monomials
• VC-dimensions of short Presburger formulas
• On the complexity of constrained VC-classes
• scientific article; zbMATH DE number 2127765 (Why is no real title available?)
• Density of smooth Boolean functions
• Edge domination in Boolean function graph \(\mathrm{B}(\overline{Kp}, \mathrm{L(G), NINC})\) of a graph
• VC-dimensions of random function classes
• VC‐dimension on manifolds: a first approach
• Complexity of Vapnik-Chervonenkis classes of sequences with long repetitive runs

This page was built for publication: On the VC-dimension and boolean functions with long runs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3637825)