tag:blogger.com,1999:blog-6555947.post3618723215296796704..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: Bob Morris and stream algorithmsSuresh Venkatasubramaniannoreply@blogger.comBlogger5125tag:blogger.com,1999:blog-6555947.post-62705205108220211342011-07-09T12:38:48.136-06:002011-07-09T12:38:48.136-06:00@Suresh: I think Martin is asking about the sum of...@Suresh: I think Martin is asking about the sum of positive and negative integers, rather than F1, which is more complicated.<br /><br />Does the obvious modification of the Morris counter still work? I feel like it should.Sashohttp://www.blogger.com/profile/09380390882603977159noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-69805266691832184412011-07-03T01:09:36.796-06:002011-07-03T01:09:36.796-06:00@Martin: there are general versions of F_1 estimat...@Martin: there are general versions of F_1 estimation that allow for increments and decrements: they aren't as elegant as this one though. <br /><br />@williampan: if I understand correctly, the log (1/eps) term relates to the space needed to generate the random coin toss from a "pure" source of randomness. There's a standard approach to doing space-efficient randomness generation due to Nisan and Wigderson that's often invoked "in theory" as a way of generating bits in small space.Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-29939952752234818032011-07-02T10:09:56.176-06:002011-07-02T10:09:56.176-06:00Nice simple algorithm. I just wonder how much spa...Nice simple algorithm. I just wonder how much space is needed to generate the random "coin" with head-probability $2^{-C}$?williampanhttp://www.blogger.com/profile/07817226646563706930noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-50829512768027725802011-07-01T04:56:59.579-06:002011-07-01T04:56:59.579-06:00This is a great algorithm! Is there also a variant...This is a great algorithm! Is there also a variant that would allow both, incrementing and <i>decrementing</i>, the counter?Martin Schwarzhttp://www.blogger.com/profile/16935124381866975661noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-26815118206534460652011-06-30T21:08:14.561-06:002011-06-30T21:08:14.561-06:00Lovely description of an approach to a problem
I h...Lovely description of an approach to a problem<br />I hadn't heard of before. Thanks, Suresh!Bryanhttp://www.blogger.com/profile/08736009689892219149noreply@blogger.com