Author: Michael Nielsen

Note: This post is one in a series introducing one of the deepest ideas in modern computer science, expander graphs. Expanders are one of those powerful ideas that crop up in many apparently unrelated contexts, and that have a phenomenally wide range of uses. The goal of the posts is to explain what an expander is, and to learn just enough about them that we can start to understand some of their amazing uses. The posts require a little background in graph theory, computer science, linear algebra and Markov chains (all at about the level of a first course) to be comprehensible. I am not an expert on expanders, and the posts are just an introduction. They are are mostly based on some very nice 2003 lecture notes by Nati Linial and Avi Wigderson, available on the web at http://www.math.ias.edu/~boaz/ExpanderCourse/.

Introduction to expanders

Expander graphs are one of the deepest tools of theoretical computer science and discrete mathematics, popping up in all sorts of contexts since their introduction in the 1970s. Here’s a list of some of the things that expander graphs can be used to do. Don’t worry if not all the items on the list make sense: the main thing to take away is the sheer range of areas in which expanders can be applied.

• Reduce the need for randomness: That is, expanders can be used to reduce the number of random bits needed to make a probabilistic algorithm work with some desired probability.
• Find good error-correcting codes: Expanders can be used to construct error-correcting codes for protecting information against noise. Most astonishingly for information theorists, expanders can be used to find error-correcting codes which are efficiently encodable and decodable, with a non-zero rate of transmission. This is astonishing because finding codes with these properties was one of the holy grails of coding theory for decades after Shannon’s pioneering work on coding and information theory back in the 1940s.
• A new proof of PCP: One of the deepest results in computer science is the PCP theorem, which tells us that for all languages [tex]L[/tex] in NP there is a randomized polyonomial-time proof verifier which need only check a constant number of bits in a purported proof that [tex]x \in L[/tex] or [tex]x \not \in L[/tex], in order to determine (with high probability of success) whether the proof is correct or not. This result, originally established in the earlier 1990s, has recently been given a new proof based on expanders.

What’s remarkable is that none of the topics on this list appear to be related, a priori, to any of the other topics, nor do they appear to be related to graph theory. Expander graphs are one of these powerful unifying tools, surprisingly common in science, that can be used to gain insight into an an astonishing range of apparently disparate phenomena.

I’m not an expert on expanders. I’m writing these notes to help myself (and hopefully others) to understand a little bit about expanders and how they can be applied. I’m not learning about expanders with any specific intended application in mind, but rather because they seem to behind some of the deepest insights we’ve had in recent years into information and computation.

What is an expander graph? Informally, it’s a graph [tex]G = (V,E)[/tex] in which every subset [tex]S[/tex] of vertices expands quickly, in the sense that it is connected to many vertices in the set [tex]\overline S[/tex] of complementary vertices. Making this definition precise is the main goal of the remainder of this post.

Suppose [tex]G = (V,E)[/tex] has [tex]n[/tex] vertices. For a subset [tex]S[/tex] of [tex]V[/tex] we define the edge boundary of [tex]S[/tex], [tex]\partial S[/tex], to be the set of edges connecting [tex]S[/tex] to its complement, [tex]\overline S[/tex]. That is, [tex]\partial S[/tex] consists of all those edges [tex](v,w)[/tex] such that [tex]v \in S[/tex] and [tex]w \not \in S[/tex]. The expansion parameter for [tex]G[/tex] is defined by

[tex] h(G) \equiv \min_{S: |S| \leq n/2} \frac{|\partial S|}{|S|}, [/tex]

where [tex]|X |[/tex] denotes the size of a set [tex]X[/tex].

One standard condition to impose on expander graphs is that they be [tex]d[/tex]-regular graphs, for some constant [tex]d[/tex], i.e., they are graphs in which every vertex has the same degree, [tex]d[/tex]. I must admit that I’m not entirely sure why this [tex]d[/tex]-regularity condition is imposed. One possible reason is that doing this simplifies a remarkable result which we’ll discuss later, relating the expansion parameter [tex]h(G)[/tex] to the eigenvalues of the adjacency matrix of [tex]G[/tex]. (If you don’t know what the adjacency matrix is, we’ll give a definition later.)

Example: Suppose [tex]G[/tex] is the complete graph on [tex]n[/tex] vertices, i.e., the graph in which every vertex is connected to every other vertex. Then for any vertex in [tex]S[/tex], each vertex in [tex]S[/tex] is connected to all the vertices in [tex]\overline S[/tex], and thus [tex]|\partial S| = |S| \times |\overline S| = |S|(n-|S|)[/tex]. It follows that the expansion parameter is given by

[tex] h(G) = \min_{S: |S|\leq n/2} n-|S| = \left\lceil \frac{n}{2} \right\rceil. [/tex]

For reasons I don’t entirely understand, computer scientists are most interested in the case when the degree, [tex]d[/tex], is a small constant, like [tex]d = 2,3[/tex] or [tex]4[/tex], not [tex]d=n-1[/tex], as is the case for the complete graph. Here’s an example with constant degree.

Example: Suppose [tex]G[/tex] is an [tex]n \times n[/tex] square lattice in [tex]2[/tex] dimensions, with periodic boundary conditions (so as to make the graph [tex]4[/tex]-regular). Then if we consider a large connected subset of the vertices, [tex]S[/tex], it ought to be plausible that that the edge boundary set [tex]\partial S[/tex] contains roughly one edge for each vertex on the perimeter of the region [tex]S[/tex]. We expect there to be roughly [tex]\sqrt{|S|}[/tex] such vertices, since we are in two dimensions, and so [tex]|\partial S|/|S| \approx 1/\sqrt{|S|}[/tex]. Since the graph can contain regions [tex]S[/tex] with up to [tex]O(n^2)[/tex] vertices, we expect

[tex] h(G) = O\left( \frac{1}{n} \right) [/tex]

for this graph. I do not know the exact result, but am confident that this expression is correct, up to constant factors and higher-order corrections. It’d be a good exercise to figure out exactly what [tex]h(G)[/tex] is. Note that as the lattice size is increased, the expansion parameter decreases, tending toward [tex]0[/tex] as [tex]n\rightarrow \infty[/tex].

Example: Consider a random [tex]d[/tex]-regular graph, in which each of [tex]n[/tex] vertices is connected to [tex]d[/tex] other vertices, chosen at random. Let [tex]S[/tex] be a subset of at most [tex]n/2[/tex] vertices. Then a typical vertex in [tex]S[/tex] will be connected to roughly [tex]d \times |\overline S|/n[/tex] vertices in [tex]\overline S[/tex], and thus we expect [tex]|\partial S| \approx d \times |S| |\overline S|/n[/tex], and so

[tex] \frac{|\partial S|}{|S|} \approx d \frac{|\overline S|}{n}. [/tex]

Since [tex]|\overline S|[/tex] has its minimum at approximately [tex]n/2[/tex] it follows that [tex]h(G) \approx d/ 2[/tex], independent of the size [tex]n[/tex].

Exercise: Show that a disconnected graph always has expansion parameter [tex]0[/tex].

In each of our examples, we haven’t constructed just a single graph, but rather an entire family of graphs, indexed by some parameter [tex]n[/tex], with the property that as [tex]n[/tex] gets larger, so too does the number of vertices in the graph. Having access to an entire family in this way turns out to be much more useful than having just a single graph, a fact which motivates the definition of expander graphs, which we now give.

Suppose we have a family [tex]G_j = (V_j,E_j)[/tex] of [tex]d[/tex]-regular graphs, indexed by [tex]j[/tex], and such that [tex]|V_j| = n_j[/tex] for some increasing function [tex]n_j[/tex]. Then we say that the family [tex]\{ G_j \}[/tex] is a family of expander graphs if the expansion parameter is bounded strictly away from [tex]0[/tex], i.e., there is some small constant [tex]c[/tex] such that [tex]h(G_j) \geq c > 0[/tex] for all [tex]G_j[/tex] in the family. We’ll often abuse nomenclature slightly, and just refer to the expander [tex]\{ G_j \}[/tex], or even just [tex]G[/tex], omitting explicit mention of the entire family of graphs.

In this post we’ve defined expanders, said a little about what they’re useful for, and given an example – [tex]d[/tex]-regular random graphs – of an expander. In the next post, I’ll describe some more explicit and much more useful examples of expander graphs.

Over the next few weeks I’m going to try out an experimental blogging style, posting a series of rather more technical expository notes than has been my wont in the past.

I’m going to try to keep the tone light, but inevitably these posts will be more technical and demanding than most – though not all – of what I’ve posted in the past. I’ll also continue to post less technical stuff.

I expect it’ll take me a little while to settle into a style that works well. I’m aiming to keep things light and personal, but must admit that after drafting material for the past couple of weeks, I’m finding this more difficult than I imagined it would be.

I don’t think this difficulty is because it’s intrinsically especially difficult to do, but rather a reflection of habit: I’m most used to writing technical material – even expository material – in the impersonal manner common to journals. Getting out of that habit is going to take some work to get right. Feedback will help me figure out what works and what doesn’t, so keep the comments coming!

The initial topics will be: (1) a series on expander graphs, which are one of the most useful and beautiful tools in computer science, and (2) a series on Fermi algebras and the Jordan-Wigner transform, which are extremely useful tools in condensed matter physics.

These are, obviously, pretty specialized topics. I’ve tried to choose topics that are simultaneously: (1) subjects I wish to understand better; and (2) contain deep ideas of reasonably broad and current interest. I don’t expect that they’d be of much interest to, say, philosophers, but expect that the central ideas are of interest to a wide cross-section of physicists, mathematicians, and computer scientists. Furthermore, I’ll try focus on big ideas, and their relationship to the rest of science. Once again, learning to do this well is partially a question of style, and I expect I’ll get better at making these connections as I go along.

Depending on how things go, I may post further expository series in the future. I expect they’ll cover topics in some mixture of physics, computer science, mathematics, and self-development, with occasional digressions into other areas. I expect to range around a lot, through whatever interests me.

On a personal note, I’ve occasionally gotten queries from people about my blog, wondering if it “takes time away from your research”.

With this experiment I’m trying to integrate my blog more thoroughly with my research. Certainly, I find that writing expository notes like these is a good way of building up my own understanding of new subjects, and of preparing the way for new research projects. Indeed, I expect that some of these pieces will be useful warm-ups for some expository journal articles (and possibly books) that I hope to write in the future. I also feel very strongly about the value of synthesis and exposition for Science as a whole, especially the value of trying to explain things as simply as possible.

Finally, I must admit that I’m a little nervous about how this goes. These subjects are more specialized than much of what I’ve posted in the past, and I do enjoy having at least some regular readers! Here’s hoping I don’t drive you all away!

An email correspondent asks:

Is it valuable to have an “internal” blog area accessible only by members of your research group, for the sake of internal communication?

I’m about to set this up for my group, so I can’t give a definite yes or no from personal experience. I certainly think it’s worth trying, and I’ve heard from others who’ve tried it that it can be an effective way of helping keep people within a research group aware of what everyone else is doing. Wikis may also be useful for this purpose.

Aside from the warm feeling from having made a positive contribution to the community, has running a public blog been helpful to you?

I’ve spent quite a bit of time drafting and redfrafting responses to that. It was more difficult to answer than I expected, because while it seems like a simple question, it’s really a whole bundle of different questions. Blogging combines: (1) the discipline, clarity of thought, and creative impulse that comes from writing things down; (2) interaction with friends and colleagues; (3) interaction with a wider audience; (4) education and outreach; (5) publicity for one’s work, field, organization and profession; (6) the excitement of being part of a new medium, which is evolving quickly; (7) the opportunity to pontificate; (8) a bunch of other things that I’ve either forgotten or are ignorant of.

When you look at it this way, blogging combines a very wide range of activities, and all of these in some sense benefit various people (not always, but often, including me). So, yes, there is definitely a considerable benefit. Whether it is worth the time and effort is difficult to say. Personally, I think I’m only just now really figuring out how to blog in a way that I feel is effective, and fully justifies the investment of time.

My partner and I took up dancing recently (rhumba, waltz, jive, etc), and it’s been great fun. The music varies quite a bit, but never more so than in last night’s first choice of song, that well-known piece of music for progressive dance, AC/DC’s “Thunderstruck”.

My friend Ben Schumacher has started a blog, Zeroth order approximation. Actually, Ben started it a few months back, and has been merrily posting away, and I simply discovered his blog yesterday. This was great for me, because it meant I got to read several months of back posts.

Here’s a little sample:

But you know, so much of academic writing is bad. It is banal, orotund, unmusical, and stuffed with wads of unnecessary jargon. It is the sort of writing that does more to obscure meaning than to convey it. I see this stuff almost every day. I swim in it. OK, maybe I do exaggerate, a little. After all, I teach at a liberal arts college that is moderately well-known for teaching people how to write. Our faculty is full of novelists and poets and whatnot. But let me tell you, it’s here, too. It’s everywhere. It is like a fungus growing over all things, blurring their shapes — the verbal equivalent, maybe, of the ivy on academic buildings. And like the ivy, I guess, its main purpose is to conceal the shabby edifices beneath.

I live in fear that one day I will write ponderous, weedy, soporific academic prose. And worse, I fear that a day will come when I will simply not know the difference.

What’s the greatest single human artifact in the world?

At different points in history I think my answer would probably be objects like the Pyramids of Egypt, the Great Wall, the Suez Canal, or the Hoover Dam.

Nowadays, though, it’s not even an object, exactly. I can’t think of anything that tops the Google database.

One unanticipated effect of my move from Movable Type to WordPress was that the old RSS feed stopped working. There is a new feed at:

http://www.qinfo.org/people/nielsen/blog/wp-rss2.php

that seems to function correctly, at least so far as bloglines is concerned.

Comments or technical assistance from anyone who uses RSS would be very greatly appreciated! It’d be good to know if other people see the feed working properly, or not.