Amplification and Derandomization Without Slowdown
Ofer Grossman∗

Dana Moshkovitz†

arXiv:1509.08123v1 [] 27 Sep 2015

September 29, 2015

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.

∗

ogrossma@mit.edu. Department of Mathematics, MIT.
dmoshkov@csail.mit.edu. Department of Electrical Engineering and Computer Science, MIT. This material is
based upon work supported by the National Science Foundation under grants number 1218547 and 1452302.
†

1
1.1

Introduction
Amplification

Given a randomized algorithm that runs in time t and has error probability 1/3, can we find a
randomized algorithm that runs in similar time and has a substantially smaller error probability
e−Ω(k) ? One can achieve such a low error probability by repeating the algorithm k times. However,
the resulting algorithm is slower by a factor of k than the original algorithm, which is a significant
slowdown when k is large (for instance, consider k that equals the input size n, or equals nǫ for
some constant ǫ > 0). In this work we show that in many situations one can decrease the error
probability of the algorithm to e−Ω(k) without any substantial slowdown. These situations occur
when there is an additional randomized algorithm for evaluating the quality of the randomized
choices of the algorithm that is more efficient than the overall algorithm.
We show how to capitalize on the existence of such a testing algorithm using an algorithm for
a stochastic multi-armed bandit problem that we define. In this problem, which we call the biased
coin problem, there is a large pile of coins, and 2/3 fraction of the coins are biased, meaning that
they fall on heads with high probability. The coins are unmarked and the only way to discover
information about a coin is to toss it. The task is to find one biased coin with certainty 1 − e−Ω(k)
using as few coin tosses as possible. The analogy between the biased coin problem and amplification
is that the coins represent possible random choices of the algorithm, many of which are good. The
task is to find one choice that is good with very high probability. Tossing a coin corresponds to
testing the random choice of the algorithm.

1.2

Derandomization

What speed-up does randomization buy? Impagliazzo and Wigderson [22] showed that, under
plausible hardness assumptions, randomness can only speed up a polynomial-time computation by
a polynomial factor. Their deterministic algorithm, which invokes the randomized algorithm on
randomness strings generated by enumerating over all possible seeds of a pseudorandom generator,
slows down the run-time by at least a linear factor. To avoid the reliance on unproven assumptions,
researchers typically use properties of the concrete randomized algorithms they wish to derandomize
and design (or use off-the-shelf) pseudorandom generators for them (e.g., pairwise independent, εbiased sets, k-wise-independent and almost k-wise independent; see, e.g., [25, 29, 6]). Here too
derandomization slows down the run-time by at least a linear factor.
A different derandomization method by Adleman [2] uses amplification for derandomization and
does not rely on any unproven assumptions. It generates a non-uniform deterministic algorithm by
first decreasing the error probability of the randomized algorithm below 2−n where n is the input
size. Then, there must exist a randomness string that works for all 2n inputs, and this randomness
string can be hard-wired to a non-uniform algorithm. Due to the slowdown in amplification discussed in the previous sub-section, this technique too slows down the run-time by a linear factor
in n.
There is a general derandomization method that typically does not increase the run-time significantly, namely the method of conditional probabilities. It is used, for instance, for finding an
assignment that satisfies 7/8 fraction of the clauses in a 3Sat formula. However, this method works
only in very special cases. In this work we’ll be interested in derandomizing algorithms without
slowing down the run-time significantly, in cases where the method of conditional expectations does

1

not apply.
Our derandomization method builds on Adleman’s technique but avoids its slowdown, by using
a new connection to sketching and sparsification. Briefly, the connection is as follows: consider a
verifier that given an input and a randomness string for the randomized algorithm tests whether
the outcome of the randomized algorithm is correct. If the verifier can perform its test with only a
size-n′ sketch of the input (we call such a verifier an oblivious verifier), then Adleman’s union bound
′
can be performed over 2n representative inputs, rather than over 2n inputs. This means that it
′
suffices to amplify the error probability below 2−n . This saving, together with the amplification
technique discussed in the previous sub-section, allows us to derandomize without slowdown.

1.3

Context

The main existing approach to derandomization – the one based on pseudorandom generators –
focuses on shrinking the number of random strings. This is possible since the algorithm is limited
(by its run-time or by the simple way it uses the randomness) and cannot distinguish the set of all
randomness strings from a small subset of it (pseudorandom strings). In contrast, our approach
focuses on shrinking the number of inputs one needs to argue about. We show that it’s enough
that a randomness string leads to a correct output for all sketches.
Crucially, we do not argue that the algorithm doesn’t make use of its entire input, or that
inputs with the same sketch are indistinguishable, or that inputs with the same sketch are not
distinguished by the algorithm. The algorithms we consider depend on all of their input. Our
argument relies on the existence of a verifier aimed at certifying that randomness is good for an
input, and which doesn’t distinguish between inputs with the same sketch. Surprisingly, we are
able to devise sketches and design such oblivious verifiers for many natural algorithms.
The sketch that the oblivious verifier uses can be hard to compute, and it may reveal to the
verifier a correct output. The verifier need not (and generally will not be) efficient. The only
requirement is that the number of bits in the sketch is small and that the verifier is deterministic
(though the construction of the sketch can be probabilistic – we only need existence of a sketch).
Our applications include problems on dense graphs where sketching can be done using uniform
samples. We hope that the large body of work on sparsification and sketching (see, e.g., [23, 9, 35]
and the many works that followed them) could be used for more sophisticated applications of our
methods.

1.4

Non-Uniform Algorithms, Preprocessing and Amortization

Our derandomization produces non-uniform algorithms, i.e., algorithms that are designed with a
specific input size in mind. The knowledge of the input size is manifested by an “advice” string that
depends on the input size. The size of the advice counts toward the run-time of the algorithm (so,
for instance, advice that consists of the output for each possible input leads to an exponential-time
algorithm). Equivalently, non-uniform algorithms are described as sequences of circuits, one for
each input size. Sorting networks are an instance of non-uniform algorithms.
In some cases non-uniform algorithms imply uniform algorithms with the same asymptotic run
time. This is the case with Matrix-Multiplication and Minimum-Spanning-Tree [30]. More
generally, whenever a problem on inputs of size n can be reduced to the same problem on n/s
inputs of size s each for, say, s = log log log n, a non-uniform algorithm for the problem implies a
uniform algorithm. The uniform algorithm uses exhaustive search to find the advice for inputs of
2

size s (checking all possible advices, and for each, all possible inputs). It then uses the reduction
to find the sub-problems and the non-uniform algorithm to solve the sub-problems.
Even when a reduction of this sort does not exist, one can either designate the search for a good
advice as a preprocessing phase after which the algorithm is correct on all inputs, or amortize the
cost of searching for a good advice across inputs. If the space of possible advice strings contains
2a possibilities (where a can be as small as O(log n) if the space is the set of possible outputs of
a pseudorandom generator), and one can amortize the cost over 2a inputs, then one obtains the
desired run-time uniformly, amortized.

1.5

Applications

We demonstrate our techniques with applications for Max-Cut on dense graphs, (approximate)
Clique on graphs that contain large cliques, free games (constraint satisfaction problems on dense
bipartite graphs), and reducing the Reed-Muller list decoding problem to its unique decoding problem. All our algorithms run in nearly linear time in their input size, and all of them beat the
current state of the art algorithms in one aspect or another. The biggest improvement is in the
algorithm for free games that is more efficient by orders of magnitude than the best deterministic
algorithms. The algorithm for Max-Cut can efficiently handle sparser graphs than the best deterministic algorithm, the algorithm for (approximate) Clique can efficiently handle smaller cliques
than the best deterministic algorithm; and the algorithm for the Reed-Muller code achieves similar
run-time as sophisticated algebraic algorithms despite being much simpler. In general, our focus
is on demonstrating the utility and versatility of the techniques and not on obtaining the most
efficient algorithm for each problem. In the open problems section we point to several aspects
where we leave room for improvement.
1.5.1

Max Cut on Dense Graphs

Given a graph G = (V, E), a cut in the graph is defined by C ⊆ V . The value of the cut is
the fraction of edges e = (u, v) ∈ E such that u ∈ C and v ∈ V − C. We say that a graph
is γ-dense if it contains γ |V |2 /2 edges. For simplicity we assume that the graph is regular, so
every vertex has degree γ |V |. Given a regular γ-dense graph that has a cut of value at least
1 − ε for ε < 1/4, we’d like to find a cut of value roughly 1 − ε. Understanding this problem
on general (non-dense) graphs is an important open problem: (a weak version of) the Unique
Games Conjecture [24]. However, for dense graphs, it is possible to construct a cut of value
1 − ε − ζ efficiently [10, 7, 18, 28]. The best randomized algorithms are an algorithm of Mathieu
2 2
and Schudy [28] that runs in time O(|V |2 + 2O(1/γ ζ ) ) and an algorithm of Goldreich, Goldwasser
2
2
3 3
and Ron [18] that runs in time O(|V | (1/γζ)O(1/γ ζ ) + (1/γζ)O(1/γ ζ ) ) (Note that the algorithm
of [18] runs in sub-linear time. This is possible since it is an Atlantic City algorithm). Both
algorithms have constant error probability. We obtain a Las Vegas algorithm with exponentially
small error probability, and deduce a deterministic non-uniform algorithm. This is the simplest
application of our techniques. It uses the biased coin algorithm, but does not require any sketches.
Theorem 1.1. There is a Las Vegas algorithm that given a γ-dense graph G that has a cut of value
at least 1 − ε for ε < 1/4, and given ζ < 1/4 − ε, finds a cut of value at least 1 − ε − O(ζ), except
2
2
with probability exponentially small in |V |2 . The algorithm runs in time Õ(|V |2 (1/ζ)O(1/γ +1/ζ ) ).
It also implies a non-uniform deterministic algorithm with the same run-time.

3

Note that run-time Ω(γ |V |2 ) is necessary for a deterministic algorithm, since the input size
is γ |V |2 . A deterministic O(|V |2 poly(1/γζ) + 2poly(1/γζ) )-time algorithm follows from a recent
deterministic version of the Frieze-Kannan regularity lemma [34, 16, 12, 11, 5], however the poly(·)
term in the exponent hides large constant exponents. Therefore, our algorithm handles efficiently
graphs that are sparser than those handled efficiently by the existing deterministic algorithm.
1.5.2

Approximate Clique

The input is 0 < ε, ρ < 1 and an undirected graph G = (V, E) for which there exists a set C ⊆ V ,
|C| ≥ ρ |V |, that spans a clique. The goal is to find a set D ⊆ V , |D| ≥ ρ |V |, whose edge density
is at

|D|
least 1−ε, i.e., if E(D) ⊆ E is the set of edges whose endpoints are in D, then |E(D)| / 2 ≥ 1−ε.
3 2
Goldreich, Goldwasser and Ron [18] gave a randomized O(|V | (1/ε)O(1/(ρ ε )) ) time algorithm for
this problem with constant error probability (Note that this is a sub-linear time algorithm. This is
possible since it is an Atlantic City algorithm). A deterministic O(|V |2 poly(1/ρ, 1/ε)+2poly(1/ρ,1/ε) )
time algorithm with worse dependence on ρ and ε follows from a deterministic version of the FriezeKannan regularity lemma [34, 16, 12, 11, 5]. We obtain a randomized algorithm with exponentially
small error probability in |V |, and use sketching to obtain a non-uniform deterministic algorithm.
Our algorithms have better dependence in ρ and ε than the existing deterministic algorithm, and
can therefore handle efficiently graphs with smaller cliques than the existing deterministic algorithm
and output denser sets.
Theorem 1.2. The following hold:
1. There is a Las Vegas algorithm that given 0 < ρ, ε < 1, and a graph G = (V, E) with a clique
on ρ |V | vertices, finds a set of ρ |V | vertices and density at least 1 − ε, except with probability
3 2
exponentially small in |V |. The algorithm runs in time Õ(|V |2 2O(1/(ρ ε )) ).
2. There is a deterministic non-uniform algorithm that given 0 < ρ, ε < 1, and a graph G =
(V, E) with a clique on ρ |V | vertices, finds a set of ρ |V | vertices and density at least 1 − ε.
3 2
The algorithm runs in time Õ(|V |2 2O(1/(ρ ε )) ).
The sketch for approximate clique consists of all the edges that touch a small random set of
vertices. We show that such a sketch suffices to estimate the density of the sets considered by the
algorithm and the quality of the random samples of the algorithm.
1.5.3

Free Games

A free game G is defined by a complete bipartite graph G = (X, Y, X × Y ), a finite alphabet Σ and
constraints πe ⊆ Σ × Σ for all e ∈ X × Y . For simplicity we assume |X| = |Y |. A labeling to the
vertices is given by fX : X → Σ, fY : Y → Σ. The value achieved by fX , fY , denoted valfX ,fY (G),
is the fraction of edges that are satisfied by fX , fY , where an edge e = (x, y) ∈ X × Y is satisfied by
fX , fY if (fX (x), fY (y)) ∈ πe . The value of the instance, denoted val(G), is the maximum over all
labelings fX : X → Σ, fY : Y → Σ, of valfX ,fY (G). Given a game G with value val(G) ≥ 1 − ε, the
task is to find a labeling to the vertices gX : X → Σ, gY : Y → Σ, that satisfies at least 1 − O(ε)
fraction of the edges.
Free games have been researched in the context of one round two prover games (see [14] and
many subsequent works on parallel repetition of free games) and two prover AM [1]. They unify
a large family of problems on dense bipartite graphs obtained by considering different constraints.
4

For instance, for Max-2Sat we have Σ = {T, F }, and πe contains all (a, b) that satisfy α ∨ β where
α is either a or ¬a and β is either b or ¬b. Note that on a small fraction of the edges the constraints
can be “always satisfied”, so one can optimize over any dense graph, not just over the complete
graph (the density of the graph is crucial: if fewer than ε |X| |Y | of the edges have non-trivial
constraints, then any labeling satisfies 1 − ε fraction of the edges).
There are randomized algorithms for free games that have constant error probability [7, 4, 8, 1],
as well as a derandomization that incurs a polynomial slowdown [7]. In addition, deterministic
algorithms for free games of value 1 are known [27]. We show a randomized algorithm with exponentially small error probability in |X| |Σ| and a non-uniform deterministic algorithm whose
running time is similar to that of the randomized algorithms with constant error probability.
Theorem 1.3. The following hold:
1. There is a Las Vegas algorithm that given a free game G with vertex sets X, Y , alphabet Σ, and
val(G) ≥ 1 − ε0 , and given ε > 0, finds a labeling to the vertices that satisfies 1 − ε0 − O(ε)
fraction of the edges, except with probability exponentially small in |X| |Σ|. The algorithm
2
runs in time Õ(|X| |Y | |Σ|O((1/ε ) log(|Σ|/ε)) ).
2. There is a deterministic non-uniform algorithm that given a free game G with vertex sets X, Y ,
alphabet Σ, and val(G) ≥ 1 − ε0 , and given ε > 0, finds a labeling to the vertices that satisfies
2
1 − ε0 − O(ε) fraction of the edges. The algorithm runs in time Õ(|X| |Y | |Σ|O((1/ε ) log(|Σ|/ε)) ).
The sketch of a free game consists of the restriction of the game to a small random subset of Y .
We show that the sketch suffices to estimate the value of the labelings considered by the algorithm
and the random samples the algorithm makes.
1.5.4

From List Decoding to Unique Decoding of Reed-Muller Code

Definition 1.4 (Reed-Muller code). The Reed-Muller code defined by a finite field F and natural
numbers m and d consists of all m-variate polynomials of degree at most d over F.
Let 0 < ǫ < ρ < 1. In the list decoding to unique decoding problem for the Reed-Muller
code, the input is a function f : Fm → F and the goal is to output a list of l = O(1/ǫ) functions
g1 , . . . , gl : Fm → F, such that for every m-variate polynomial p of degree at most d over F that
agrees with f on at least ρ fraction of the points x ∈ Fm , there exists gi that agrees with p on at
least 1 − ǫ fraction of the points x ∈ Fm .
There are randomized, self-correction-based, algorithms for this problem (see [33] and the references there). There are also deterministic list decoding algorithms for the Reed-Solomon and
Reed-Muller codes that can solve this problem: The algorithms of Sudan [32] and GuruswamiSudan [20] run in large polynomial time, as they involve solving a system of linear equations and
factorization of polynomials. There are efficient implementations of these algorithms that run in
time Õ(|Fm |) (see [3] and the references there), but they involve deeper algebraic technique. Our
contribution is simple, combinatorial, algorithms, randomized and deterministic, with nearly-linear
run-time. This application too relies on the biased coin algorithm but does not require sketching.
Theorem 1.5. Let F be
a finite field, let d and
p m > 3 be natural numbers and let 0 < ρ, ǫ < 1, such
p
3
that d ≤ |F| /10, ǫ > 2/ |F| and ρ > ǫ + 2 d/ |F|. There is a randomized algorithm that given
f : Fm → F, finds a list of l = O(1/ρ) functions g1 , . . . , gl : Fm → F, such that for every m-variate
5

polynomial p of degree at most d over F that agrees with f on at least ρ fraction of the points x ∈ Fm ,
there exists gi that agrees with p on at least 1 − ǫ fraction of the points x ∈ Fm . The algorithm has
error probability exponentially small in |Fm | log |F| and it runs in time Õ(|Fm | poly(|F|)). It implies
a deterministic non-uniform algorithm with the same run-time.
Note that the standard choice of parameters for the Reed-Muller code has |F| = poly log |Fm |,
and in this case our algorithms run in nearly linear time Õ(|Fm |).

1.6

Previous Work

The biased coin problem introduced in Sub-section 1.1 is related to the stochastic multi-armed bandit problem studied in [13, 26], however, in the latter there might be only one biased coin, whereas
in our problem we are guaranteed that a constant fraction of the coins are biased. This makes a big
difference in the algorithms one would consider for each problem and in their performance. In the
setup considered by [13, 26] one has to toss all coins, and the algorithms focus on which coins to
eliminate. In our setup it is likely that we find a biased coin quickly, and the focus is on certifying
bias. In [13, 26] an Ω(k2 ) lower bound is proved for the number of coin tosses needed to find a
biased coin with probability 1 − e−Ω(k) , whereas we present an Õ(k) upper bound for the case of a
constant fraction of biased coins.
The connection that we make between derandomization and sketching adds to a long list of
connections that have been identified over the years between derandomization, compression, learning and circuit lower bounds, e.g., circuit lower bounds can be used for pseudorandom generators
and derandomization [22]; learning goes hand in hand with compression, and can be used to prove
circuit lower bounds [15]; simplification under random restrictions can be used to prove circuit
lower bounds [31] and construct pseudorandom generators [21]. Sparsification of the distinguisher
of a pseudorandom generator (e.g., for simple distinguishers like DNFs) can lead to more efficient
pseudorandom generators and derandomizations [19]. Our connection differs from all those connections. In particular, previous connections are based on pseudorandom generators, while our
approach is dual and focuses on shrinking the number of inputs.
The idea of saving in a union bound by only considering representatives is an old idea with
countless appearances in math and theoretical computer science, including derandomization (one
example comes from the notion of an ε-net and its many uses; another example is [19] we mentioned
above). Our contribution is in the formulation of an oblivious verifier and in designing sketches
and oblivious verifiers.
Our applications have Atlantic City algorithms that run in sub-linear time and have a constant error probability. There are works that aim to derandomize sub-linear time algorithms.
Most notably, as mentioned before, there is a deterministic version of the Frieze-Kannan regularity
lemma [34, 16, 12, 11, 5], which is relevant to some of our applications but not to others. Another
work is [36] that generates deterministic average case algorithms for decision problems with certain
sub-linear run time while incurring a slowdown.

6

2
2.1

Preliminaries
Conventions and Inequalities

Lemma 2.1 (Chernoff bounds). Let X1 , . . . , Xn be i.i.d random variables taking values in {0, 1}.
Let ε > 0. Then,
 X

 X

1
1
1X
1X
−2ε2 n
−2ε2 n
Pr
Xi ≥
E [Xi ] + ε ≤ e
, Pr
Xi ≤
.
E [Xi ] − ε ≤ e
n
n
n
n
The same inequalities hold for random variables taking values in [0, 1] (Hoeffding bound). The
multplicative version of the Chernoff bound states:

X

X
P
P
X
X
2
[Xi ]/3
−ε2
E
Xi ≤ (1 − ε) ·
Xi ≥ (1 + ε) ·
, Pr
Pr
E [Xi ] ≤ e−ε E [Xi ]/2 .
E [Xi ] ≤ e
When we say that a quantity is exponentially small in k we mean that it is of the form 2−Ω(k) .
We use exp(−n) to mean e−n .

2.2

Non-Uniform and Randomized Algorithms

Definition 2.2 (Non-uniform algorithm). A non-uniform algorithm that runs in time t(n) is given
by a sequence {Cn } of Boolean circuits, where for every n ≥ 1, the circuit Cn gets an input of size
n and satisfies |Cn | ≤ t(n).
Alternatively, a non-uniform algorithm that runs in time t(n) on input of size n is given an
advice string a = a(n) of size at most t(n) (note that a(n) depends on n but not on the input!).
The algorithm runs in time t(n) given the input and the advice.
The class of all languages that have non-uniform polynomial time algorithms is called P/ poly.
There are two main types of randomized algorithms: the strongest are Las Vegas algorithms
that may not return a correct output with small probability, but would report their failure. Atlantic
City algorithms simply return an incorrect output a small fraction of the time.
Definition 2.3 (Las Vegas algorithm). A Las Vegas algorithm that runs in time t(n) on input
of size n is a randomized algorithm that always runs in time at most t(n), but may, with a small
probability return ⊥. In any other case, the algorithm returns a correct output.
The probability that a Las Vegas algorithm returns ⊥ is called its error probability. In any
other case we say that the algorithm succeeds.
Definition 2.4 (Atlantic City algorithm). An Atlantic City algorithm that runs in time t(n) on
input of size n is a randomized algorithm that always runs in time at most t(n), but may, with a
small probability, return an incorrect output.
The probability that an Atlantic City algorithm returns an incorrect output is called its error
probability. In any other case we say that the algorithm succeeds.
Note that a Las Vegas algorithm is a special case of Atlantic City algorithms. Atlantic City
algorithms that solve decision problems return the same output the majority of the time. For search
problems we have the following notion:
Definition 2.5 (Pseudo-deterministic algorithm, [17]). A Pseudo-deterministic algorithm is an
Atlantic City algorithm that returns the same output except with a small probability, called its
error probability.
7

3

Derandomization by Oblivious Verification

In this section we develop a technique for converting randomized algorithms to deterministic nonuniform algorithms. The derandomization technique is based on the notion of “oblivious verifiers”,
which are verifiers that deterministically test the randomness of an algorithm while accessing only
a sketch (compressed version) of the input to the algorithm. If the verifier accepts, the algorithm
necessarily succeeds on the input and the randomness. In contrast, the verifier is allowed to reject
randomness strings on which the randomized algorithm works correctly, as long as it does not do
so for too many randomness strings.
Definition 3.1 (Oblivious verifier). Suppose that A is a randomized algorithm that on input
x ∈ {0, 1}N uses p(N ) random bits. Let s : N → N and ε : N → [0, 1]. An (s, ε)-oblivious verifier
for A is a deterministic procedure that gets as input N , a sketch x̂ ∈ {0, 1}s(N ) and r ∈ {0, 1}p(N ) ,
either accepts or rejects, and satisfies the following:
• Every x ∈ {0, 1}N has a sketch x̂ ∈ {0, 1}s(N ) .
• For every x ∈ {0, 1}N and its sketch x̂ ∈ {0, 1}s(N ) , for every r ∈ {0, 1}p(N ) , if the verifier
accepts on input x̂ and r, then A succeeds on x and r.
• For every x ∈ {0, 1}N and its sketch x̂ ∈ {0, 1}s(N ) , the probability over r ∈ {0, 1}p(N ) that
the verifier rejects is at most ε(N ).
Note that ε of the oblivious verifier may be somewhat larger than the error probability of the
algorithm A, but hopefully not much larger. We do not limit the run-time of the verifier, but
the verifier has to be deterministic. Indeed, the oblivious verifiers we design run in deterministic
exponential time. We do not limit the time for computing the sketch x̂ from the input x either.
Indeed, we use the probabilistic method in the design of our sketches. Crucially, the sketch depends
on the input x, but is independent of r.
Our derandomization theorem shows how to transform a randomized algorithm with an oblivious
verifier into a deterministic (non-uniform) algorithm whose run-time is not much larger than the
run-time of the randomized algorithm. Its idea is as follows. An oblivious verifier allows us to
partition the inputs so inputs with the same sketch are bundled together, and the number of inputs
effectively shrinks. This allows us to apply a union bound, just like in Adleman’s proof [2], but over
many fewer inputs, to argue that there must exist a randomness string for (a suitable repetition
of) the randomized algorithm that works for all inputs.
Theorem 3.2 (Derandomizing by verifying from a sketch). For every t ≥ 1, if a problem has a Las
Vegas algorithm that runs in time T and a corresponding (s, ε)-oblivious verifier for ε < 2−s/t , then
the problem has a non-uniform deterministic algorithm that runs in time T · t and always outputs
the correct answer.
Proof. Consider the randomized algorithm that runs the given randomized algorithm on its input
for t times independently, and succeeds if any of the runs succeeds. Its run-time is T · t. For any
input, the probability that the oblivious verifier rejects all of the t runs is less than (2−s/t )t = 2−s .
By a union bound over the 2s possible sketches, the probability that the oblivious verifier rejects
for any of the sketches is less than 2s · 2−s = 1. Hence, there exists a randomness string that the
oblivious verifier accepts no matter what the sketch is. On this randomness string the algorithm
8

has to be correct no matter what the input is. The deterministic non-uniform algorithm invokes
the repeated randomized algorithm on this randomness string.
Adleman’s theorem can be seen as a special case of Theorem 3.2, in which the sketch size is
the trivial s(N ) = N , the oblivious verifier runs the algorithm on the input and randomness and
accepts if the algorithm succeeds, and the randomized algorithm has error probability ε < 2−N/t .
The reason that we require that the algorithm is a Las Vegas algorithm in Theorem 3.2 is that
it allows us to repeat the algorithm and combine the answers from all invocations. Combining
is possible by other means as well. E.g., for randomized algorithms that solve decision problems
or for pseudo-deterministic algorithms (algorithms that typically return the same answer) one can
combine by taking majority. For algorithms that return a list, one can combine the lists.
The derandomization technique assumes that the error probability of the algorithm is sufficiently
low. To complement it, in Section 4 we develop an amplification technique to decrease the error
probability. Interestingly, our applications are such that the error probability can be decreased
without a substantial slowdown to a point at which our derandomization technique kicks in, but
we do not know how to decrease the error probability sufficiently for Adleman’s original proof to
work without slowing down the algorithm significantly.

4

Amplification by Finding a Biased Coin

In this section we develop a technique that will allow us to significantly decrease the error probability
of randomized algorithms without substantially slowing down the algorithms. The technique works
by testing the random choices made by the algorithm and quickly discarding undesirable choices. It
requires the ability to quickly estimate the desirability of random choices. The technique is based
on a solution to the following problem.
Definition 4.1 (Biased coin problem). Let 0 < η, ζ < 1. In the biased coin problem one has a
source of coins. Each coin has a bias, which is the probability that the coin falls on “heads”. The
bias of a coin is unknown, and one can only toss coins and observe the outcome. It is known that
at least 2/3 fraction1 of the coins have bias at least 1 − η. Given n ≥ 1, the task is to find a coin
of bias at least 1 − η − ζ with probability at least 1 − exp(−n) using as few coin tosses as possible.
A similar problem was studied in the setup of multi-armed bandit problems [13, 26], however in
that setup there might be only one coin with large bias, as opposed to a constant fraction of coins
as in our setup. In the former setup, many more coin tosses might be needed (an Ω(n2 /ζ 2 ) lower
bound is proved in [26]).
The analogy between the biased coin problem and amplification is as follows: a coin corresponds
to a random choice of the algorithm. Its bias corresponds to how desirable the random choice is.
The assumption is that a constant fraction of the random choices are very desirable. The task is to
find one desirable random choice with a very high probability. Tossing a coin corresponds to testing
the random choice. The coin falls on heads in proportion to the quality of the random choice.
Interestingly, if we knew that all coins have bias either at least 1 − η or at most 1 − η − ζ, it
would have been possible to solve the biased coin problem using only O(n/ζ 2 ) coin tosses. The
algorithm is described in Figure 1. It tosses a random coin a small number of times and expects
to witness about 1 − η fraction heads. If so, it doubles the number of tosses, and tries again, until
1

2/3 can be replaced with any constant larger than 0.

9

its confidence in the bias is sufficiently large. If the fraction of heads is too small, it restarts with
a new coin. The algorithm has two parameters i0 that determines the initial number of tosses and
if that determines the final number of tosses.
The probability that the algorithm restarts at the i’th phase is exponentially small in ζ 2 k for
k = 2i : either the coin had bias at least 1− η, and then there’s an exponentially small probability in
ζ 2 k that there were less than (1 − η − ζ/2)k heads, or the coin had bias at most 1 − η − ζ, and then
there is probability exponentially small in ζ 2 k that the coin had at least 1 − η − ζ/2 fraction heads
in all the previous phases (whereas if this is phase i = i0 , then the probability that a coin with bias
less than 1 − η was picked in this case is constant, i.e., exponentially small in ζ 2 k). Moreover, the
number of coin tosses up to this step is at most 2k. Hence, we maintain a linear relation (up to
ζ 2 factor) between the number of coin tosses and the exponent of the probability. To get the error
probability down to exp(−n) we only need O(n/ζ 2 ) coin tosses.
Find-Biased-Coin-Given-Gap(n, η, ζ)
1 Set i0 = log(1/ζ 2 ) + Θ(1); if = log(n/ζ 2 ) + Θ(1) (constants picked appropriately).
2 Pick a coin at random.
3 for i = i0 , i0 + 1, . . . , if
4
Toss the coin for k = 2i times.
5
If the fraction of heads is less than 1 − η − ζ/2, restart.
6 return coin.

Figure 1: An algorithm for finding a coin of bias at least 1 − η − ζ when all the coins either have
bias at least 1 − η or at most 1 − η − ζ. The algorithm uses O(n/ζ 2 ) coin tosses and achieves error
probability exp(−n).
Counter-intuitively, adding coins of bias between 1 − η − ζ and 1 − η – all acceptable outcomes
of the algorithm – derails the algorithm we outlined above, as well as other algorithms. If one fixes
a threshold like 1 − η − ζ/2 for the fraction of heads one expects to witness, there might be a coin
whose bias is around the threshold. We might toss this coin a lot and then decide to restart with a
new coin. One can also consider a competition-style algorithm like the ones studied in [13, 26] when
one tries several coins each time, keeping the ones that fall on heads most often. Such a algorithm
may require Ω(n2 /ζ 2 ) coin tosses, since coins can lose any short competition to coins with slightly
smaller bias; then, such coins can lose to coins with slightly smaller bias, and so on, until we may
end up with a coin of bias smaller than 1 − η − ζ.
There is, however, a algorithm that uses only Õ(n/ζ 2 ) coin tosses. This algorithm decreases the
threshold for the fraction of heads one expects to witness with respect to the number of coin tosses
one already made for this coin. If the coin was already tossed a lot, the deviation of the number of
heads from 1 − η would have to be large for us to decide to restart with a new coin. The algorithm
is described in Figure 2.
Note that the deviation parameter β is picked so 1 − η − iβ ≥ 1 − η − ζ for all i ≤ if .
Lemma 4.2. Within O((n/ζ 2 ) log2 (n/ζ)) = Õ(n/ζ 2 ) coin tosses, Find-Biased-Coin outputs a
coin of bias at least 1 − η − ζ except with probability exp(−n).
Proof. Suppose that the algorithm restarts at phase i. The number of coin tosses made by this
point since the previous restart (if any) is 2i0 +2i0 +1 +. . .+2i ≤ 2i+1 . Moreover, if the coin had bias
10

Find-Biased-Coin(n, η, ζ)
Set i0 = log(1/ζ 2 ) + Θ(1); if = log(n/ζ 2 ) + Θ(log log(n/ζ)); β = ζ/if .
Pick a coin at random.
for i = i0 , i0 + 1, . . . , if
Toss the coin for k = 2i times.
If the fraction of heads is less than 1 − η − iβ, restart.
return coin.

1
2
3
4
5
6

Figure 2: An algorithm for finding a coin of bias at least 1 − η − ζ using Õ(n/ζ 2 ) coin tosses. The
error probability is exponentially small in n.
smaller than 1 − η − iβ + β/2, then, if i > i0 , by a Chernoff bound, the probability the coin passed
the previous test, where it was supposed to have at least 1 − η − (i − 1)β fraction of heads, is at
most exp(−β 2 2i−2 ). If i = i0 , there is probability less than 1/3 that the coin was picked. If the coin
had bias at least 1 − η − iβ + β/2, then by the Chernoff bound, the probability it failed the current
test, where it is supposed to have at least 1 − η − iβ fraction of heads, is at most exp(−β 2 2i−1 ).
In any case, the ratio between the number of coin tosses and the exponent of the probability is
O(1/β 2 ). The value of if is chosen so that the error probability in the last iteration is exp(−n).
By the choice of β, the coin tosses to exponent ratio is O((1/ζ 2 ) log2 (n/ζ)). Therefore, the number
of coin tosses one needs in order to reach error probability exp(−n) is O((n/ζ 2 ) log2 (n/ζ)).

4.1

Extensions

In the sequel, we’ll use the biased coin algorithm in a more general setting, and in this section we
develop the appropriate machinery. In the general setting coins are divided into groups, and rather
than directly tossing coins we simulate tossing. The simulation may fail or may produce results
that are inconsistent with the true bias of the coin. Some of the coins may be faulty, and their
tossing may fail arbitrarily. For other coins, the probability that tossing fails is small. For any coin,
the probability that the coin toss does not fail and is inconsistent with the true bias is small. The
coins are partitioned into groups of size g each. The bias of a group is the maximum bias among
non-faulty coins in the group, and is 0 if all the coins in the group are faulty. At least 2/3 fraction
of the groups have bias at least 1 − η. The task is to find a group of coins of bias at least 1 − η − ζ.
The formal requirements from a simulated coin toss are as follows:
Definition 4.3. Simulated coin tosses satisfy the following:
• For any coin, when tossing the coin k times, there is exponentially small probability in β 2 k
for the following event: the tosses do not fail, yet the fraction of tosses that fall on heads
deviates from the true bias by more than an additive β/4 for β as in Figure 3.
• For non-faulty coins, the probability that tossing the coin fails is exponentially small in β 2 k.
Note that the simulation has to be very accurate, since the deviation β/4 is sub-constant. We
describe a modified biased coin algorithm in Figure 3.

11

Find-Biased-Coin-in-Group(n, g, η, ζ)
1
2
3
4
5
6
7

Set if = log((n + log g)/ζ 2 ) + Θ(log log((n + log g)/ζ)); β = ζ/if .
Set i0 = log(log g/β 2 ) + Θ(1), where the constant term is sufficiently large.
Pick a group of coins at random.
for i = i0 , i0 + 1, . . . , if
Simulate tossing each one of the g coins in the group for k = 2i times.
If the maximum fraction of heads per coin is less than 1 − η − iβ, restart.
return group of coins.

Figure 3: An algorithm for finding a group of coins of bias at least 1 − η − ζ, where the coins are
partitioned into groups of size g each. The error probability is exponentially small in n.
Lemma 4.4 (Generalized biased coin). If Find-Biased-Coin-in-Group restarts at a certain
phase, then either in this phase or in the previous, the reported fraction of heads deviates by more
than β/2 from the true bias for one of the non-faulty coins in the group, or it is the first phase and
a group of bias at most 1 − η − β/2 was picked.
As a result, within O((ng log g/ζ 2 ) log2 ((n + log g)/ζ)) = Õ(ng/ζ 2 ) coin tosses Find-BiasedCoin-in-Group outputs a coin of bias at least 1 − η − ζ except with probability exp(−n).
Proof. Suppose that the algorithm restarts at phase i. The number of coin tosses made by this
point is g · (2i0 + 2i0 +1 + . . . + 2i ) ≤ g · 2i+1 .
Suppose that the group had bias smaller than 1 − η − iβ + β/2. If i > i0 , the probability
that the coins passed the previous test, where at least one of them was supposed to have at least
1−η−(i−1)β fraction of heads, is g·(exp(−β 2 2i−4 )+exp(−Ω(β 2 2i−1 ))) (where β/4 of the deviation
and exp(−Ω(β 2 2i−1 )) of the error probability can be attributed to the simulation). Note that this
probability is exponentially small in β 2 2i when log g is sufficiently smaller than β 2 2i0 −1 (here we
use the choice of i0 ). If i = i0 , the probability that a group of bias smaller than 1 − η was picked
is less than 1/3.
On the other hand, if the group has bias at least 1 − η − iβ + β/2, then the probability it failed
the current test, where one of the coins is supposed to have at least 1 − η − iβ fraction of heads,
is at most exp(−β 2 2i−3 ) + exp(−Ω(β 2 2i )) (again, β/4 of the deviation and exp(−Ω(β 2 2i )) of the
error probability can be attributed to the simulation).
In any case, the ratio between the number of coin tosses and the exponent of the probability is O(g log g/β 2 ). The value of if is set so the error probability in the last iteration is
exp(−n). By the choice of β, the coin tosses to exponent ratio is O((g log g/ζ 2 ) log2 ((n + log g)/ζ)).
Therefore, the number of coin tosses one needs in order to reach error probability exp(−n) is
O((ng log g/ζ 2 ) log2 ((n + log g)/ζ)) = Õ(ng/ζ 2 ).

5

Max Cut on Dense Graphs

In this section we show the application to Max-Cut on dense graphs. This is our simplest example.
It relies on the biased coin algorithm, and does not require any sketches.

12

5.1

A Simple Randomized Algorithm

First we describe a simple randomized algorithm for dense Max-Cut based on the sampling idea
of Fernandez de la Vega [10] and Arora, Karger and Karpinski [7]. We remark that Mathieu
and Schudy [28] have similar, but more efficient, randomized algorithms, however, for the sake of
simplicity, we stick to the simplest algorithm with the easiest analysis.
The main idea of the algorithm is as follows. We sample a small S ⊆ V and enumerate over all
possible S-cuts H ⊆ S. Each S-cut induces a cut CS,H ⊆ V as follows.
Definition 5.1 (Induced cut). Let G = (V, E). Let S ⊆ V and H ⊆ S. We define CS,H ⊆ V as
follows: for every v ∈ V let v ∈ CS,H if the fraction of edges e = (v, s) ∈ E with s ∈ S − H is larger
than the fraction of edges e = (v, s) ∈ E with s ∈ H.
We will argue below that if there is a cut in G with value at least 1 − ε and H is the restriction
of that cut to S, then the induced cut is likely to approximately achieve the optimal value. Note
that we rely on density when we hope that the edges that touch the small set S span most of the
vertices in the graph.
Lemma 5.2 (Sampling). Let G = (V, E) be a regular γ-dense graph that has a cut of value at least
1 − ε for ε < 1/4. Then for ζ < 1/4 − ε and for a uniform S ⊆ V ,

|S| = max ⌈log(2/ζ 2 )/ζ 2 ⌉, ⌈2 log(2/ζ 2 )/γ 2 ⌉ ,

with probability at least 1 − ζ, there exists H ⊆ S such that the value of the cut CS,H is at least
1 − ε − 10ζ.

Proof. Let C ∗ be the optimal cut in G. Let H ⊆ S be the restriction of C ∗ to S. Denote by V ′ the
set of all v ∈ V such that at least 1/2 + ζ fraction of the edges that touch v contribute to the value
of C ∗ . Note that |V ′ | ≥ (1 − 4ζ) |V |. By γ-density and regularity, the degree of all vertices is γ |V |.
By a Chernoff bound, except with probability ζ 2 /2 over S, at least (γ/2) |S| of the vertices in S
are neighbors of v. The sample of v’s neighbors is uniform and hence by another Chernoff bound,
except with probability ζ 2 /2 over S, the vertex v is assigned by CS,H to the same side as C ∗ assigns
it. Therefore, except with probability ζ over the random choice of S, at least 1 − ζ fraction of the
vertices v ∈ V ′ are assigned by CS,H the same as C ∗ . This means that at least 1 − 5ζ fraction of
the vertices v ∈ V are assigned by CS,H the same as C ∗ . Therefore, the fraction of edges that: (i)
contribute to the value of C ∗ , and (ii) have both their endpoints assigned by CS,H the same as C ∗ ,
is at least 1 − ε − 2 · 5ζ = 1 − ε − 10ζ.

5.2

A Randomized Algorithm With Exponentially Small Error Probability

We describe an analogy between finding a cut of high value and finding a biased coin. We think
of sampling S ⊆ V as picking a group of coins, and picking H ⊆ S as picking a coin in the group.
The bias of the coin is the value of the cut CS,H . Therefore a biased coin directly corresponds to
a desirable cut. One tosses a coin by picking an edge (u, v) ∈ E uniformly at random, computing
whether u ∈ CS,H and whether v ∈ CS,H , and checking whether the edge contributes to the value
of the cut. Note that checking whether a vertex belongs to CS,H is computed in time |S|. The coin
toss algorithm is described in Figure 4. The algorithm based on finding a biased coin is described
in Figure 5.
13

Max-Cut-Toss-Coin(G = (V, E), S, H)
1 Pick e = (u, v) ∈ E uniformly at random.
2 return “heads” iff u ∈ CS,H and v ∈
/ CS,H or vice versa.

Figure 4: A coin toss picks an edge at random and checks whether it contributes to the value of
the cut CS,H .
Find-Cut(G = (V, E), ε, ζ)

1 Set s = max ⌈log(2/ζ 2 )/ζ 2 ⌉, ⌈2 log(2/ζ 2 )/γ 2 ⌉ , where γ is the density of G.
2 Set if = log((|V |2 + s)/ζ 2 ) + Θ(log log((|V | + s)/ζ)); β = ζ/if .
3 Set i0 = log(s/β 2 ) + Θ(1).
4 Sample S ⊆ V , |S| = s.
5 for i = i0 , i0 + 1, . . . , if
6
for all H ⊆ V
7
Invoke Max-Cut-Toss-Coin(G, S, H) for k = 2i times.
8
If the fraction of heads is less than 1 − ε − 10ζ − iβ for all H, restart.
9 return cut CS,H with value at least 1 − ε − 11ζ if exists.

Figure 5: An algorithm for finding a cut of value 1 − ε − O(ζ) in a regular γ-dense graph that has
a cut of value 1 − ε. The error probability of the algorithm is exponentially small in |V |2 .
This proves Theorem 1.1, which is repeated below for convenience. Note that for a sufficiently
small error probability exponentially small in |V |2 it follows that there exists a randomness string
on which the algorithm succeeds, no matter what the input is.
Theorem 5.3. There is a Las Vegas algorithm that given a γ-dense graph G that has a cut of value
at least 1 − ε for ε < 1/4, and given ζ < 1/4 − ε, finds a cut of value at least 1 − ε − O(ζ), except
2
2
with probability exponentially small in |V |2 . The algorithm runs in time Õ(|V |2 (1/ζ)O(1/γ +1/ζ ) ).
It also implies a non-uniform deterministic algorithm with the same run-time.

6
6.1

Approximate Clique
An Algorithm With Constant Error Probability

In this section we describe a randomized algorithm with constant error probability for finding an
approximate clique in a graph that has a large clique. The algorithm is a simplified version of an
algorithm and analysis by Goldreich, Goldwasser and Ron [18]. We rely on the algorithm and the
analysis when we design a randomized algorithm with error probability exp(−Ω(|V |)) and again
when we design a deterministic algorithm.
The main idea of the algorithm is as follows. We first find a small random subset U ′ of the
large clique C by sampling vertices U from V and enumerating over all possibilities for C ∩ U . The
intuition is that now we would like to find other vertices that are part of the large clique C. A
14

natural test for whether a vertex v ∈ V is in the clique is whether v is connected to all the vertices
in U ′ . This, however, is not a sound test, since the clique might have many vertices that neighbor
it but do not neighbor one another. A better test checks whether v neighbors all of U ′ , as well as
many of the vertices that neighbor all of U ′ . Vertices that neighbor all of U ′ are likely to neighbor
almost all of the clique.
The algorithm is described in Figure 6. It picks U ⊆ V at random, considers all possible
sub-cliques U ′ ⊆ U , |U ′ | ≥ (ρ/2) |U |, computes Γ(U ′ ) the set of vertices that neighbor all of U ′ ,
computes for every vertex in Γ(U ′ ) the fraction of vertices in Γ(U ′ ) that neighbor it, and considers
SU ′ the set of ρ |V | vertices in Γ(U ′ ) with largest fractions of neighbors. The algorithm outputs a
sufficiently dense set among all sets SU ′ , if such exists.
Find-Approximate-Clique-Constant-Error(G = (V, E), ρ, ε)
1 Sample U ⊆ V , |U | = ⌈k0 /ρ⌉, for k0 = 100/ε2 .
2 for all sub-cliques U ′ ⊆ U , |U ′ | ≥ (ρ/2) |U |,
3
Compute Γ(U ′ ) the set of vertices that neighbor all of U ′ .
4
For each v ∈ Γ(U ′ ) compute the fraction fv of vertices in Γ(U ′ ) that neighbor v.
5
Let SU ′ ⊆ Γ(U ′ ) contain the ρ |V | vertices with largest fv .
6 return set SU ′ of density at least 1 − 2ε/ρ if such exists.

Figure 6: Randomized algorithm with constant error probability for finding an approximate clique.
The algorithm runs in time exp(k0 /ρ) · O(|V |2 ). Next we analyze the probability it is correct.
By a Chernoff bound, we have |U ∩ C| ≥ (ρ− ε) |U |, except with probability 1/10. Pick a uniformly
random order on the vertices. Let us focus on the event |U ∩ C| ≥ (ρ − ε) |U | and U ′ that is the
first (ρ/2) |U | elements in U ∩ C according to the random order. Note that the elements of U ′ are
uniformly and independently distributed in C. Let Γ(U ′ ) ⊆ V contain all the vertices that neighbor
all of U ′ .
Lemma 6.1. With probability 1 − e−25/ε over the choice of U ′ , the fraction of v ∈ Γ(U ′ ) that
neighbor less than 1 − ε fraction of C is at most e−25/ε .
Proof. Consider v ∈ V that has less than 1 − ε neighbors in C. For v to be in Γ(U ′ ) the set U ′ must
miss all of the non-neighbors of v. Since U ′ is a uniform sample of C, this happens with probability
′
(1 − ε)|U | ≤ e−50/ε . The lemma follows.
Let us focus on U ′ for which the fraction of v ∈ Γ(U ′ ) that neighbor less than 1 − ε fraction
of C is at most e−25/ε . Lemma 6.1 guarantess that such a U ′ , which we call good, is picked with
constant probability. Next we show that an average vertex in C neighbors most of Γ(U ′ ).
Lemma 6.2 (Density for C). For good U ′ , the average number of neighbors a vertex c ∈ C has in
Γ(U ′ ) is at least (1 − 2ε) · |Γ(U ′ )|.
Proof. Since U ′ is good, more than 1 − e−25/ε fraction of Γ(U ′ ) neighbor at least 1 − ε fraction of C.
Hence, the average fraction of Γ(U ′ ) neighbors a uniform vertex in C has is at least 1 − 2ε (using
e−25/ε ≤ ε).
We can now prove the correctness of Find-Approximate-Clique-Constant-Error.
15

Lemma 6.3. With probability at least 1−e−25/ε , Find-Approximate-Clique-Constant-Error,
when invoked on 0 <Pρ, ε < 1, and a graph G = (V, E) with a clique on ρ |V | vertices, picks SU ′
such that (1/|SU ′ |) · v∈S ′ fv ≥ 1 − 2ε, and returns a set of density at least 1 − 2ε/ρ.
U
P
Proof. For good U ′ , by Lemma 6.2, (1/|C|) v∈C fv P
≥ 1 − 2ε. Since SU ′ takes the ρ |V | vertices
with largest fv and |C| ≥ ρ |V |, we have (1/|SU ′ |) · v∈S ′ fv ≥ 1 − 2ε. Therefore, the density
U
within SU ′ is at least 1 − 2ε/ρ, and so is the density of the set returned by the algorithm.
Next we show how to transform the randomized algorithm with constant error probability from
Section 6.1 into an algorithm with error probability that is exponentially small in |V | without
increasing the run-time by more than poly-logarithmic factors. The algorithm applies the biased
coin algorithm from Section 4.

6.2

Finding an Approximate Clique as Finding a Biased Coin

The analogy between finding a biased coin and finding an approximate clique is as follows: Picking
U picks a group of coins. There is a coin for every U ′ ⊆ U , |U ′ | ≥ (ρ/2) |U |. The coin is faulty if
|Γ(U ′ )| < ρ |V |. A coin corresponds to the set SU ′ of the ρ |V | vertices in Γ(U ′ ) with largest number
of neighbors in Γ(U ′ ) (when the coin is faulty, pad the set with dummy vertices with 0 neighbors).
The bias of the coin biasU ′ is the expectation, over the choice of a random vertex v ∈ SU ′ , of the
fraction of vertices in Γ(U ′ ) that neighbor v. With at least 2/3 probability, one of the coins in
the group – the one associated with a good U ′ in the sense of Section 6.1 – has biasU ′ ≥ 1 − 2ε.
Moreover, any U ′ with biasU ′ ≥ 1 − cε corresponds to a set of density at least 1 − cε/ρ.
Had we found the vertices in each SU ′ , we could have tossed a coin by picking a vertex at
random from SU ′ and a vertex at random from Γ(U ′ ) and letting the coin fall on heads if there
is an edge between the two vertices. Unfortunately, finding the vertices in SU ′ may take Ω(|V |2 )
time, so we refrain from doing that. We settle for a simulated toss – where with high probability
the coin falls on heads with probability close to its bias. In Section 4.1 we extended the biased
coin algorithm to simulated tosses. In Figure 7 we describe the algorithm for tossing a coin enough
times so the probability of γ-deviation from the true bias is exponentially small in k (the number
of coin tosses is implicit). The algorithm runs in time O(k |V | |U ′ | poly(1/ρ, 1/γ)).
Clique-Coin-Toss(G = (V, E), U ′ , ρ, k, γ)
1 Compute Γ(U ′ ).
2 if |Γ(U ′ )| < ρ |V |
3
Fail.
4 Sample V ′ ⊆ V , |V ′ | = ⌈k/(ργ 2 )⌉.
5 For all v ∈ V ′ compute the fraction fv of Γ(U ′ ) vertices that neighbor v.
6 Let SU ′ ,V ′ ⊆ V ′ ∩ Γ(U ′ ) contain the ρ |V ′ | vertices with largest fv .
P
′ .
7 return biasVU ′ = (1/ρ |V ′ |) v∈S ′ ′ fv heads.
U ,V

Figure 7: An algorithm for tossing the coin associated with U ′ , where the coin falls on heads with
probability Θ(γ)-close to its bias except with probability exponentially small in k.

16

′

In the next lemma we prove that biasVU ′ is likely to approximate biasU ′ well. For future use we
phrase a more general statement than we need here, addressing U ′ that defines a slightly faulty
coin as well.
Lemma 6.4. Assume that |Γ(U ′ )| ≥ (1 − γ ′ )ρ |V |, where γ ′ = Θ(γ) and γ, γ ′ ≤ 1/4. For a uniform
V ′ ⊆ V , except with probability exponentially small in ργ 2 |V ′ |,
′

biasVU ′ − biasU ′ ≤ 3γ + 2γ ′ .
Proof. By a multiplicative Chernoff bound, except with probability exponentially small in ργ 2 |V ′ |,
there are (1 ± γ ± γ ′ )ρ |V ′ | vertices in V ′ ∩ SU ′ . Let us focus on this event.
By a Hoeffding bound, except with probability exponentially small in ργ 2 |V ′ |, we have
1
|V ′ ∩ SU ′ |

1 X
fv ≤ γ.
|SU ′ |

X

fv −

fv −

1 X
fv ≤ 3γ + 2γ ′ .
|SU ′ |

v∈V ′ ∩SU ′

v∈SU ′

Hence,
1
ρ |V ′ |

X

v∈V ′ ∩SU ′

v∈SU ′

The lemma follows.
The algorithm for finding an approximate clique using Clique-Coin-Toss is described in
Figure 8. Note that the coin tossing algorithm satisfies the conditions of simulated tossing (Definition 4.3). Lemma 6.1 and Lemma 6.2 ensure that with constant probability over the choice of U ,
for U ′ as specified in Section 6.1, we have biasU ′ ≥ 1 − 2ε for one of the U ′ ⊆ U . Moreover, a coin
with bias at least 1− cε yields a set which is at least 1− cε/ρ-dense, and this set can be computed in
O(|V |2 ) time. Therefore, the algorithm in Figure 8 gives an algorithm for finding an approximate
2
clique that errs with probability exponentially small in |V | and runs in time Õ(|V |2 2O(1/ε ρ) ). This
proves part of Theorem 1.2 repeated below for convenience (note that ε in Theorem 1.2 is replaced
with O(ε/ρ) here).
Theorem 6.5. There is a Las Vegas algorithm that given a graph G = (V, E) with a clique on
ρ |V | vertices and given 0 < ρ, ε < 1, finds a set of ρ |V | vertices and density 1 − O(ε/ρ), except
2
with probability exponentially small in |V |. The algorithm runs in time Õ(|V |2 2O(1/(ε ρ)) ).
The remainder of the section constructs an oblivious verifier for Find-Approximate-Clique
and uses it to prove the second part of Theorem 1.2 (a deterministic algorithm). First we describe
the sketch and its properties, then we devise an oblivious verifier for Clique-Coin-Toss, and
finally we describe the verifier for Find-Approximate-Clique.

6.3

A Sketch for Approximate Clique

The sketch for a given G contains, for some carefully chosen set R of poly(log |V | , 1/ε, 1/ρ) vertices,
the bipartite graph GR = (R, V, ER ) that contains all the edges of G that at least one of their
endpoints falls in R. The set R is chosen so it allows the verifier to estimate the fv ’s corresponding
to different sets U ′ ⊆ V . Note that the size of the sketch is |R| |V |.
17

Find-Approximate-Clique(G = (V, E), ρ, ε)
1
2
3
4
5
6
7
8
9
10

Set u = ⌈100/(ε2 ρ)⌉.
Set if = log((|V | + u)/ε2 ) + Θ(log log((|V | + u)/ε)); β = ε/if .
Set i0 = log(u/β 2 ) + Θ(1).
Sample U ⊆ V , |U | = u.
for i = i0 , i0 + 1, . . . , if
Set k = 2i .
for all U ′ ⊆ U , |U ′ | ≥ (ρ/2) |U |
Clique-Coin-Toss(G, U ′ , ρ, β 2 k, γ = β/100). If fails, skip this U ′ .
If the fraction of heads is less than 1 − 2ε − iβ for all (non-skipped) U ′ , restart.
return set SU ′ of density at least 1 − 3ε/ρ if such exists.

Figure 8: An algorithm for finding an approximate clique in a graph G = (V, E) that contains a
clique on ρ |V | vertices. The error probability of the algorithm is exponentially small in |V |.
Let U ′ ⊆ U . For every v ∈ V we denote by fv the fraction of vertices in Γ(U ′ ) that neighbor v.
′
For V ′ ⊆ V , let SU ′ ,V ′ ⊆ V ′ ∩ Γ(U ′ ) denote the ρ |V ′ | elements v ∈ V ′ ∩ Γ(U
P) with largest fv (pad
′ .
′
V
with dummy vertices with 0 neighbors if needed). Let biasU ′ = (1/ρ |V |) v∈S ′ ′ fv . For v ∈ V
U ,V
let f˜v denote the fraction of Γ(U ′ ) ∩ R vertices that neighbor v among all vertices in Γ(U ′ ) ∩ R.
For V ′ ⊆ V , let S̃U ′ ,V ′ be the ρ |V ′ | vertices v ∈ V ′ with largest f˜v (pad with dummy vertices with
′
P
.
˜ V′ =
0 neighbors if needed). Let bias
(1/ρ |V ′ |) v∈S̃ ′ ′ f˜v .
U
U ,V
In the lemma we use u, ρ, γ from Find-Approximate-Clique in Figure 8.
Lemma 6.6 (Sketch). There exists R ⊆ V , |R| = O(u log |V | /ργ 2 ), such that for every U ′ ⊆ V ,
|U ′ | ≤ u,
1. If |Γ(U ′ )| ≥ ρ |V |, then |R ∩ Γ(U ′ )| ≥ (1 − γ)ρ |R|, whereas if |Γ(U ′ )| < (1 − 2γ)ρ |V |, then
|R ∩ Γ(U ′ )| < (1 − γ)ρ |R|.
2. Suppose that |Γ(U ′ )| ≥ (1 − 2γ)ρ |V |. Then, for every v ∈ V , we have f˜v − fv ≤ γ.
3. Suppose that |Γ(U ′ )| ≥ (1 − 2γ)ρ |V |. Then, biasR
U ′ − biasU ′ ≤ 7γ.
Proof. Pick R ⊆ V uniformly at random. Let U ′ ⊆ U , |U ′ | ≤ u. By a multiplicative Chernoff
bound, if |Γ(U ′ )| ≥ ρ |V |, then |R ∩ Γ(U ′ )| ≥ (1 − γ)ρ |R|, except with probability exponentially
small in ργ 2 |R|. If |Γ(U ′ )| < (1 − 2γ)ρ |V |, then |R ∩ Γ(U ′ )| ≤ (1 − γ)ρ |R| except with probability
exponentially small in ργ 2 |R|.
Suppose that |Γ(U ′ )| ≥ (1 − 2γ)ρ |V |. Let v ∈ V . By a multiplicative Chernoff bound, except
with probability exponentially small in ργ 2 |R|, we have |Γ(U ′ ) ∩ R| ≥ (1 − 3γ) |R|. By a Chernoff
bound, except with probability exponentially small in ργ 2 |R|, we have
f˜v − fv ≤ γ.
By a union bound over all v and by the choice of |R|, the last inequality holds for all v ∈ V except
with probability exponentially small in ργ 2 |R|.
18

By Lemma 6.4, if |Γ(U ′ )| ≥ (1− 2γ)ρ |V |, except with probability exponentially small in ργ 2 |R|,
we have
biasR
U ′ − biasU ′ ≤ 7γ.
Since there are less than |V |u choices for U ′ , it follows from a union bound that there exists R
for which all three items hold for all U ′ ⊆ V , |U ′ | ≤ u.
Lemma 6.7. Suppose that |Γ(U ′ )| ≥ (1 − 2γ)ρ |V |. For any V ′ ⊆ V ,
′

˜ V ′ − biasV ′′ ≤ 2γ.
bias
U
U
Proof. By Lemma 6.6, the contribution from v ∈ V ′ in S̃U ′ ,V ′ ∩SU ′ ,V ′ is at most γ since f˜v − fv ≤ γ.
It remains to bound the contribution from other elements v ∈ V ′ that are either in S̃U ′ ,V ′ − SU ′ ,V ′
or in SU ′ ,V ′ − S̃U ′ ,V ′ . Pair those vertices arbitrarily, and consider a single pair v2 ∈ S̃U ′ ,V ′ − SU ′ ,V ′
and v1 ∈ SU ′ ,V ′ − S̃U ′ ,V ′ . We know that fv1 ≥ fv2 ≥ f˜v2 − γ, so f˜v2 − fv1 ≤ γ. Similarly,
f˜v2 ≥ f˜v1 ≥ fv1 − γ, so fv1 − f˜v2 ≤ γ. In any case, fv1 − f˜v2 ≤ γ. The triangle inequality implies
the lemma.
Corollary 6.8. For every U ′ ⊆ V , |U ′ | ≤ u, either |R ∩ Γ(U ′ )| < (1 − 2γ)ρ |V |, or
˜ R′ − biasU ′ ≤ 9γ.
bias
U
Proof. If |R ∩ Γ(U ′ )| ≥ (1−2γ)ρ |V |, by Lemma 6.6, we have biasR
U ′ − biasU ′ ≤ 7γ. By Lemma 6.7,
R
˜ ′ − biasR′ ≤ 2γ. The claim follows.
bias
U

U

Interestingly, our construction of the sketch is randomized, yet it will allow us to obtain a
deterministic algorithm. The reason is that we only need the existence of a sketch describing an
input so we can take a union bound over all possible sketches.

6.4

Obliviously Checking V ′

Next we show how we can check the sample V ′ of Clique-Coin-Toss using the sketch. The
oblivious verifier receives a sketch GR of the graph G, the rest of the input of Clique-Coin-Toss
′
and the randomness V ′ used by the algorithm. The verifier accepts iff biasVU ′ is approximately
˜ R′ . It is described in Figure 9.
biasU ′ . It uses the sketch to approximate biasU ′ via bias
U

Recall that by Lemma 6.6, if the coin is non-faulty and |Γ(U ′ )| ≥ ρ |V |, then |R ∩ Γ(U ′ )| ≥
(1 − γ)ρ |R|, so Oblivious-Verifier-Clique-Coin-Toss does not fail in Step 2. Moreover, if
|Γ(U ′ )| < (1 − 2γ)ρ |V |, then |R ∩ Γ(U ′ )| < (1 − γ)ρ |R|, and Oblivious-Verifier-Clique-CoinToss necessarily fails.
Lemma 6.9. The following hold:
1. If Oblivious-Verifier-Clique-Coin-Toss accepts then |Γ(U ′ )| ≥ (1 − 2γ)ρ |V | and V ′
′
sampled by Clique-Coin-Toss satisfies biasVU ′ − biasU ′ ≤ 29γ.
2. If |R ∩ Γ(U ′ )| ≥ (1 − γ)ρ |V |, then the probability that Oblivious-Verifier-Clique-CoinToss rejects is exponentially small in k.
19

Oblivious-Verifier-Clique-Coin-Toss(GR , U ′ , ρ, k, γ, V ′ )
1 If |R ∩ Γ(U ′ )| < (1 − γ)ρ |R|
2
Fail.
3 For all v ∈ V ′ compute the fraction f˜v of vertices in Γ(U ′ ) ∩ R that neighbor v.
4 Let S̃U ′ ,V ′ be the ρ |V ′ | vertices v ∈ V ′ with largest f˜v .
′
P
.
˜ V′ =
5 Let bias
(1/ρ |V ′ |)
f˜v .
U

6 Accept iff

′
˜ V′
bias
U

−

v∈S̃U ′ ,V ′
R
˜ ′ ≤ 18γ.
bias
U

Figure 9: An oblivious verifier for Clique-Coin-Toss.
Proof. Toward the second item, suppose that |R ∩ Γ(U ′ )| ≥ (1 − γ)ρ |V |. By Lemma 6.7, we have
′
˜ R′ − biasU ′ ≤ 9γ. By Lemma 6.4, we have
˜ V ′ − biasV ′′ ≤ 2γ. By Corollary 6.8, we have bias
bias
U
U
U
′

biasVU ′ − biasU ′ ≤ 7γ, except with probability exponentially small in k. The low probability of
rejection follows.
Toward the first item, suppose that Oblivious-Verifier-Clique-Coin-Toss accepts, so
′
′
˜ V ′ − biasV ′′ ≤
˜ V ′ − bias
˜ R′ ≤ 18γ. By Lemma 6.7, we have bias
|R ∩ Γ(U ′ )| ≥ (1− γ)ρ |R| and bias
U
U
U
U
˜ R′ − biasU ′ ≤ 9γ. Thus, we have biasV ′′ − biasU ′ ≤ 29γ.
2γ. By Corollary 6.8, we have bias
U
U

6.5

An Oblivious Verifier for Approximate Clique

The verifier is unable to follow the execution of Find-Approximate-Clique nor compute its
output, since it can’t tell exactly how many heads Clique-Coin-Toss yields. The verifier can be
probably approximately correct about the fraction of heads, but it is likely that during the execution
of Find-Approximate-Clique some of its predictions would be false, thereby changing the course
of execution. It may seem that under these conditions the verifier cannot check the randomness of
the algorithm, but this is not so. The key idea is that the verifier is not limited computationally and
can try all possible executions of the algorithm (i.e., the outcomes of all possible restart decisions).
Remark 6.1. The algorithm Find-Approximate-Clique uses its randomness as a stream of
random bits, and uses independent randomness between restarts. The oblivious verifier for a single
execution simulates a possible run of the algorithm and follows the algorithm in its use of the
randomness. Different executions use the same randomness.
The verifier maintains a set G of possible input graphs G that are consistent with the execution
up to this step (initially G contains all the input graphs that are consistent with the sketch). If the
set of inputs becomes empty, then the execution is designated infeasible. Otherwise the execution
is designated feasible. Additionally, the verifier maintains counter such that the probability of the
execution is at most exponentially small in counter (initially, counter = 0). If counter becomes too
large, the verifier rejects the execution. If none of the feasible executions get rejected, the verifier
accepts. The verifier for a single execution (a single fixing of guesses) is described in Figure 10.

20

Note that we use the shorthand OVCCT for Oblivious-Verifier-Clique-Coin-Toss and that
the verifier uses the parameters i0 , if , β of the algorithm. The final verifier is described in Figure 11.
Oblivious-Verifier-Clique-Execution(G, GR = (R, V, ER ), ρ, ε, r, counter)
1 if G = φ
2
return infeasible.
3 if counter > |V |
4
return reject.
5 Extract from r the sample U ⊆ V of the algorithm.
˜ R′ < 1 − 2ε − β/2 + 9γ for all U ′ such that |R ∩ Γ(U ′ )| ≥ (1 − γ)ρ |V |
6 if bias
U

7
8
9
10
11
12
13
14
15
16
17
18

counter ← counter + 25/ε.
for i = i0 , i0 + 1, . . . , if
Set k = 2i .
for all U ′ ⊆ U , |U ′ | ≥ (ρ/2) |U |
Extract from r the randomness V ′ for Clique-Coin-Toss.
OVCCT(GR , U ′ , ρ, β 2 k, γ = β/100, V ′ )
if ∃U ′ , |R ∩ Γ(U ′ )| ≥ (1 − γ)ρ |V | such that OVCCT rejects
2
counter ←
n counter + β k − u. o
′

Guess if max biasVU ′ |Γ(U ′ )| ≥ ρ |V | < 1 − 2ε − iβ and update G accordingly.

if guessed true
Restart maintaining G and counter.

˜ R′ ≥ 1 − 3ε − 9γ.
return accept iff ∃U ′ ⊆ U , |R ∩ Γ(U ′ )| ≥ (1 − γ)ρ |V |, such that bias
U

Figure 10: An oblivious verifier for a single execution of Find-Approximate-Clique (an execution is defined by the outcomes of guesses). We use the shorthand OVCCT for ObliviousVerifier-Clique-Coin-Toss.

Oblivious-Verifier-Approximate-Clique(GR = (R, V, ER ), ρ, ε, r)
1 Let G contain all the graphs that are consistent with GR .
2 Try all guesses in Oblivious-Verifier-Clique-Execution(G, GR , ρ, ε, r, 0).
3 Accept iff all feasible executions accept.

Figure 11: The final oblivious verifier for approximate clique.
Next we analyze Oblivious-Verifier-Approximate-Clique.
Lemma 6.10. If Oblivious-Verifier-Approximate-Clique accepts on a sketch of a graph G
and randomness r, then Find-Approximate-Clique2 necessarily finds U ′ ⊆ V with biasU ′ ≥
1 − 3ε − 18γ when invoked on G and r with the same parameters ρ and ε.
2

Note that we argue about a version of Find-Approximate-Clique that checks a relaxed condition on the density
such that the condition is satisfied by a coin of bias 1 − 3ε − 18γ (as opposed to the version of Figure 8).

21

Proof. If Oblivious-Verifier-Approximate-Clique accepts with G’s sketch and randomness
r, then, in particular, the execution of Oblivious-Verifier-Clique-Execution with the guesses
that correspond to the run of Find-Approximate-Clique on G and r results in U such that for
˜ R′ ≥ 1 − 3ε − 9γ. By Corollary 6.8,
some U ′ ⊆ U , |R ∩ Γ(U ′ )| ≥ (1 − γ)ρ |V |, it holds that bias
U
biasU ′ ≥ 1 − 3ε − 18γ.
Next we argue that Oblivious-Verifier-Approximate-Clique rejects with probability exponentially small in |V |.
Lemma 6.11. The following hold:
• For any guesses, the probability that Oblivious-Verifier-Clique-Execution rejects is
exponentially small in |V |.
• Oblivious-Verifier-Clique-Execution makes a number of guesses that is sufficiently
smaller than |V | (the ratio between the number of guesses and |V | can be made arbitrarily
small by lowering ε by a constant factor and by increasing i0 by a constant).
The correctness of the final oblivious verifier follows from a union bound over all possible
choices of guesses. If the number of guesses is sufficiently smaller than |V |, the probability that
Oblivious-Verifier-Approximate-Clique rejects is exponentially small in |V |.
In order to show the two items above we show that three invariants hold. The invariants are in
Lemmas 6.12, 6.13 and 6.14.
Lemma 6.12. Throughout the execution of Oblivious-Verifier-Clique-Execution: G contains all the graphs that are consistent with the sketch and guesses so far.
Proof. The invariant holds since G is initialized to contain all graphs consistent with the sketch,
and since after each guess G is updated to contain only those graphs in G that are consistent with
the guess.
Lemma 6.13. Throughout the execution of Oblivious-Verifier-Clique-Execution: The probability of reaching counter = c is exponentially small in c.
Proof. counter is initially 0. The increase in step 7 is justified as follows. When this step occurs,
˜ R′ < 1 − 2ε − β/2 + 9γ for all U ′ such that |R ∩ Γ(U ′ )| ≥ (1 − γ)ρ |V |. By Corollary 6.8, for
bias
U
˜ R′ − biasU ≤ 9γ. Hence, when step 7 occurs
all U ′ such that |Γ(U ′ )| ≥ (1 − 2γ)ρ |V |, we have bias
U
for all U ′ with |Γ(U ′ )| ≥ ρ |V |, it holds that biasU ′ < 1 − 2ε (here we also use Lemma 6.6). By
Lemma 6.3, for every graph in G, the probability that this happens is e−25/ε , and therefore the
increase in counter is justified. The increase in Step 14 follows from the correctness of ObliviousVerifier-Clique-Coin-Toss (Note that we take a union bound over 2u possible U ′ ).
Lemma 6.14. If Oblivious-Verifier-Clique-Execution restarts in phase i then counter increases by at least β 2 2i−1 − u either in the restart phase or in the previous phase, or it is the first
phase and counter increases by 25/ε.
Proof. Suppose that there is a restart in phase i. Let k = 2i . By Lemma 4.4, either in this iteration,
or in the previous iteration, there exists a non-faulty coin in the group that yielded a fraction of
heads that deviates from its bias by an additive β/2, or it’s the first phase and a group with bias
at most 1 − 2ε − β/2 was picked. Next we handle each of these cases.
22

1. Suppose that i = i0 and max { biasU ′ | |Γ(U ′ )| ≥ ρ |V |} < 1 − 2ε − β/2. By Lemma 6.6,
˜ R′ − biasU ′ ≤ 9γ. This implies
|R ∩ Γ(U ′ )| ≥ (1 − γ)ρ |R|, and, hence, by Corollary 6.8, bias
U
˜ R′ < 1 − 2ε − β/2 + 9γ and that counter increases in step 7.
that bias
U
′

2. Suppose that there exists U ′ ⊆ U with |Γ(U ′ )| ≥ ρ |V | such that biasVU ′ deviates from biasU ′
by at least β/2 in phase i or i − 1. By Lemma 6.9 (and Lemma 6.6), since 29γ < β/2 and
Clique-Coin-Toss does not fail on U ′ , we know that Clique-Coin-Toss rejects and that
counter increases in Step 14.
The lemma follows.
Next we prove Lemma 6.11 from the invariants in Lemmas 6.12, 6.13 and 6.14.
Proof. (of Lemma 6.11 from invariants) Rejection is caused either by counter reaching |V |, which
happens with probability exponentially small in |V | by Lemma 6.13, or by Find-ApproximateClique, running on any of the graphs in G (recall that G =
6 φ), returning, by Corollary 6.8, U ′
such that biasU ′ < 1 − 3ε. We already saw that the latter has probability exponentially small in
|V | for any graph in G in Section 6.2.
The second item follows from Lemma 6.14 and since counter increases by large increments and
counter ≤ |V |. The increments are either at least β 2 2i0 −1 − u (which corresponds to the constant
term in i0 ) or 25/ε.
A non-uniform deterministic algorithm for approximate clique follows, concluding the proof of
Theorem 1.2 (note that ε in Theorem 1.2 is replaced with O(ε/ρ) here).
Theorem 6.15. There is a deterministic non-uniform algorithm that given 0 < ρ, ε < 1 and a graph
G = (V, E) with a clique on ρ |V | vertices, finds a set of ρ |V | vertices and density 1 − O(ε/ρ). The
2
algorithm runs in time Õ(|V |2 2O(1/(ε ρ)) ).
Remark 6.2. There is a an alternative way to prove Theorem 6.15 based on the biased coin algorithm. It involves a more complicated randomized algorithm that can achieve lower error probability
and no sketching. First we devise a coin tossing algorithm that achieves error probability exponentially small in k for any 1 ≤ k ≤ |V | while running in time O(k |U ′ | poly(1/ρ, 1/γ)). This algorithm
′
picks V ′ ⊆ V like Clique-Coin-Toss, but then instead of computing biasVU ′ directly, it estimates
′
biasVU ′ by picking for every v ∈ V ′ a small independent sample to estimate the fraction of Γ(U ′ )
vertices that neighbor it. The observation is that it suffices that the estimates for most v ∈ V ′ are
′
accurate in order for the estimate for biasVU ′ to be accurate. By repeating this coin tossing algorithm r times, we can obtain a coin tossing algorithm that runs in time O(kr |U ′ | poly(1/ρ, 1/γ))
and achieves error probability exponentially small in kr for any r ≥ 1. Via the biased coin algo2
rithm, we obtain a Las Vegas algorithm that runs in time Õ(|V |2 2O(1/(ε ρ)) ) and achieves error
probability exponentially small in |V |2 . This implies a deterministic non-uniform algorithm that
runs in the same time.

23

7

Free Games

7.1

A Simple Randomized Algorithm

First we describe a simple randomized algorithm with constant error probability for free games
based on the sampling idea in the Max-Cut algorithm. A similar algorithm appeared in [1]. The
main idea of the algorithm is as follows. We sample a small S ⊆ X and enumerate over all possible
labelings h : S → Σ. Each labeling induces a labeling to all vertices as follows.
Definition 7.1 (Induced labeling). Let G be a free game on a graph G = (X, Y, X × Y ), alphabet
Σ and constraints {πe }. Let S ⊆ X and let h : S → Σ be a labeling to S.
• The induced labeling fS,h,Y : Y → Σ is defined as follows: For every y ∈ Y let fS,h,Y (y) be the
label σ ∈ Σ that maximizes the fraction of edges e = (s, y) ∈ S × {y} such that (h(s), σ) ∈ πe
(ties are broken arbitrarily).
• The induced labeling fS,h,X : X → Σ is defined as follows: For every x ∈ X let fS,h,X (x)
be the label σ ∈ Σ that maximizes the fraction of edges e = (x, y) ∈ {x} × Y such that
(σ, fS,h,Y (y)) ∈ πe (ties are broken arbitrarily).
Note that for each y ∈ Y computing fS,h,Y (y) takes time O(|Σ| |S|). For each x ∈ X computing
fS,h,X (x) takes time O(|Σ| |Y |).
We will argue below that if h is the restriction of an optimal assignment to G, then the induced
labeling is likely to approximately achieve the value of G.
Lemma 7.2 (Sampling). Let G be a free game on a graph G = (X, Y, X × Y ) and with alphabet
Σ. Let ε, δ > 0. Then for a uniform S ⊆ X, |S| = ⌈log(|Σ| /εδ)/ε2 ⌉, with probability at least 1 − δ,
there exists h : S → Σ such that fS,h,X , fS,h,Y satisfy at least val(G) − 2ε fraction of the edges in
G.
∗ : X → Σ, f ∗ : Y → Σ that achieves the value of G, namely,
Proof. There is a labeling fX
Y
∗ to S. Let y ∈ Y . Let σ ∈ Σ. By a
valfX∗ ,fY∗ (G) = val(G). Let h : S → Σ be the restriction of fX
Chernoff bound except with probability εδ/ |Σ|, the fraction of edges e = (s, y) ∈ S × {y} such that
(h(s), σ) ∈ πe , is the same up to an additive ε as the fraction of edges e = (x, y) ∈ X × {y} such
∗ (x), σ) ∈ π . By a union bound over all σ ∈ Σ, for each y ∈ Y , except with probability at
that (fX
e
most εδ over S, this holds for all σ ∈ Σ. In other words, for a uniform S, the expected fraction
of y ∈ Y for which this holds is at most εδ. Thus, with probability at most δ over the choice of
S, for at least 1 − ε fraction of the y ∈ Y , this holds. Therefore, except for at most δ fraction of
the S, we have valfX∗ ,fS,h,Y (G) ≥ valfX∗ ,fY∗ (G) − 2ε = val(G) − 2ε. The lemma follows noticing that
valfS,h,X ,fS,h,Y (G) ≥ valfX∗ ,fS,h,Y (G).

7.2

A Randomized Algorithm With Exponentially Small Error Probability

We think of sampling S ⊆ X as picking a group of coins. The group has a coin per h : S → Σ. The
bias of the coin is the fraction of edges satisfied by fS,h,X and fS,h,Y . One tosses a coin k times
by picking roughly k vertices X ′ ⊆ X and estimating the success of fS,h,X and fS,h,Y on edges
that touch X ′ . The coin tossing algorithm is described in Figure 12. For a deviation parameter
γ dictating by how much the coin toss deviates from the actual bias and for k dictating the error
probability, the toss runs in time k |Y | · poly(|Σ| , 1/ε, 1/γ).
24

Free-Toss-Coin(G, S, h, k, γ)
1
2
3
4
5

Compute fS,h,Y (y) for all y ∈ Y .
Pick X ′ ⊆ X, |X ′ | = ⌈(k + |S| log |Σ|)/γ 2 ⌉, uniformly at random.
For all x ∈ X ′ and σ ∈ Σ compute the fraction of y ∈ Y so (σ, fS,h,Y (y)) ∈ π(x,y) .
For all x ∈ X ′ let gS,h,x be the max over σ ∈ Σ of the fractions.
P
′ .
′
return biasX
x∈X ′ gS,h,x fraction heads.
S,h = (1/ |X |)

Figure 12: A coin toss picks vertices at random and estimates how many of the edges that touch
the sample are satisfied by fS,h,X and fS,h,Y .
′

Let biasS,h be the fraction of edges satisfied by fS,h,X and fS,h,Y . For X ′ ⊆ X, let biasX
S,h
be the fraction of edges that touch X ′ and are satisfied by fS,h,X , fS,h,Y . For each x ∈ X let
gS,h,x beP
the fraction of edges that touch
fS,h,X , fS,h,Y . We have biasS,h =
Px and are satisfied by
′
(1/ |X|) x∈X gS,h,x , and and (1/ |X ′ |) x∈X ′ gS,h,x = biasX
.
S,h The following lemma shows that
′
X
the estimate biasS,h of the coin tossing algorithm typically doesn’t deviate much from the actual
bias biasS,h .
Lemma 7.3. Except with probability exponentially small in k, for all h : S → Σ,
′

biasX
S,h − biasS,h ≤ γ.
Proof. By a Hoeffding bound, except with probability exponentially small in k + |S| log |Σ| we have,
1 X
gS,h,x − biasS,h ≤ γ.
|X ′ |
′
x∈X

The lemma follows from a union bound over all h : S → Σ.
Using an algorithm for the biased coin problem we get an algorithm for finding a good labeling
to a free game. The algorithm is described in Figure 13.
The algorithm proves part of Theorem 1.3 repeated here for convenience.
Theorem 7.4. Given a free game G with vertex sets X, Y , alphabet Σ, and val(G) ≥ 1 − ε0
and given ε > 0, the algorithm Find-Labeling finds a labeling for G that achieves value at least
1 − ε0 − 3ε except with probability exponentially small in |X| |Σ|. The algorithm runs in time
2
Õ(|X| |Y | |Σ|O((1/ε ) log(|Σ|/ε)) ).
In the remainder of the section we construct an oblivious verifier for free games and prove the
rest of Theorem 1.3, namely show a deterministic non-uniform algorithm.

7.3

A Sketch for Free Games

In this section we show that free games can be sketched using Õ(|X| |Σ|2 poly(1/ε)) bits (as opposed
to O(|X| |Y | |Σ|2 ) bits needed to describe the entire input game). The idea is to store the sub-game
25

Find-Labeling(G = (G = (X, Y, X × Y ), Σ, {πe }), ε0 , ε)
1
2
3
4
5
6
7
8
9
10

Set s = ⌈log(|Σ| /ε2 )/ε2 ⌉.
Set if = log((|X| |Σ| + s log |Σ|)/ε2 ) + Θ(log log((|X| |Σ| + s log |Σ|)/ε)); β = ε/if .
Set i0 = log(s log |Σ| /β 2 ) + Θ(1).
Sample S ⊆ X, |S| = s.
for i = i0 , i0 + 1, . . . , if
Set k = 2i .
for all h : S → Σ
Free-Toss-Coin(G, S, h, β 2 k, γ = β/80).
If the fraction of heads is less than 1 − ε0 − 2ε − iβ for all h, restart.
return labeling fS,h,X , fS,h,Y with value at least 1 − ε0 − 3ε, if such exists.

Figure 13: An algorithm for finding a good labeling to a free game G with val(G) ≥ 1 − ε0 . The
error probability of the algorithm is exponentially small in |X| |Σ|.
GR induced on a small and carefully chosen set R ⊆ Y , that is, store all the constraints of the form
π(x,y) for x ∈ X and y ∈ R. We will show that this allows us to estimate the bias of every coin, as
well as the value of the labeling induced by the coin on the random samples the algorithm makes.
R
be the maximum over σ ∈ Σ of the fraction of vertices y ∈ R such
Let x ∈ X. Let gS,h,x
P
′ ,R .
.
R
that (σ, fS,h,Y (y)) ∈ π(x,y) . We use the notation biasX,R
= (1/ |X|) x∈X gS,h,x
and biasX
=
S,h
S,h
P
R
′
(1/ |X |) x∈X ′ gS,h,x for the bias of S, h as witnessed by R.

Lemma 7.5 (Free game sketch). Let s be as in Figure 13. Then, there exists R ⊆ Y , |R| =
⌈s(s + 1) log |Σ| log |X| /γ 2 ⌉, such that for all S ⊆ X, |S| = s, for all h : S → Σ, for every x ∈ X
we have
R
− gS,h,x ≤ γ.
gS,h,x
′

X ,R
′
X
As a result, biasX,R
S,h − biasS,h ≤ γ, and, for all X ⊆ X, biasS,h − biasS,h ≤ γ.
′

Proof. Pick uniformly at random R ⊆ Y of the specified size. Let S ⊆ X, |S| = s, h : S → Σ,
x ∈ X. By applying a Chernoff bound for every σ ∈ Σ and taking a union bound over σ ∈ Σ, we get
R
− gS,h,x ≤ γ except with probability smaller than |Σ|−s |X|−(s+1) . By a union bound
that gS,h,x
R
− gS,h,x ≤ γ
over all S, h and x, we get that there exists R ⊆ Y of the specified size such that gS,h,x
always holds. The claims about bias follow.

7.4

Oblivious Verifier for Free Games

We design an oblivious verifier for Find Labeling, which we call Oblivious-Verifier-FreeExecution. The verifier gets the sketch of the input and the randomness of the algorithm Find
Labeling, and follows the execution of the algorithm by guessing when it decides to restart.
The final verifier, Oblivious-Verifier-Free-Game, checks all possible guesses. During its run
Oblivious-Verifier-Free-Execution maintains counter recording the low probability events
it witnessed. If counter ever reaches a value larger than |X| |Σ|, the verifier rejects. The verifier
26

also maintains H the family of all free games consistent with the execution so far. If H becomes
empty, the execution is designated as infeasible. Initially, counter = 0 and H contains all free
games consistent with the sketch. The final verifier checks that, no matter what were the guesses,
all feasible executions of Oblivious-Verifier-Free-Execution accept. We argue that since the
algorithm has error probability that is exponentially small in |X| |Σ|, the probability that the final
verifier rejects is exponentially small in |X| |Σ| as well.
The verifier for a single execution (a single set of guesses) is described in Figure 14. Note that
it uses the parameters i0 , if , β of the algorithm. The final verifier is described in Figure 15.
Oblivious-Verifier-Free-Execution(H, GR , ε0 , ε, r, counter)
1 if H = φ
2
return infeasible.
3 if counter > |X| |Σ|
4
return reject.
5 Extract from r the sample S ⊆ X of the algorithm.
6 if maxh biasX,R
S,h < 1 − ε0 − 3ε − β/2 + γ
7
counter ← counter + log(1/ε)
8 for i = i0 , i0 + 1, . . . , if
9
k ← 2i .
10
for all h : S → Σ
11
Extract from r the sample X ′ ⊆ X of the algorithm.
′ ,R
12
Compute biasX
S,h .
13
14
15
16
17
18

′

,R
X,R
if ∃h, biasX
S,h − biasS,h > 3γ

counter ← counter + β 2 k − s log |Σ|.
′
Guess if maxh biasX
S,h < 1 − ε0 − 2ε − iβ and update H accordingly.
if guessed true
Restart maintaining H and counter.
return accept iff maxh biasX,R
S,h ≥ 1 − ε0 − 3ε − γ.

Figure 14: An oblivious verifier for a single execution of Find-Labeling (an execution is defined
by the outcomes of guesses). The final oblivious verifier checks that all feasible executions are
accepted.

Oblivious-Verifier-Free-Game(GR , ε0 , ε, randomness)
1 Let H contain all the free games that are consistent with GR .
2 Try all guesses in Oblivious-Verifier-Free-Execution(H, GR , ε0 , ε, randomness, 0).
3 Accept iff all feasible executions accept.

Figure 15: The final oblivious verifier for free games.
Next we analyze the oblivious verifier. We start by showing that when it accepts, Find27

Labeling finds a high quality labeling (even if slightly of lower quality than in Figure 13).
Lemma 7.6. If Oblivious-Verifier-Free-Game accepts on the sketch of a game G and on
randomness r, then Find-Labeling3 produces a labeling that satisfies at least 1 − ε0 − 3ε − 2γ
fraction of the edges when invoked on G and r and with the same parameters ε0 , ε.
Proof. Let G be the input game to Find-Labeling. If Oblivious-Verifier-Free-Game accepts
with the sketch GR , then, in particular, the execution of Oblivious-Verifier-Free-Execution
with the guesses that correspond to the run of Find-Labeling accepts. By Lemma 7.5, FindLabeling finds a labeling that satisfies 1 − ε0 − 3ε − 2γ fraction of the edges.
In order to argue that Oblivious-Verifier-Free-Game rejects with probability exponentially
small in |X| |Σ| we prove the following.
Lemma 7.7. The following hold:
• For any guesses, the probability that Oblivious-Verifier-Free-Execution rejects is exponentially small in |X| |Σ|.
• Oblivious-Verifier-Free-Execution makes a number of guesses that is sufficiently smaller
than |X| |Σ| (the ration between the number of guesses and |X| |Σ| can be made arbitrarily
small by multiplying ε by a suitable constant and by increasing the constant term of i0 ).
The correctness of the final verifier follows from a union bound over all possible guesses. If the
number of guesses is sufficiently small, then there is an exponentially small probability in |X| |Σ|
that the final verifier rejects.
In order to prove Lemma 7.7, we show the following invariants.
Lemma 7.8. The following invariants are maintained throughout the run of Oblivious-VerifierFree-Execution:
1. H consists of all the free games that are consistent with the sketch and the guesses so far.
2. The probability that counter = c is exponentially small in c.
3. If Oblivious-Verifier-Free-Execution restarts in phase i, then either in the current
phase or in the previous counter increases by at least β 2 2i−1 − s log |Σ|, or i = i0 and counter
increases by log(1/ε).
Proof. It’s clear that Invariant 1 holds. Next we show that Invariant 2 holds. Initially counter is
set to 0. The increase in Step 7 is justified by Lemma 7.2 and the design of the sketch (Lemma 7.5).
The increase in Step 14 is justified by Lemma 7.3 and the design of the sketch (Lemma 7.5).
Next we show that Invariant 3 holds. Suppose that there is a restart in phase i. Let k = 2i .
′
Lemma 4.4 ensures that either in the current phase or in the previous one maxh biasX
S,h deviates
from maxh biasS,h by more than an additive β/2, or it’s the first phase and maxh biasS,h is smaller
than 1 − ε0 − 2ε − β/2. We handle both cases:
3

Note that we argue about a version of Find-Labeling that checks a relaxed condition that is satisfied by a coin
of bias 1 − ε0 − 3ε − 2γ (as opposed to the version of Figure 13).

28

1. Suppose that this is the first phase and maxh biasS,h < 1 − ε0 − 2ε − β/2. By the design of
the sketch (Lemma 7.5), we have maxh biasX,R
S,h < 1 − ε0 − 2ε − β/2 + γ, and hence counter
increases as required in Step 7.
′

2. Suppose that either in the current phase or in the previous one maxh biasX
S,h deviates from
maxh biasS,h by more than an additive β/2. By the design of the sketch (Lemma 7.5), either
′

,R
X,R
in this phase or in the previous there exists h : S → Σ such that biasX
S,h − biasS,h > 3γ.
In this case, counter increases appropriately in Step 14 of the appropriate phase.

We can now prove Lemma 7.7 from the invariants of Lemma 7.8.
Proof. (of Lemma 7.7 from Lemma 7.8) Let us show that the first item in Lemma 7.7 follows from
Invariant 2. The verifier only rejects if counter > |X| |Σ|, or if it reached Step 18 and rejected.
The invariant ensures that the probability that counter > |X| |Σ| is exponentially small in |X| |Σ|.
Theorem 7.4 ensures that the probability that maxh biasS,h < 1 − ε0 − 3ε is exponentially small
in |X| |Σ|. The design of the sketch (Lemma 7.5) ensures that if maxh biasS,h ≥ 1 − ε0 − 3ε, then
maxh biasX,R
S,h ≥ 1 − ε0 − 3ε − γ.
The second item follows from Invariant 3, since counter < |X| |Σ|, and, counter increases in
large increments: Invariant 6.14 ensures that the increments only depend on ε and i0 , and can be
made arbitrarily large by multiplying ε by a small constant and by adding to i0 a large constant.
A non-uniform deterministic algorithm for free games follows, concluding the proof of Theorem 1.3.
Theorem 7.9. There is a deterministic non-uniform algorithm that given a free game G with vertex
sets X, Y , alphabet Σ and val(G) ≥ 1 − ε0 , finds a labeling to the vertices that satisfies 1 − ε0 − O(ε)
2
fraction of the edges. The algorithm runs in time Õ(|X| |Y | |Σ|O((1/ε ) log(|Σ|/ε)) ).
We remark that there is an alternative way to prove Theorem 7.9 similarly to Remark 6.2.

8
8.1

From List Decoding to Unique Decoding of Reed-Muller Code
A Randomized Algorithm With Error Probability Roughly 1/ |F|

Let F be a finite field, and let m > 3 and d < |F| be natural numbers. First we describe a
randomized algorithm with error probability |F|−Ω(1) for reducing the Reed-Muller list decoding
problem with parameters F, m, d to the Reed-Muller unique decoding problem. The algorithm
is based on the idea of self-correction (see, e.g., [33] and the references there). The algorithm is
described in Figure 16. On input f : Fm → F it picks a random line ℓ and finds all the polynomials
that agree with f on about ρ fraction of the points in ℓ. We’ll show that if f agrees with an mvariate polynomial p on ρ fraction of the points in Fm , then, except with probability roughly 1/ |F|
over the choice of ℓ, there is about ρ fraction of the points on ℓ on which f agrees with p. Hence, the
restriction of p to ℓ is likely to be one of the polynomials that the algorithm finds. The algorithm
outputs a list of functions g1 , . . . , gk : Fm → F. Each gi corresponds to one of the polynomials
in the line list. The algorithm computes each gi by iterating over all z ∈ Fm and considering the
29

plane s spanned by ℓ and z. Again, except for fraction roughly 1/ |F| of the z ∈ Fm , there is about
ρ fraction of the points on s on which f agrees with p. The algorithm sets gi (z) = f (z) if there
is a unique polynomial that agrees with f on about ρ fraction of the points in s and with gi ’s
polynomial on ℓ.
Self-Correct(f, ρ, ǫ)
1 Pick uniformly at random x, y ∈ Fm ,ny 6= ~0.
(1)

(k)

2 Find all univariate px,y , . . . , px,y so

o
(j)
t ∈ F | f (x + ty) = px,y (t) ≥ (ρ − ǫ) · |F|.

3 for z ∈ Fm such that z − x, y are independent
′
4
Find q (1) , . . . , q (k ) : t1 , t2 ∈ F | f (x + t1 y + t2 (z − x)) = q (j) (t1 , t2 )
5
for 1 ≤ i ≤ k
(i)
6
if ∃! 1 ≤ j ≤ k′ , px,y (t) = q (j) (t, 0) for all t ∈ F
7
Set gi (z) = q (j) (0, 1).
8 return g1 , . . . , gk .

≥ (ρ − ǫ) · |F|2 .

Figure 16: A randomized algorithm with error probability |F|−Ω(1) that finds g1 , . . . , gk : Fm → F,
k ≤ O(1/ρ), such that for every polynomial p of degree at most d that agrees with f on ρ fraction
of the points in Fm there is gi that agrees with p on at least 1 − ǫ fraction of the points.
Steps 2 and 4 that require list decoding of Reed-Solomon code can be performed in time
poly(|F|). Therefore, the run time of the algorithm is O(|Fm | poly(|F|)). A standard choice of
parameters is |F| = poly log |Fm |, and it leads to a run-time of Õ(|Fm |). Next we prove the correctness of the algorithm.
We’ll need the following lemma about list decoding for polynomials.
Lemma 8.1 (List decoding).
Fix a finite field F and natural numbers m and d < |F|. Let f : Fm →
q

d
, if q1 , . . . , qk : Fm → F are different polynomials of degree at most d,
F. Then, for any ρ ≥ 2 |F|
and for every 1 ≤ i ≤ k, the polynomial qi agrees with f on at least ρ fraction of the points, i.e.,
Prx∈Fm [qi (x) = f (x)] ≥ ρ, then k ≤ ρ2 .
q
d
Proof. Let ρ ≥ 2 |F|
, and assume on way of contradiction that there exist k = ⌊ 2ρ ⌋ + 1 different
polynomials q1 , . . . , qk : Fm → F as stated.
.
For every 1 ≤ i ≤ k, let Ai = { x ∈ Fm | qi (x) = f (x)}. By inclusion-exclusion,

|Fm | ≥

k
[

i=1

Ai ≥

k
X

|Ai | −

i=1

X

|Ai ∩ Aj |

i6=j

d
By Schwartz-Zippel, for every 1 ≤ i 6= j ≤ k, |Ai ∩ Aj | ≤ |F|
· |Fm |. Therefore, by the premise,
 
k d m
m
m
|F | ≥ kρ |F | −
|F |
2 |F|
q
2
2
On one hand, since k > ρ , we get kρ > 2. On the other hand, since ρ ≤ |F|
d and d ≤ |F|, we get
 |F|
k
2 ≤ d . This results in a contradiction.

30

Let p be an m-variate polynomial of degree at most d over F that agrees with f on at least ρ
fraction of the points x ∈ Fm . We will show that most likely one of the gi ’s that the algorithm
outputs is very close to p.
In the following lemma we argue that the restriction of p to the line defined by x and y is likely
to appear in the line list.
Lemma 8.2 (Sampling). Except with probability ρ/(ǫ2 |F|) over the choice of x and y, for at least
(ρ − ǫ) |F| elements t ∈ F we have f (x + ty) = p(x + ty).
Proof. The lemma follows from a second moment argument. Let A ⊆ Fm , |A| = ρ |Fm | contain
elements z ∈ Fm such that f (z) = p(z). For uniformPx, y ∈ Fm , for t ∈ F let Xt be an indicator
random variable for x + ty ∈ A. Let X = (1/ |F|) Xt . We have
 E [X] = 2ρ.
P For every t 6=
′
2
′
t ∈ F we have that Xt and Xt are independent. Hence, E X = (1/ |F|)
t,t′ E [Xt Xt′ ] =
P
2
(1/ |F|)
t E [Xt ] = ρ/ |F|. By Chebychev inequality,
 
ρ
E X2
= 2 .
Pr [|X − ρ| > ǫ] ≤
2
ǫ
ǫ |F|
The lemma follows.
The same holds for the planes defined by most z ∈ Fm .
Lemma 8.3 (Sampling). Except with probability ρ/(ǫ2 |F|) over the choice of z, x and y, for at
least (ρ − ǫ) |F|2 elements t1 , t2 ∈ F, we have f (x + t1 y + t2 (z − x)) = p(x + t1 y + t2 (z − x)).
From Lemmas 8.2 and 8.3 it follows that except with probability roughly 1/ |F| restrictions of
p appear both in the line list and in most planes lists. Next we’ll argue that for most z ∈ Fm it’s
unlikey that the restriction of p to the plane is not the unique polynomial in the plane list that
agrees with p on the line.
Lemma 8.4. The probability over the choice of x, y and z that there are 1 ≤ j < i ≤ k ′ such that
q (j) (t, 0) ≡ q (i) (t, 0) even though q (j) 6≡ q (i) , is at most 4d/((ρ − ǫ)2 |F|).
Proof. Fix 1 ≤ j < i ≤ k′ . Suppose that one first picks the three dimensional subspace s and then
picks x, y, z ∈ Fm such that { x + t1 y + t2 (z − x) | t1 , t2 ∈ F}. The probability over the choice of
x and y, that q (j) agrees with q (i) on the line { x + ty | t ∈ F} is at most d/ |F|. By Lemma 8.1,
there are at most 2/(ρ − ǫ) polynomials in the list of s. Taking a union bound over all choices of
1 ≤ j < i ≤ k′ results in the lemma.

Hence, except with probability O(δ) over x, y for δ = max d/(ρ2 |F|), ρ/(ǫ2 |F|) , the restriction
(i)

of p to the line { x + ty | t ∈ F} appears as px,y , and, moreover, gi agrees with p on all but O(δ)
fraction of the z (note that only a small fraction |F|2 / |Fm | of the z ∈ Fm satisfy that z − x, y are
dependent).

8.2

Finding Approximate Codewords as Finding a Biased Coin

We describe an analogy between finding a list of approximate polynomials and finding a biased
coin. We think of picking a line and finding a list decoding of f on the line as picking a coin.
The coin picking algorithm is described in Figure 17. We think of sampling z ∈ Fm and checking
31

RM-Pick-Coin(f, ρ, ǫ)
1 Pick uniformly at random x, y ∈ Fm , y 6= ~0. n
o
(j)
(1)
(k)
2 Find univariate polynomials px,y , . . . , px,y so t ∈ F | f (x + ty) = px,y (t) ≥ (ρ − ǫ) · |F|.
(1)

(k)

3 return x, y, px,y , . . . , px,y .

Figure 17: A coin corresponds to a line in Fm and the list decoding of f on the line.
(1)

(k)

RM-Toss-Coin(f, ρ, ǫ, x, y, px,y , . . . , px,y )
1 Pick uniformly z ∈ Fm independent of x, y.
′
2 Find q (1) , . . . , q (k ) so |{ t1 , t2 ∈ F | f (x + t1 y + t2 (z − x)) = q(t1 , t2 )}| ≥ (ρ − ǫ) · |F|2 .
3 for 1 ≤ i ≤ k
(i)
4
if ¬∃!1 ≤ j ≤ k′ , px,y (t) ≡ q (j) (t, 0)
5
return “tails”.
6 return “heads”.

Figure 18: A coin toss corresponds to picking a uniform z ∈ Fm and checking whether the line
list decoding is consistent with the list decoding on the subspace defined by the line and z.
whether the line list decoding is consistent with the list decoding on the subspace defined by z and
the line as a coin toss that falls on “heads” if there is consistency. The coin tossing algorithm is
described in Figure 18.
Lemmas 8.2, 8.3 and 8.4 ensure that a biased coin is picked with at least a constant probability
for sufficiently large ρ > ǫ > 0 and sufficiently small d < |F|. Note that both picking a coin and
tossing it take short time poly(|F|). Hence, if we use Õ(|Fm |) coin tosses to find a biased coin and
|F| = poly log |Fm |, then we get an algorithm with Õ(|Fm |) run-time. Moreover, using a biased coin
one can compute a short list of approximate polynomials as in Figure 19.
(1)

(k)

Lemma 8.5. Assume that x, y, px,y , . . . , px,y define a biased coin (namely, a coin that falls on
“heads” with probability at least 1 − O(δ) for δ as in Section 8.1), and that ǫ is smaller than O(δ)
from Section 8.1. Then, for every m-variate polynomial p of degree at most d over F there exists
gi in the list computed by RM-Interpolate that agrees with p on at least 1 − O(δ) fraction of the
points.
Proof. Let p be an m-variate polynomial of degree at most d over F that agress with f on at least
(1)
(k)
ρ fraction of the points x ∈ Fm . Assume on way of contradiction that none of px,y , . . . , px,y is p
restricted to the line { x + ty | t ∈ F} (otherwise, we are done as we argued in Section 8.1). Take ǫ
sufficiently smaller than O(δ) in the lemma. For at least ǫ fraction of the z ∈ Fm such that z − x, y
are independent, the fraction of points x + t1 y + t2 (z − x) with t1 , t2 ∈ F on which f agrees with
p, is at least ρ − ǫ. For those choices of z, the coin falls on “tails”, hence the bias of the coin is at
most 1 − ǫ, which is a contradiction.
Therefore, Find-Biased-Coin when using RM-Pick-Coin and RM-Toss-Coin, and when
32

(1)

(k)

RM-Interpolate(f, ρ, ǫ, x, y, px,y , . . . , px,y )
1 for z ∈ Fm independent of x, y
′
2
Find q (1) , . . . , q (k ) so |{ t1 , t2 ∈ F | f (x + t1 y + t2 (z − x)) = q(t1 , t2 )}| ≥ (ρ − ǫ) · |F|2 .
3
for 1 ≤ i ≤ k
(i)
4
if ∃! 1 ≤ j ≤ k′ , px,y (t) = q (j) (t, 0) for all t ∈ F
5
Set gi (z) = q (j) (0, 1).
6 return g1 , . . . , gk .

(1)

(k)

Figure 19: An algorithm that uses a biased coin (given by x, y, px,y , . . . , px,y ) to find a short list
of functions g1 , . . . , gk : Fm → F such that for every polynomial p of degree at most d that agrees
with f on ρ fraction of the points in Fm there is gi that agrees with p on at least 1 − ǫ fraction of
the points.
followed by RM-Interpolate to obtain the list of approximate polynomials from the coin, solves
the list decoding to unique decoding problem for the Reed-Muller code in time Õ(|Fm | poly(|F|)) and
with error probability exponentially small in |Fm | log |F|. Since the input f, ρ, ǫ is of size |Fm | log |F|,
we also get a deterministic non-uniform algorithm that runs in similar time. For convenience, we
repeat Theorem 1.5 that we just proved.
Theorem 8.6. Let F be
a finite field, let d and
p m > 3 be natural numbers and let 0 < ρ, ǫ < 1, such
p
3
that d ≤ |F| /10, ǫ > 2/ |F| and ρ > ǫ + 2 d/ |F|. There is a randomized algorithm that given
f : Fm → F, finds a list of l = O(1/ρ) functions g1 , . . . , gl : Fm → F, such that for every m-variate
polynomial p of degree at most d over F that agrees with f on at least ρ fraction of the points x ∈ Fm ,
there exists gi that agrees with p on at least 1 − ǫ fraction of the points x ∈ Fm . The algorithm has
error probability exponentially small in |Fm | log |F| and it runs in time Õ(|Fm | poly(|F|)). It implies
a deterministic non-uniform algorithm with the same run-time.

9

Open Problems
• We obtained efficient non-uniform deterministic algorithms. It would be very interesting to
convert them to uniform algorithms.
• What other algorithms can be derandomized using our method? Can more sophisticated
sketching and sparsification techniques be used to handle algorithms on sparse graphs? The
applications in this paper have Atlantic City algorithms that run in sub-linear time, but we do
not think that the method is limited to such problems. It will be interesting to find concrete
examples.
• What lower bound can one prove on the number of coin tosses needed to find a biased coin?
What if the target bias is not known, yet it is known that a large fraction of the coins achieve
that target? Solving the latter would yield an algorithm for Free Games that handles games
with general value, rather than value close to 1.

33

• Can one derandomize algorithms using pseudorandom generators and make use of the fact
that the pseudorandomness should look random only to a distinguisher that is a verifier
for the algorithm? Can one use the existence of an oblivious verifier to construct better
psuedorandom generators?
• Are there deterministic algorithms for Max-Cut on dense graphs that run in time Õ(|V |2 +
2
2
2
(1/ε)O(1/γε ) ) or even O(|V |2 + 2O(1/γε ) ) instead of Õ(|V |2 (1/ε)O(1/γε ) )? Recall that the
2 2
randomized algorithm of Mathieu and Schudy [28] runs in time O(|V |2 +2O(1/γ ε ) ). Are there
3 2
deterministic algorithms for (approximate) Clique that run in time Õ(|V |2 + 2O(1/(ρ ε )) )
2 O(1/(ρ3 ε2 ))
instead of Õ(|V | 2
)?
• The run-times of our algorithms have poly log n factors coming from our algorithm for the
biased coin problem and from the size of the sketches. Can they be eliminated?

Acknowledgements
Dana Moshkovitz is grateful to Sarah Eisenstat for her collaboration during the long preliminary
stages of this work. Many thanks to Scott Aaronson, Noga Alon, Bernard Chazelle, Shiri Chechik,
Shayan Oveis Gharan, Oded Goldreich, David Karger, Guy Moshkovitz, Michal Moshkovitz, Richard
Peng, Seth Pettie, Vijaya Ramachandran, Aaron Sidford, Dan Spielman, Bob Tarjan, Virginia Vassilevska Williams, Avi Wigderson and Ryan Williams for discussions.

References
[1] S. Aaronson, R. Impagliazzo, and D. Moshkovitz. AM with multiple Merlins. In Computational
Complexity (CCC), 2014 IEEE 29th Conference on, pages 44–55, 2014.
[2] L. Adleman. Two theorems on random polynomial time. In Proc. 19th IEEE Symp. on
Foundations of Computer Science, pages 75–83, 1978.
[3] M. Alekhnovich. Linear diophantine equations over polynomials and soft decoding of ReedSolomon codes. IEEE Transactions on Information Theory, 51(7):2257–2265, 2005.
[4] N. Alon, W. F. de la Vega, R. Kannan, and M. Karpinski. Random sampling and approximation
of MAX-CSPs. Journal of Computer and System Sciences, 67(2):212–243, 2003.
[5] N. Alon, R.A. Duke, H. Lefmann, V. Rödl, and R. Yuster. The algorithmic aspects of the
regularity lemma. Journal of Algorithms, 16(1):80 – 109, 1994.
[6] N. Alon, O. Goldreich, J. Håstad, and R. Peralta. Simple constructions of almost k-wise independent random variables. Random Structures and Algorithms, 3:289–304, 1992. Addendum:
Random Structures and Algorithms 4:119-120, 1993.
[7] S. Arora, D. Karger, and M. Karpinski. Polynomial time approximation schemes for dense
instances of NP-hard problems. In Proceedings of the Twenty-seventh Annual ACM Symposium
on Theory of Computing, Proc. 27th ACM Symp. on Theory of Computing, pages 284–293,
1995.

34

[8] B. Barak, M. Hardt, T. Holenstein, and D. Steurer. Subsampling mathematical relaxations and
average-case complexity. In Proceedings of the Twenty-second Annual ACM-SIAM Symposium
on Discrete Algorithms, SODA ’11, pages 512–531, 2011.
[9] A. A. Benczúr and D. R. Karger. Approximating s-t minimum cuts in Õ(n2 ) time. In Proc.
28th ACM Symp. on Theory of Computing, pages 47–55, 1996.
[10] W. Fernandez de la Vega. Max-cut has a randomized approximation scheme in dense graphs.
Random Struct. Algorithms, 8(3):187–198, 1996.
[11] D. Dellamonica, S. Kalyanasundaram, D. Martin, V. Rödl, and A. Shapira. A deterministic
algorithm for the Frieze-Kannan rerularity lemma. SIAM Journal on Discrete Math, 26:15–29,
2012.
[12] D. Dellamonica, S. Kalyanasundaram, D. Martin, V. Rödl, and A. Shapira. An optimal algorithm for finding Frieze-Kannan regular partitions. Combinatorics, Probability and Computing,
24(2):407–437, 2015.
[13] E. Even-Dar, S. Mannor, and Y. Mansour. PAC bounds for multi-armed bandit and Markov
decision processes. In Computational Learning Theory, volume 2375 of Lecture Notes in Computer Science, pages 255–270. Springer Berlin Heidelberg, 2002.
[14] U. Feige. Error reduction by parallel repetition - the state of the art, 1995.
[15] L. Fortnow and A. R. Klivans. Efficient learning algorithms yield circuit lower bounds. Journal
of Computer and System Sciences, 75(1):27 – 36, 2009.
[16] A. Frieze and R. Kannan. The regularity lemma and approximation schemes for dense problems. In Proc. 37th IEEE Symp. on Foundations of Computer Science, pages 12–20, 1996.
[17] E. Gat and S. Goldwasser. Probabilistic search algorithms with unique answers and their
cryptographic applications. Electronic Colloquium on Computational Complexity (ECCC),
18:136, 2011.
[18] O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and
approximation. Journal of the ACM, 45(4):653–750, 1998.
[19] P. Gopalan, R. Meka, and O. Reingold. DNF sparsification and a faster deterministic counting
algorithm. Computational Complexity, 22(2):275–310, 2013.
[20] V. Guruswami and M. Sudan. Improved decoding of Reed-Solomon and algebraic-geometry
codes. IEEE Transactions on information theory, 45:1757–1767, 1999.
[21] R. Impagliazzo, R. Meka, and D. Zuckerman. Pseudorandomness from shrinkage. In Proc.
53rd IEEE Symp. on Foundations of Computer Science, pages 111–119, 2012.
[22] R. Impagliazzo and A. Wigderson. P = BPP if E requires exponential circuits: Derandomizing
the XOR lemma. In Proc. 29th ACM Symp. on Theory of Computing, pages 220–229, 1997.
[23] D. R. Karger. Using randomized sparsification to approximate minimum cuts. In Proceedings
of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994,
Arlington, Virginia., pages 424–432, 1994.
35

[24] S. Khot. On the power of unique 2-prover 1-round games. In Proc. 34th ACM Symp. on
Theory of Computing, pages 767–775, 2002.
[25] M. Luby and A. Wigderson. Pairwise independence and derandomization. Foundations and
Trends in Theoretical Computer Science, 1(4):237–301, 2005.
[26] S. Mannor and J. N. Tsitsiklis. The sample complexity of exploration in the multi-armed
bandit problem. J. Mach. Learn. Res., 5:623–648, 2004.
[27] P. Manurangsi and D. Moshkovitz.
RANDOM, 2015.

Approximating dense max 2-CSPs.

In APPROX-

[28] C. Mathieu and W. Schudy. Yet another algorithm for dense max cut: go greedy. In Proceedings
of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San
Francisco, California, USA, January 20-22, 2008, pages 176–182, 2008.
[29] J. Naor and M. Naor. Small-bias probability spaces: Efficient constructions and applications.
SIAM Journal on Computing, 22(4):838–856, 1993.
[30] S. Pettie and V. Ramachandran. An optimal minimum spanning tree algorithm. Journal of
the ACM, 49(1):16–34, 2002.
[31] B. A. Subbotovskaya. Realizations of linear functions by formulas using +, *, -,. Sov. Math.
Dokl., 2:110–112, 1961.
[32] M. Sudan. Decoding of Reed Solomon codes beyond the error-correction bound. Journal of
Complexity, 13(1):180–193, 1997.
[33] M. Sudan, L. Trevisan, and S. P. Vadhan. Pseudorandom generators without the XOR lemma.
J. Comput. Syst. Sci., 62(2):236–266, 2001.
[34] E. Szemerédi. Regular partitions of graphs. In Problmes combinatoires et thorie des graphes
(Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), pages 399–401, 1978.
[35] M. Thorup and U. Zwick. Approximate distance oracles. In Proc. 33rd ACM Symp. on Theory
of Computing, pages 183–192, 2001.
[36] M. Zimand. Exposure-resilient extractors and the derandomization of probabilistic sublinear
time. computational complexity, 17(2):220–253, 2008.

36

