On the complexity of constrained VC-classes

DOI10.1016/J.DAM.2007.05.041MaRDI QIDQ2478433zbMATH OpenOpenAlexFDO

Authors Joel Ratsaby

Publication date 28 March 2008

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2007.05.041

zbMATH Keywords

integer partitionsBoolean functionsVC-dimensionSauer's lemma

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of partitions of integers (05A17) Boolean functions (06E30)

Recommendations

• scientific article; zbMATH DE number 2127765
• Constrained versions of Sauer's Lemma
• VC-dimensions of random function classes
• Some new maximum VC classes
• A generalization of Sauer's lemma

Cites work

• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 4029608 (Why is no real title available?)
• scientific article; zbMATH DE number 1332320 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• A trinomial analogue of Bailey's lemma and \(N=2\) superconformal invariance
• Complexity of hyperconcepts
• Neural Network Learning
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the VC-dimension and boolean functions with long runs
• On the density of families of sets
• On the trace of finite sets
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension

Cited in

(7)

• VC bounds on the cardinality of nearly orthogonal function classes
• scientific article; zbMATH DE number 1453031 (Why is no real title available?)
• VC-dimensions of short Presburger formulas
• On the complexity of binary samples
• Some new maximum VC classes
• \(L_{p}\)-norm Sauer-Shelah lemma for margin multi-category classifiers
• scientific article; zbMATH DE number 2127765 (Why is no real title available?)

This page was built for publication: On the complexity of constrained VC-classes

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