A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension

DOI10.1137/1.9781611973402.101MaRDI QIDQ5384063zbMATH OpenOpenAlexFDO

Authors Esther Ezra

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973402.101

Mathematics Subject Classification ID

Combinatorial complexity of geometric structures (52C45) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
• On discrepancy bounds via dual shatter function
• Tight upper bounds for the discrepancy of half-spaces
• The determinant bound for discrepancy is almost tight
• Discrepancy and approximations for bounded VC-dimension

Cited in

(5)

• Discrepancy and approximations for bounded VC-dimension
• A simple proof of the shallow packing lemma
• scientific article; zbMATH DE number 1241856 (Why is no real title available?)
• On discrepancy bounds via dual shatter function
• A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension

This page was built for publication: A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384063)