tag:blogger.com,1999:blog-3722233.post8130761782776347154..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: How free is Randomness?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-85234876203520476752014-04-08T20:18:18.623-05:002014-04-08T20:18:18.623-05:00Mark Manasse, Frank McSherry and I were working at...Mark Manasse, Frank McSherry and I were working at some point on weighted consistent sampling (weighted version of minhashing) and found our implementation using a weak (C random, iirc) prng to be extremely inaccurate, leading us to question the correctness of our theorems. Fortunately for us, it was the prng's fault, and replacing it with something like SHA, while very likely overkill, did the trick. The algorithm we were implementing is in this paper:http://research.microsoft.com/apps/mobile/Publication.aspx?id=132309<br />--KunalAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2238197541312021362014-04-08T09:48:00.704-05:002014-04-08T09:48:00.704-05:00In my experience, a small amount of care with gene...In my experience, a small amount of care with generating random bits seems to suffice for randomized algorithms in practice. That said, there are some reported cases of Monte-Carlo simulations giving quite different results under different random-number generators \cite{flw}; it has also been noted that direct implementations of certain RNC algorithms for list ranking and graph connectivity \cite{hsu:thesis,hrd} sometimes take longer time than expected.<br /><br />\bibitem{flw}<br />A.~M. Ferrenberg, D.~P. Landau, and Y.~J. Wong.<br />\newblock Monte {C}arlo simulations: {H}idden errors from "good" random number<br /> generators.<br />\newblock {\em Physical {R}eview {L}etters}, 69(23):3382--3384, 1992.<br /><br />\bibitem{hsu:thesis}<br />T.{-s}. Hsu.<br />\newblock {\em Graph augmentation and related problems: theory and practice}.<br />\newblock PhD thesis, Department of {C}omputer {S}ciences, {U}niversity of<br /> {T}exas at {A}ustin, October 1993.<br /><br />\bibitem{hrd}<br />T.{-s}. Hsu, V.~Ramachandran, and N.~Dean.<br />\newblock Parallel implementation of algorithms for finding connected<br /> components.<br />\newblock In {\em {DIMACS} {I}nternational {A}lgorithm {I}mplementation<br /> {C}hallenge}, pages 1--14, 1994.<br />aravindhttp://www.cs.umd.edu/~srinnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82752573539286223062014-04-07T23:19:00.523-05:002014-04-07T23:19:00.523-05:00I was wondering about a problem lately about rando...I was wondering about a problem lately about randomness and I am not sure if the answer to this is already known (or obvious). Let say we have a black box that can return a random number, say in the range [0,1]. If somehow it is possible for us to open the box and see how it works (the algorithm maybe) , does the box loses its "random" nature? I mean if we find out how some object X works, does that reduces the state of X being random? Is randomness equiv to being unknown?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3451631839609963372014-04-07T09:16:17.183-05:002014-04-07T09:16:17.183-05:00Sure - PRNGs are used all the time in monte carlo ...Sure - PRNGs are used all the time in monte carlo simulations of physical (and increasingly, social) systems. There are many examples of situations where, by bad luck, problems with the PRNG happened to correlate with something of interest in the modelled system, and the results being incorrect calculations. Sometimes this is due to a researcher writing their own bad random number generator, but sometimes it has occurred using generators that were thought to be perfectly fine. Most famously, in the early '90s, a relatively respectable random number generator, r250 was used in calculations of the Wolff cluster algorithm of a 2-d Ising spin system, giving results (as energy-per-spin at the critical temperature) which were 42 standard deviations off from the expected value - http://arxiv.org/pdf/cond-mat/9512135.pdf.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70135982629692584152014-04-07T08:59:20.895-05:002014-04-07T08:59:20.895-05:00I thought he was only allowed to win $50k due to l...I thought he was only allowed to win $50k due to limits in place at the time :)<br /><br />Also, this wasn't a RNG. It was known to the system creators that there were a fixed number of patterns and a fixed set of values for each spot.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68336111872670773992014-04-07T08:38:55.141-05:002014-04-07T08:38:55.141-05:00A bad RNG once cost a gameshow $110k:
http://www....A bad RNG once cost a gameshow $110k:<br /><br />http://www.thisamericanlife.org/radio-archives/episode/412/million-dollar-idea?act=4#playAndrewhttp://polylogblog.wordpress.comnoreply@blogger.com