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

Please wait, while we are loading the content...

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

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Ezra, Esther
Copyright Year	2016
Abstract	Let $(X,\EuScript{S})$ be a set system on an $n$-point set $X$. The discrepancy of $\EuScript{S}$ is defined as the minimum of the largest deviation from an even split, over all subsets of $S \in \EuScript{S}$ and two-colorings $\chi$ on $X$. We consider the scenario where, for any subset $X' \subseteq X$ of size $m \le n$ and for any parameter $1 \le k \le m$, the number of restrictions of the sets of $\EuScript{S}$ to $X'$ of size at most $k$ is only $O(m^{d_1} k^{d-d_1})$ for fixed integers $d > 0$ and $1 \le d_1 \le d$ (this generalizes the standard notion of bounded primal shatter dimension when $d_1 = d$). In this case we show that there exists a coloring $\chi$ with discrepancy bound $O^{}(\|S\|^{1/2 - d_1/(2d)} n^{(d_1 - 1)/(2d)})$, for each $S \in \EuScript{S}$, where $O^{}(\cdot)$ hides a polylogarithmic factor in $n$. This bound is tight up to a polylogarithmic factor [J. Matoušek, Discrete Comput. Geom., 13 (1995), pp. 593--601, Geometric Discrepancy, Algorithms Combin. 18, Springer-Verlag, Heidelberg, 1999], and the corresponding coloring $\chi$ can be computed in expected polynomial time using the very recent machinery of Lovett and Meka [Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012, pp. 61--67] for constructive discrepancy minimization. Our bound improves and generalizes the bounds obtained from the machinery of Har-Peled and Sharir [Discrete Comput. Geom, 45 (2011), pp. 462--496] (and the follow-up work in [M. Sharir and S. Zaban, Output-Sensitive Tools for Range Searching in Higher Dimensions, unpublished manuscript, 2011; available online from www.cs.tau.ac.il/thesis/thesis/zaban.pdf]) for points and halfspaces in $d$-space for $d \ge 3$. Last but not least, we show that our bound yields improved bounds for the size of relative $(\varepsilon, \delta)$-approximations for set systems of the above kind.
Sponsorship	National Science Foundation
Starting Page	84
Ending Page	101
Page Count	18
File Format	PDF
ISSN	00975397
DOI	10.1137/140977746
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	1
Volume Number	45
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2016-01-26
Access Restriction	Subscribed
Subject Keyword	$\delta$-packing set systems of bounded primal shatter dimension entropy Probability in computer science partial coloring geometric discrepancy relative approximations Combinatorial complexity of geometric structures General
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

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

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

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

Two Proofs for Shallow Packings

On the discrepancy for cartesian products.

Geometric set systems (1998).

Output-Sensitive Construction of the Union of Triangles

Dimension in Complexity Classes

Dimension in complexity classes (2000)

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

Similar Documents

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

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

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

Two Proofs for Shallow Packings

On the discrepancy for cartesian products.

Geometric set systems (1998).

Output-Sensitive Construction of the Union of Triangles

Dimension in Complexity Classes

Dimension in complexity classes (2000)

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