22 events
when toggle format what by license comment
Oct 11 '10 at 19:19 history edited Robin Kothari
added a tag
Oct 8 '10 at 16:10 history rollback M.S. Dousti
Rollback to Revision 7
Oct 8 '10 at 16:10 history edited M.S. Dousti CC BY-SA 2.5
deleted 1 characters in body
Oct 3 '10 at 18:46 answer Warren Schudy timeline score: 3
Oct 3 '10 at 7:05 history edited M.S. Dousti CC BY-SA 2.5
deleted 21 characters in body
Oct 2 '10 at 21:57 history edited M.S. Dousti CC BY-SA 2.5
added 104 characters in body; edited tags
Oct 2 '10 at 21:52 history edited M.S. Dousti CC BY-SA 2.5
added 265 characters in body
Oct 2 '10 at 19:50 comment added Sylvain Peyronnet @sadeq : I meant pick uniformly at random X inputs, and use a Chernov bound, but as Robin says, it does not satisfy the constraint on the precision. There is a paper of Karp, Luby and Madras (Monte-Carlo algorithms for enumeration problem) with a sampler that is adaptive (by analysis of the variance), maybe it works for the precision but I guess it violates the constraint on the running time.
Oct 2 '10 at 19:34 history edited M.S. Dousti CC BY-SA 2.5
deleted 46 characters in body
Oct 2 '10 at 19:10 comment added Robin Kothari @Sylvain: How many samples do you take before you stop? If you take a fixed number of samples, you'll get an estimate that will not satisfy the precision condition.
Oct 2 '10 at 18:59 comment added M.S. Dousti @Sylvain: Could you please describe more, or provide a link? (P.S: I know what Chernoff bound is.)
Oct 2 '10 at 17:57 comment added Sylvain Peyronnet I think I don't clearly understand the question. Why a naive sampler with a chernoff bound is not a good estimator ?
Oct 2 '10 at 17:04 comment added Tsuyoshi Ito Just a wild guess: Fix some polynomial p(n). Keep choosing an n-bit string uniformly at random with replacement and summing the value of f at the chosen point until the sum becomes at least p(n). Let T be the number of the tries made, and output p(n)/T. I do not have a provable bound on the expected running time or the precision, but this might work.
Oct 2 '10 at 16:56 answer Robin Kothari timeline score: 15
Oct 2 '10 at 16:49 comment added M.S. Dousti @Tsuyoshi: Yes, the estimator is randomized. I edited the question to reflect the meaning of such conditions.
Oct 2 '10 at 16:48 history edited M.S. Dousti CC BY-SA 2.5
added 437 characters in body
Oct 2 '10 at 16:40 comment added Tsuyoshi Ito Also, I guess that the estimator is randomized (just because it looks impossible otherwise). Is this the case? Also, if it is, what do the running-time condition and the precision condition exactly require?
Oct 2 '10 at 16:36 comment added M.S. Dousti @Tsuyoshi & Robin: Sorry fellas, I missed one condition in the precision. Check it out now!
Oct 2 '10 at 16:35 history edited M.S. Dousti CC BY-SA 2.5
added 66 characters in body
Oct 2 '10 at 16:35 comment added Robin Kothari It seems that p(n)=q(n)=O(1) and the trivial algorithm $E^f(1^n)$ that outputs "1" should work. It's running time is O(1), which is bounded by $\frac{p(n)}{\mathbb{E}[f(n)]}$. And it's precision is <=1, which is less than q(n).
Oct 2 '10 at 16:32 comment added Tsuyoshi Ito I cannot understand the precision condition. What prevents the algorithm E from always outputting 1? Did you mean 1/q(n) < (True value)/(Estimated value) < q(n)?
Oct 2 '10 at 16:20 history asked M.S. Dousti CC BY-SA 2.5