Timeline for Deamortizing a Las-Vegas randomized algorithm
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 7, 2015 at 18:17 | comment | added | Yuval Filmus | That's covered by my answer: you hope that the algorithm terminates in $n$ steps, and if not, you wait in the last step for the algorithm (or one of its copies) to finish. | |
| Dec 7, 2015 at 15:32 | comment | added | R B | Thanks Yuval, that answers the first part of my question. Assume that I want the algorithm to succeed with probability 1 (and the number of operations we perform at each time can vary), do you know how we can select the number of operations so that it'll be low (preferably constant) with high probability? Is this even possible? | |
| Dec 7, 2015 at 14:38 | history | answered | Yuval Filmus | CC BY-SA 3.0 |