Amplification and Derandomization without Slowdown

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 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 algorithms for approximating free games (constraint satisfaction problems on dense bipartite graphs).

Authors

• Ofer Grossman
• Dana Moshkovitz

Keywords

• Algorithm design and analysis
• Error probability
• Approximation algorithms
• Generators
• Partitioning algorithms
• Games
• Computer science
• Deterministic
• Constraint Satisfaction Problem
• Multi-armed Bandit
• Bandit Problem
• Linear Time
• Input Size
• Head And Tail
• Algorithm For Problem
• Problem Of Bias
• Random Choice
• Algorithm Works
• Constant Probability
• Random Bits
• Fewer Inputs
• Fraction Of Edges
• Theoretical Computer Science
• Linear-time Algorithm
• Amplification; derandomization; Free game;