# Amplification and Derandomization Without Slowdown

arXiv: https://arxiv.org/abs/1509.08123 · HTML: https://mlsanity.com/paper/1509.08123/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Sep 2015.

## Built on by (most cited first, 1 of 1)

- [Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits](https://mlsanity.com/paper/2306.01995/) (2023)

## Abstract (arXiv)

We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (non-uniform) algorithms. Unlike most existing techniques that involve repetition of the randomized algorithm and hence a slowdown, our techniques produce algorithms with a similar run-time to the original randomized algorithms. The amplification technique is related to a certain stochastic multi-armed bandit problem. The derandomization technique - which is the main contribution of this work - points to an intriguing connection between derandomization and sketching/sparsification. We demonstrate the techniques by showing applications to Max-Cut on dense graphs, approximate clique on graphs that contain a large clique, constraint satisfaction problems on dense bipartite graphs and the list decoding to unique decoding problem for the Reed-Muller code.