tag:blogger.com,1999:blog-6555947.post4059733631539307562..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: Trolled from the arXiv... volume estimation...Suresh Venkatasubramaniannoreply@blogger.comBlogger7125tag:blogger.com,1999:blog-6555947.post-71016073768204800332009-03-31T02:43:00.000-06:002009-03-31T02:43:00.000-06:00Benoit:I think that one of the keys is that you ca...Benoit:<BR/><BR/>I think that one of the keys is that you can't distinguish between a uniform dist over a convex shape and a spherical dist using only poly many points. <BR/><BR/>What you mention about concentration of mass may have something to do with that.John Moellerhttp://ontopo.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-39878936823692525322009-03-30T23:56:00.000-06:002009-03-30T23:56:00.000-06:00I'm having trouble comparing this to the usual con...I'm having trouble comparing this to the usual concentration results, which show that all the mass is near the surface.<BR/><BR/>Of course, this is all in asymptotic dimensions. In d=2 or d=3, this is easy, right?Benoithttp://www.blogger.com/profile/04713089900964656656noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-69458060553714565132009-03-23T15:06:00.000-06:002009-03-23T15:06:00.000-06:00@Suresh:My confusion was whether or not you meant ...@Suresh:<BR/><BR/>My confusion was whether or not you meant that the vertices have real or rational coordinates.<BR/><BR/>For rational coordinates checking whether $x \in conv(V)$ or not just amounts to checking that the LP $x=V^T*\Lambda, \Lambda >= 0, \Sigma \lambda_i = 1$ is feasible or not.<BR/><BR/>If the entries of V are real then we don't know how to check the feasibility efficiently but for rational V it does not matter that you don't know the halfspaces (and you don't need to compute them). It is just a matter of checking feasibility of a rational LP.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-28526540263717825572009-03-23T10:17:00.000-06:002009-03-23T10:17:00.000-06:00that's what I did mean: you're given the vertices,...that's what I did mean: you're given the vertices, rather than the inequalities defining the halfspaces.Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-5438611869080366442009-03-23T07:11:00.000-06:002009-03-23T07:11:00.000-06:00On the other hand, I can imagine a membership orac...<I>On the other hand, I can imagine a membership oracle being hard if the object is described by its vertices only. Computing the convex hull is expensive.</I><BR/><BR/>Complexity of computing the convex hull is not really relevant here since you can check membership in this case by solving an LP.<BR/><BR/>Of course you could say that the vertex coordinates are given by real numbers and so solving an LP is not an option. I don't know if you meant it that way. In this case one could still "almost" sample points from this polytope by using a slight perturbation. (the new polytope has almost the same volume and almost the same interior available for sampling but the membership answers for some points differ for the two polytopes.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-5962478347881493392009-03-21T22:24:00.000-06:002009-03-21T22:24:00.000-06:00I'm not sure I can answer that. I think the point ...I'm not sure I can answer that. I think the point of the result was that you can't just sample from the convex body if you want an efficient estimator: it's not that it's cheaper but limited. <BR/><BR/>On the other hand, I can imagine a membership oracle being hard if the object is described by its vertices only. Computing the convex hull is expensive.Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-50296473238192991992009-03-21T22:19:00.000-06:002009-03-21T22:19:00.000-06:00Can you give an example of a convex body for which...Can you give an example of a convex body for which an efficient random point oracle exists but not efficient membership oracle? Do such objects ever come up naturally?Arvind Narayananhttp://www.blogger.com/profile/02495762505427759752noreply@blogger.com