tag:blogger.com,1999:blog-6555947.post6725612357216163999..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: Geometry @ BarriersSuresh Venkatasubramaniannoreply@blogger.comBlogger1125tag:blogger.com,1999:blog-6555947.post-71476869277132236682010-09-03T02:08:14.857-06:002010-09-03T02:08:14.857-06:00Sariel's question about short certificates was...Sariel's question about short certificates was intriguing and puzzling also.<br /><br />epsilon-samples, epsilon-nets, and coresets are not certificates in the usual sense. They are small subsets of the input set that are guaranteed to yield nearly tight lower bounds on some set functions. Since they are certificates for monotone functions on sets, they prove lower bounds on the true answers, but that is true of ANY (small) set. However they are not true certificates because they contain no inherent information that "proves" their near-optimality (and often that is only with high probability). Such a proof is external to the sets and it isn't necessarily small at all; indeed, it is unlikely to be so.<br /><br />However, there is something interesting going on - I am just not sure that "certificate" is the right way to think about things.Anonymousnoreply@blogger.com