(This is a continuation of a previous post.)
We begin by building up some of the canonical technology of expander graphs. Morally, we can think of an expander graph as a building block characterized paradoxically by connectivity and sparseness, out of which we can construct families of increasingly larger graphs increasing in the number of vertices but barely growing in degree, i.e. by taking some combination of graph powers, tensor products, zigzag products, etc. Here are a few measures of the connectivity characteristic of expander graphs:
Definition 1 (vertex expansion): A directed multigraph (the word “graph” will be used to denote these from now on unless otherwise stated) is a -vertex expander if all sets of at most vertices have at least neighbors. In other words, all small enough collections of vertices are well connected to the entire graph.
Definition 2 (spectral expansion): A regular graph is a -spectral expander if the spectral gap of its Laplacian is at least . Morally, the algebraic “mixing” of is sufficiently fast.
Definition 3 (edge expansion): For subsets of the vertices of a graph , let denote the cut size between and , i.e. the number of directed edges from vertices in to vertices in . A -regular graph is a -edge expander if for all such that .
In other words, all small enough collections of vertices have lots of edges emanating from them. It turns out that these three criteria for expansion are closely related (the following results aren’t immediately relevant to error reduction, but as a newbie learning about expander graphs for the first time, I think they form a neat connection between the algebraic and the combinatorial).
The following series of posts will document things that I’ve learned from a neat survey on pseudorandomness by Prof. Salil Vadhan at Harvard. They’re mostly to help me digest the material, but I hope they’ll be of interest to anyone reading this blog.
Specifically, this first set of two posts will be about the power of expander graphs in randomness-efficient error reduction in randomized algorithms; this first post will present two naive approaches to error reduction. We begin with the following definition.
Definition 1: A language lies in class BPP (bounded-error probabilistic polynomial-time) if there exists a probabilistic polynomial-time algorithm such that the probability that accepts an element x is if and is if , where is some polynomial in the length of the input. Stated another way, BPP is the class of languages with probabilistic polynomial-time algorithms with two-sided error at most .
Intuitively, taking multiple repetitions should push the error in any such arbitrarily low, thanks to the following standard result from probability theory:
Result 1 ((A) Chernoff Bound): Let be independent random variables from . Let be their average , and let be the expected value of . Then , that is, the probability of the average differing from its expected value by some quantity falls exponentially in the number of repetitions .
For an algorithm with error at most , consider the corresponding algorithm which runs for repetitions. Let be the average of the indicator variables which each take on a value of 1 if the algorithm outputs the right answer on the th repetition and 0 otherwise. By the Chernoff bound above for , we get that . Taking to be , we get that the probability is bounded above by as long as is large enough. Here, reducing error to comes at a cost of k repetitions and, if our algorithm requires random bits, requires random bits, because our repetitions are completely independent.