Name
Abstract | ||
|---|---|---|
We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (nonuniform) algorithms. Unlike most existing techniques that involve repetition of the randomized algorithm and hence a slowdown, our techniques produce algorithms with similar run-time to the original randomized algorithms. The amplification technique applies when there is a quick, probabilistic test of the randomness. In this case, we show how to efficiently find one randomness string for the algorithm that works with very high probability and apply the algorithm only on that randomness (in contrast, standard approaches suggest a number of possible randomness strings and run the algorithm on all of them). The search of good randomness turns out to be a natural stochastic multiarmed bandit problem, which we define ("the biased coin problem") and analyze. The derandomization technique applies when there is a verifier that can test the randomness of the algorithm while only inspecting a sublinear size sketch of the input (the sketch may be hard to compute; the verifier may be inefficient and is allowed to reject a small portion of the good randomness strings). In this case, we show how to apply Adleman's derandomization (from the proof of BPP subset of P/poly) more efficiently. We demonstrate the techniques by showing applications for dense max-cut, approximate clique, free games, and going from list decoding to unique decoding for Reed-Muller codes. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1137/17M1110596 | SIAM JOURNAL ON COMPUTING |
Keywords | DocType | Volume |
derandomization,amplification,sketching | Journal | 49 |
Issue | ISSN | Citations |
5 | 0097-5397 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ofer Grossman | 1 | 10 | 4.70 |
| Dana Moshkovitz | 2 | 368 | 19.14 |