On the complexity of constrained VC-classes

DOI10.1016/J.DAM.2007.05.041zbMATH Open1135.68025OpenAlexW2129072346MaRDI QIDQ2478433FDOQ2478433

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

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

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)

Cites Work

• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the density of families of sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A trinomial analogue of Bailey's lemma and \(N=2\) superconformal invariance
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
• Neural Network Learning
• On the trace of finite sets
• Complexity of hyperconcepts
• On the VC-dimension and boolean functions with long runs

Cited In (7)

• Title not available (Why is that?)
• VC bounds on the cardinality of nearly orthogonal function classes
• 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
• Title not available (Why is that?)

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)