tag:blogger.com,1999:blog-6555947.post114141078348695896..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: AdversariesSuresh Venkatasubramanianhttps://plus.google.com/112165457714968997350noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-6555947.post-1141424101066624652006-03-03T15:15:00.000-07:002006-03-03T15:15:00.000-07:00It is certainly plausible that Nature is computati...It is certainly plausible that Nature is computationally bounded. Indeed if BQP is contained in NP, then this is even more believable. What's interesting though is that most useful distributions (the so-called exponential family) are characterized by exponential tails, and therefore efficient sampling is always possible. <BR/><BR/>On the other hand, certain natural processes generate polynomial tails, which make efficient estimation a lot harder. What do we do then ? <BR/><BR/> <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>SureshSureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1141419651258737292006-03-03T14:00:00.000-07:002006-03-03T14:00:00.000-07:00Thank you for your careful reading and your commen...Thank you for your careful reading and your comments! <BR/><BR/>Thanks also for bringing up the point that we can empirically determine distributions that might be appropriate for assumptions. What's interesting is that when we do an empirical investigation to find out what distribution is appropriate for modelling a problem, should we require that the distribution have a probabilistic polynomial time algorithm for sampling? My impression is that this is not a common requirement, or at least, not made explicit. <BR/><BR/>Put another way, in principle, Gauss could have come up with a distribution that is "hard" to sample from, yet explained the data. He didn't. Why? <BR/><BR/>One response is to postulate that Nature itself is constrained by efficiency requirements. I first saw this formulated explicitly in the "Optimal Error Correction Against Computationally Bounded Noise" paper by Micali, Peikert, Sudan, and Wilson<BR/>http://theory.csail.mit.edu/~cpeikert/pubs/mpsw.pdf<BR/><BR/>To me this is an attractive assumption, but I wonder how it looks to, say, a physicist. <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>David MolnarDavid Molnarnoreply@blogger.com