A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension
From MaRDI portal
Publication:5743609
DOI10.1137/140977746zbMath1334.68097arXiv1307.8139OpenAlexW2570456698MaRDI QIDQ5743609
Publication date: 5 February 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1307.8139
entropygeometric discrepancyrelative approximationspartial coloringset systems of bounded primal shatter dimension\(\delta\)-packing
Analysis of algorithms and problem complexity (68Q25) Combinatorial complexity of geometric structures (52C45)
Related Items (2)
Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning ⋮ Two proofs for shallow packings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Relative \((p,\varepsilon )\)-approximations in geometry
- \(\epsilon\)-nets and simplex range queries
- Irregularities of distribution. I
- ``Integer-making theorems
- Roth's estimate of the discrepancy of integer sequences is nearly sharp
- Decision theoretic generalizations of the PAC model for neural net and other learning applications
- Central limit theorems for empirical measures
- An \(L_p\) version of the Beck-Fiala conjecture
- Discrepancy and approximations for bounded VC-dimension
- Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
- Applications of random sampling in computational geometry. II
- Quasi-optimal range searching in spaces of finite VC-dimension
- Tight upper bounds for the discrepancy of half-spaces
- Geometric methods in the study of irregularities of distribution
- Constructive Discrepancy Minimization by Walking on the Edges
- On Approximating the Depth and Related Problems
- Six Standard Deviations Suffice
- Discrepancy in arithmetic progressions
- Two Proofs for Shallow Packings
- A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension
- Approximate Halfspace Range Counting
- Optimal private halfspace counting via discrepancy
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- On approximate range counting and depth
- Geometric discrepancy. An illustrated guide
- Improved bounds on the sample complexity of learning
This page was built for publication: A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension