abstract
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 the following applications:
1. dense max-cut: a las vegas algorithm that given a γ-dense g = (v, e) that has a
cut containing 1 − ε fraction of the edges, finds a cut that contains 1 − o(ε) fraction of
2
2
2
the edges. the algorithm runs in time õ(|v | (1/ε)o(1/γ +1/ε ) ) and has error probability
2
exponentially small in |v | . it also implies a deterministic non-uniform algorithm with
the same run-time (note that the input size is θ(|v |2 )).
2. approximate clique: a las vegas algorithm that given a graph g = (v, e) that
contains a clique on ρ |v | vertices, and given ε > 0, finds a set on ρ |v | vertices of density
3 2
2
at least 1 − ε. the algorithm runs in time õ(|v | 2o(1/(ρ ε )) ) and has error probability
exponentially small in |v |. we also show a deterministic non-uniform algorithm with the
same run-time.
3. free games: a las vegas algorithm and a non-uniform deterministic algorithm that
given a free game (constraint satisfaction problem on a dense bipartite graph) with value
at least 1 − ε0 and given ε > 0, find a labeling of value at least 1 − ε0 − ε. the error
probability of the randomized algorithm is exponentially small in the number of vertices
and labels. the run-time of the algorithms is similar to that of algorithms with constant
error probability.
4. from list decoding to unique decoding for reed-muller code: a randomized
algorithm with error probability exponentially small in the input size that given a word f
and 0 < ǫ, ρ < 1 finds a short list such that every low degree polynomial that is ρ-close
to f is (1 − ǫ)-close to one of the words in the list. the algorithm runs in nearly linear
time in the input size, and implies a deterministic non-uniform algorithm with similar runtime. the run-time of our algorithms compares with that of the most efficient algebraic
algorithms, but our algorithms are combinatorial and much simpler.