A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension

DOI10.1137/140977746zbMath1334.68097arXiv1307.8139OpenAlexW2570456698MaRDI QIDQ5743609

Esther Ezra

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

zbMATH Keywords

entropygeometric discrepancyrelative approximationspartial coloringset systems of bounded primal shatter dimension\(\delta\)-packing

Mathematics Subject Classification ID

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