Two proofs for shallow packings

DOI10.1007/s00454-016-9824-0zbMath1352.05047OpenAlexW2525451309WikidataQ113905014 ScholiaQ113905014MaRDI QIDQ728497

Esther Ezra, Kunal Dutta, Arijit Ghosh

Publication date: 20 December 2016

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5149/

zbMATH Keywords

packing lemmaClarkson-Shor propertyprimal shatter functionset systems of finite VC-dimensionshallow packing lemma

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Combinatorial aspects of packing and covering (05B40) Combinatorial complexity of geometric structures (52C45)

Related Items

Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning ⋮ When are epsilon-nets small?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple proof of the shallow packing lemma
• VC bounds on the cardinality of nearly orthogonal function classes
• Relative \((p,\varepsilon )\)-approximations in geometry
• Using the doubling dimension to analyze the generalization of learning algorithms
• \(\epsilon\)-nets and simplex range queries
• Reporting points in halfspaces
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Central limit theorems for empirical measures
• Predicting \(\{ 0,1\}\)-functions on randomly drawn points
• 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
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Constructive Discrepancy Minimization by Walking on the Edges
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Two Proofs for Shallow Packings
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension
• Convergence of stochastic processes
• Geometric discrepancy. An illustrated guide
• Improved bounds on the sample complexity of learning

This page was built for publication: Two proofs for shallow packings