Discrepancy and approximations for bounded VC-dimension
From MaRDI portal
Publication:1316651
DOI10.1007/BF01303517zbMath0795.05105OpenAlexW2173468371WikidataQ54309514 ScholiaQ54309514MaRDI QIDQ1316651
Lorenz Wernisch, Ermo Welzl, Ji{ří} Matoušek
Publication date: 11 September 1994
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01303517
Hypergraphs (05C65) Permutations, words, matrices (05A05) Coloring of graphs and hypergraphs (05C15) Erd?s problems and related topics of discrete geometry (52C10) Discrete geometry (52C99)
Related Items (23)
Optimal approximations made easy ⋮ Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements ⋮ Typical rounding problems ⋮ An elementary approach to lower bounds in geometric discrepancy ⋮ Tight upper bounds for the discrepancy of half-spaces ⋮ Almost optimal set covers in finite VC-dimension ⋮ Approximation and learning of convex superpositions ⋮ The \(\varepsilon\)-\(t\)-net problem ⋮ Approximating majority depth ⋮ Vapnik-Chervonenkis density in some theories without the independence property. II ⋮ Quasi-Monte-Carlo methods and the dispersion of point sequences ⋮ Set-Codes with Small Intersections and Small Discrepancies ⋮ Relative \((p,\varepsilon )\)-approximations in geometry ⋮ Reprint of: Approximating majority depth ⋮ Sign rank versus Vapnik-Chervonenkis dimension ⋮ On discrepancy bounds via dual shatter function ⋮ A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension ⋮ A lower bound for families of Natarajan dimension \(d\) ⋮ Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique ⋮ Vapnik-Chervonenkis density in some theories without the independence property, I ⋮ The VC-dimension of axis-parallel boxes on the torus ⋮ Extending the centerpoint theorem to multiple points ⋮ Norm-graphs: Variations and applications
Cites Work
- Unnamed Item
- Unnamed Item
- \(\epsilon\)-nets and simplex range queries
- New applications of random sampling in computational geometry
- Quasi-optimal range searching in spaces of finite VC-dimension
- On the density of families of sets
- Geometric methods in the study of irregularities of distribution
- Some upper bounds in the theory of irregularities of distribution
- Learnability and the Vapnik-Chervonenkis dimension
- Quasi‐random 2‐ colorings of point sets
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
This page was built for publication: Discrepancy and approximations for bounded VC-dimension