tag:blogger.com,1999:blog-6555947.post1722497836080213126..comments2023-09-10T07:21:33.251-06:00Comments on The Geomblog: Sample Complexity for eps-approximations of Range SpacesSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-6555947.post-47221651546789755122011-02-04T00:48:37.613-07:002011-02-04T00:48:37.613-07:00There is a more straightforward proof for eps-appr...There is a more straightforward proof for eps-approximation and also eps-nets using discrepency.<br />The proof to get a $O((1/\varepsilon^2)(d \log(1/\varepsilon)$ eps-approximation<br />is given in Matousek's Geometric Discrepency Book (Ch 5.2, Lemma 5.13).<br /><br />The idea is to iteratively halve the set $P$ by random 2-coloring (sampling). The random 2-coloring is shown to have a discrepency bound of $\sqrt (n \log m)$. Using this, it is shown that you get an eps-approximation when the sample is of the required size.<br /><br />I find the discrepency proof more direct as compared to the original<br />VC'71 paper which seems to need the non-intuitive tricks.<br /><br />Sathish GovindarajanAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-48712357437183449252011-02-03T05:13:59.926-07:002011-02-03T05:13:59.926-07:00Nice post, Jeff and Suresh. Please fix the typo in...Nice post, Jeff and Suresh. Please fix the typo in my last name when you refer to one of my papers.<br /><br />Aravind Srinivasanaravindhttp://www.cs.umd.edu/~srinnoreply@blogger.com