Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-158 | 27th September 2015 20:37

Amplification and Derandomization Without Slowdown


Authors: Ofer Grossman, Dana Moshkovitz
Publication: 28th September 2015 01:00
Downloads: 1678


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.

ISSN 1433-8092 | Imprint