1. Introduction

In this course, we study a single broad question:

When does randomness help make computers more efficient?

This is a question that comes up in many different settings, and the answer varies greatly depending on the computational model.

We illustrate this variety with three examples.

Example 1: Communication Complexity of Equality

Consider the problem where Alice has a string \(x \in \{0,1\}^n\) and Bob has a string \(y \in \{0,1\}^n\). Alice and Bob want to determine if $x=y$ or not. How many bits of communication must Alice and Bob exchange to do so?

There is a simple protocol that Alice and Bob can follow to solve this problem: Alice uses $n$ bits to send $x$ over to Bob, and Bob sends 1 bit back to Alice to say whether his input $y$ is identical to $x$ or not. This naive solution, it turns out, is optimal among the set of all deterministic protocols for the problem. In communication complexity terms, we write this result as follows:

Theorem. \(\mathrm{D}(\mathsf{EQ}) = n+1\).

Can we do better with randomness? Consider first the public randomness model where there is a random string \(r \in \{0,1\}^n\) of \(n\) bits that Alice and Bob can both see. Can Alice and Bob use this common random string to obtain a much better protocol for checking equality?

The answer is an emphatic YES, if we let the protocol fail with some probability:

Theorem. There is a randomized protocol in which Alice and Bob each send exactly 1 bit to the other player and

As a consequence, \(R^{\mathrm{pub}}(\mathsf{EQ}) = O(1)\).

We can also consider a more restrictive private randomness model where both Alice and Bob can flip coins to generate random strings, but they can’t see each other’s random strings. Does randomness still help in this setting? Yes!

Theorem. \(\mathrm{R}^{\mathrm{private}}(\mathsf{EQ}) = \Theta( \log n)\).

Example 2: Time Complexity of \(\mathsf{MinCut}\)

Here’s another problem: given a weighted graph \(G\) with \(m\) edges on \(n\) vertices and a parameter \(k\), determine whether there is a cut in \(G\) with weight at most \(k\). (A cut in a graph is a partition of its vertex set $V$ into the pair $S$ and \(V \setminus S\) and its weight is the total weight of edges in \(G\) that have exactly one end vertex in \(S\).) This problem is (a decision version of the) minimum cut problem.

One of the classic results in algorithms research is that by using the Max-flow Min-cut Theorem, we can obtain a polynomial-time algorithm for this problem.

Theorem. \(\mathsf{MinCut} \in \mathbf{P}\).

If we consider polynomial-time to represent efficiency, this result states that randomness does not help for the \(\mathsf{MinCut}\) problem: we can already solve it efficiently deterministically. But if we take a finer-grained view and examine the exact time cost of the algorithm, we find that the classic algorithms for this problem have complexity roughly \(O(m n)\).

In 1993, David Karger introduced a radically different solution to the minimum cut problem for unweighted graphs: while the graph has more than 2 vertices, pick an edge uniformly at random and contract it. Surprisingly, the final cut we get that corresponds to the final 2-vertex graph is the minimum cut of the graph with probability at least \(\binom{n}{2}^{-1}\). Karger’s algorithm can be implemented to run in $O(m)$ time, but we need to run it multiple times to solve the minimum cut problem with small error, so that the complexity of this algorithm is no better than the deterministic algorithm. However, further work by Karger and Stein (1993) and Karger (1996) showed that randomness can be used to obtain a very efficient solution to the problem.

Theorem. There is a randomized algorithm that correctly solves the \(\mathsf{MinCut}\) problem with high probability in time \(O(m \log^3 n)\).

This time complexity is optimal up to the polylogarithmic factor, since \(\Omega(m)\) time is required just to read the edges of a graph. Can deterministic algorithms also match this near-optimal time complexity? The answer is yes, but this answer was only obtained very recently, by Henzinger, Li, Rao, and Wang (2024).

Theorem. There is a deterministic algorithm for \(\mathsf{MinCut}\) with time cost \(O(m \, \mathrm{polylog}\, n)\).

Example 3: Query Complexity of Graph Properties

Let’s consider yet another different model of computation. Our input is again a graph \(G\), but now the cost of our algorithms is the number of edge queries that the algorithm makes: the algorithm does not initially know the graph \(G\), but it can ask about any pairs of vertices in the graph and learn whether they are connected by an edge or not in \(G\). Let’s consider first a very simple problem in this model: determining if a graph \(G\) is empty or not. Can we solve this problem without querying all \(\binom{n}{2}\) vertex pairs in the graph?

Deterministically, no: with an adversary argument, we can see that any correct algorithm must sometimes query all possible vertex pairs before it can output the answer. We write this result in query complexity terms as follows.

Theorem. \(\mathrm{D}(\mathsf{Empty}) = \binom{n}{2}\).

(A note of warning: \(D(\cdot)\) is not the same complexity measure in this theorem as in our first example. Here, it represents query complexity; earlier it represented communication complexity. To be precise, we can distinguish them by writing \(D^{\mathrm{DT}}(\cdot)\) and \(D^{\mathrm{CC}}(\cdot)\) but in general we will try to minimize the additional superscripts when the measure should be clear from context or when we prove general results.)

With randomness, we can do a little bit better: instead of querying all \(\binom{n}{2}\) vertex pairs, if we are allowed to err with some small constant probability, then we only need to query a constant fraction of the vertex pairs. However, that is the only possible savings. Formally, we have the following query complexity bound.

Theorem. \(\mathrm{R}(\mathsf{Empty}) = \Theta( n^2 )\).

What about other graph properties: are there any of them that we can determine without querying all (or a constant fraction) of the vertex pairs? For monotone graph properties, the properties of graphs like \(\mathsf{Empty}\) that are preserved when we remove any edge, Rivest and Vuillemin (1975) showed that they are all evasive, in the sense that they have this maximal asymptotic query complexity.

Theorem. For every monotone property \(\mathsf{P}\) of graphs, \(\mathrm{D}(\mathsf{P}) = \Theta( n^2 )\).

Does the same bound hold for randomized algorithms? No one knows! The randomized evasiveness conjecture posits that it does, but the conjecture remains open to this day.