Timeline for Chernoff bounds and Monte Carlo algorithms
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 25, 2013 at 23:12 | comment | added | Louis | This use of Chernoff bounds is more of an example of a general approach than a specific result. Try to formalize your specific setup and see! | |
| Nov 25, 2013 at 20:03 | comment | added | zpavlinovic | Great, much clearer! I guess when $A$ is not a decision problem, yet, for example yes/no/maybe, things get more complicated. | |
| Nov 25, 2013 at 19:56 | vote | accept | zpavlinovic | ||
| Nov 25, 2013 at 19:22 | history | edited | Louis | CC BY-SA 3.0 |
Edited to have more detail.
|
| Nov 25, 2013 at 18:34 | comment | added | zpavlinovic | Yes, I am unsure how to use them. For example, imagine that I want to make sure the error probability is at most $\epsilon$. How would I go about it? Basically, this example would guide me through on how to use and appreciate Chernoff bounds. | |
| Nov 25, 2013 at 18:30 | comment | added | Louis | Are you unsure about how to use Chernoff bounds at all, or what a Monte Carlo algorithm is? The question is a little fuzzy about what the problem is. | |
| Nov 25, 2013 at 15:59 | comment | added | zpavlinovic | It would help if you could add the part with Chernoff bounds, i.e., how to use it here. Moreover, does it matter whether $A$ is a decision problem or it can return more values? | |
| Nov 25, 2013 at 15:13 | history | edited | Juho | CC BY-SA 3.0 |
added 2 characters in body
|
| Nov 25, 2013 at 15:11 | history | answered | Louis | CC BY-SA 3.0 |