The Power of Randomness

Randomness is a fleeting commodity if you believe in the “Big Freeze” theory of our universe’s fate [3]. Should we survive as flesh or metal to explore the universe, a lack of randomness could make our algorithms and programs inefficient (if $P \neq BPP$), or at least it would likely be more complicated to write (if $P = BPP$) [1]. It is currently unknown which case we exist in, although most likely the former case, but neither are ideal situations. Randomness is particularly vital to a field I find great interest in, that is probabilistic proof systems [2] [5]. Although it may make winning the big lottery jackpot harder, we should be cherishing randomness while we have it, because in this blog post I will show examples where access to randomness can give us improvements in communication cost, running time, and space cost.

Communication Complexity Improvements

Imagine the following scenario. Alice and Bob are on opposite ends of the earth. Bob wants to check if a document that Alice has on her computer is the same as the one Bob has on his. How might Bob be convinced of this? Well, the first idea that probably comes to mind is for Alice to just send her file to Bob. If Alice is not using any coding theory techniques to detect if any errors occur during the transmission, which would be unlikely in practice, Alice would have to send the entire file to Bob. This may be doable if our file is small, but what if the file was all of Wikipedia? Or what if it were the Ethereum blockchain? That would start to become an issue. Unfortunately if we had to be 100% confident that our files were the same, there is no shortcut. However, if we were willing to allow some probability of one-sided error, that is Bob being convinced the files are the same when they are not, then we can utilize randomness to help us with this task. I will walk through an example of a protocol for this, then describe the protocol in technical detail, then prove the correctness of the protocol.

First, let’s assume that they already established that their file is the same size, because if not, they quickly know the contents aren’t the same. Suppose Alice has a file containing “hello”, as does Bob. Supposing we know the file contains only ASCII characters, then each character can be mapped to a number between 0 and 127, inclusive. So, “hello” gets mapped to “104 101 108 108 111”. We then interpret this encoded message as the polynomial

over the field $\mathbb{F}_{131}$. If you don’t know what a field is, don’t worry. I won’t go over it here, since there are many introductions to fields available online, including Dummit and Foote notes, Wikipedia, and Socratica. All you need to know for the purpose of this article, for the fields we will be working with, $\mathbb{F}_p$ is a number system that works exactly like clock arithmetic, but on a clock with $p$ hours. You can do all your familiar operations you know and love, just mod by $p$ in the end. Division is a little trickier, since you’ll have to use the Extended Euclidean Algorithm, or you can trust my math here.

Now that Alice encoded her message as a polynomial, she will pick an element uniformly random from the field, notated $r \xleftarrow{R} \mathbb{F}_{131}$, and evaluate it on the polynomial. For this example, say $r = 71$. So, Alice calculates

Alice then sends Bob the message $(p_{Alice}(r), r) = (24, 71)$. Now, Bob encodes his file contents as the polynomial $p_{Bob}$ in the same way that Alice did hers, and he also evaluates his polynomial on $r$. So, he checks $p_{Bob}(71) \stackrel{?}{\equiv} 24 \pmod{131}$. If so, he is convinced that with high probability (at least 96.9%) that they share the same file, otherwise he knows the file contents are different. We prove this property of the protocol shortly below. This confidence can also be made arbitrarily high!

Now, below, I will prove that if the file contents are the same and Alice is honest, meaning Alice may not deviate from the protocol to convince Bob otherwise, then Bob is convinced that the files are the same with probability 1. I will also prove that if the file contents are not the same and Alice is honest, then Bob will be falsely convinced the files are the same with probability $< 1/n$. In other words, the probability that Bob is convinced of the contrary decreases linearly with the size of the file contents. Both properties have technical terms in probabilistic proof systems, where the first property is called completeness and the second is called soundness. Completeness is usually trivial, while soundness is not.

Running Time Complexity Improvements

Now, I’ll describe how randomness can improve the running time performance of algorithms. Imagine this new scenario. Some salesman comes to your door and is selling you a black box which will spit out the result of two $n \times n$ matrices multiplied together in $O(1)$ time! Now, the naive time complexity of multiplying two $n \times n$ matrices is $O(n^3)$ with your normal matrix multiplication you would learn in a linear algebra class. A popular improvement used today is called Strassen’s algorithm, which runs in $O(n^{\log_2 7 + o(1)}) \approx O(n^{2.8074})$ time. The fastest known algorithm for multiplying two $n \times n$ matrices currently runs in time $O(n^{2.371339})$, however it isn’t very useful unless the matrices are incredibly large.

This would be an incredibly useful tool to have to quickly satisfy all your square matrix multiplication needs! But, you don’t really trust what the salesman says and what he claims the product to do. You also don’t want to spend a lot of time checking if it did the calculation right, which would require running one of those algorithms above, and at that point there would be no point in buying the box. However, luckily we can use randomness to be highly convinced of the correctness of the answer in $O(n^2)$ time!

Now, from a bird’s eye view, how does this algorithm work? Imagine you have two matrices $A,B \in \mathbb{F}_p^{n \times n}$ and you throw them into this machine, which returns the supposed result $C \in \mathbb{F}_p^{n \times n}$. Now, we don’t want to check if $C \stackrel{?}{=} A \cdot B$ since, again, we would need to use one of the algorithms above, which is too slow. Instead, what if we choose $r \xleftarrow{R} \mathbb{F}_p$ and multiply both sides of the equation by the column vector $x = (1, r, r^2, \dots, r^{n-1})$ so that we now check if $C \cdot x \stackrel{?}{=} (A \cdot B) \cdot x$? Well, now we still have a matrix multiplication, which is slow, but we are definitely getting somewhere because matrix multiplication is associative! So, we can check if $C \cdot x \stackrel{?}{=} A \cdot (B \cdot x)$ without the slow matrix multiplication.

This algorithm is a variation of Freivalds’ algorithm, runs in time $O(n^2)$, and can verify the matrix product with a probability of failure $\leq (n-1)/p$. This is a variation on the original because the original algorithm chooses $x \xleftarrow{R} \{0,1\}^n$, which still runs in time $O(n^2)$, but has an error probability of $\leq 1/2$. You can see that we get a tradeoff where choosing $p$ much larger than $n$ gives us better confidence in our verification, at the cost of using randomness from a larger field. I chose to show the variation of Freivalds’ algorithm because its analysis is actually easier, especially given the proof we already established in the section above.

Space Complexity Improvements

Lastly, we are going to look at an example where access to randomness can save us space. The problem we are going to look at is called the undirected $s$-$t$ connectivity (USTCON) problem. Given an undirected graph $G$ and two vertices $s$ and $t$ in $G$, we must decide whether $s$ and $t$ are in the same component, that is that there is a path going from one to the other. This may seem like an esoteric example, but there are actually many real-world examples where this is useful. We could imagine that Google Maps stores all of the roads as a graph where the vertices are intersections and the roads going in and out of intersections are edges. So, we could see Google Maps being able to answer the question “Can you get from intersection $x$ to intersection $y$”?

How might we solve this problem if we wanted to be 100% sure of its connectivity? Well, the easiest way might be to do a depth-first search starting from $s$. The space complexity of this solution is $O(n)$ and the time complexity is $O(n + m)$, where $n$ and $m$ are the number of vertices and edges in the graph, respectively, since it has to keep track of where it has been and possibly traverse the whole graph. As with our previous examples, if we use randomness and we allow ourselves a probability of outputting the incorrect solution, we can find improvements in space complexity.

Now, what if we just walk around the graph randomly? This could greatly reduce our space because all we need to do is keep track of the current vertex we are on, which only takes $O(\log_2 n)$ space with a numbering scheme of the vertices. But, we don’t want to be walking forever because it may be the case that $s$ and $t$ are not connected. So, how long might we want to be randomly walking for in order to be highly confident in outputting $\texttt{NOT-CONNECTED}$ if we have not seen $t$? Luckily for us the study of Markov Chains gives us some terminology and prior results to solve this question.

The hitting time between vertices $u$ and $v$, denoted $h_{uv}$, is the expected number of steps in a random walk that starts at $u$ and ends upon first reaching $v$. The commute time between vertices $u$ and $v$, denoted $C_{uv}$, is the expected number of steps in a random walk that starts at $u$, reaches $v$, and returns to $u$. Clearly, $h_{uv} < C_{uv}$ when $u \neq v$. I will prove that if we walk for $2n^3$ steps and $s$ and $t$ are connected, we will output $\texttt{CONNECTED}$ with probability $\geq 1/2$. The following corollary is useful to us, but will not be proved, as it is out of the scope of the blog post. See Chapter 6 of the Motwani and Raghavan book for details [4].

So, notice that we have given ourselves a trade-off. The depth-first search solution was able to output an always correct answer in time $O(n + m)$, which is $O(n^2)$ in the densest case, while the randomized walk algorithm runs in time $O(n^3)$, with a probability of outputting a correct answer. However, as noted previously, we do not need to store all previously visited vertices in the randomized algorithm, just the current vertex and a step counter, which gives us a greatly improved space complexity of $O(\log_2 n)$.

There is one important modern caveat here. This random-walk algorithm is a simple and historically important way to see how randomness can reduce space, but it is not the final word on USTCON. Omer Reingold later proved that undirected $s$-$t$ connectivity can be solved deterministically in logarithmic space. So, randomness is not necessary for the best-known space bound here, but it remains the most approachable route to the idea.