Computer scientists want to know how many steps a given algorithm requires. For example, any local algorithm that can solve the router problem with only two colors must be incredibly inefficient, but if you are allowed to use three colors it is possible to find a very efficient local algorithm.
At a talk Bernshtein was attending, the speaker discussed these limits for a variety of problems. A limit, he realized, sounds like a limit that exists in the world of descriptive set theory – about the number of colors needed to color some infinite graph in a measurable way.
To Bernshtein this seemed more than a coincidence. It’s not just that computer scientists are like librarians, they solve problems based on how efficiently their algorithms work. It was not as if these problems could even be written in terms of graphs and colors.
Perhaps, he thought, the two bookshelves had more in common than that. Perhaps the relationship between these two areas has become much deeper.
Perhaps all the books, and their shelves, were the same, just written in different languages – and required a translator.
open the door
Bernshtein attempted to clarify this relationship. He wanted to show that every efficient local algorithm can be transformed into a Lebesgue-measurable way of coloring an infinite graph (which satisfies some additional important properties). That is, one of the most important shelves of computer science is equivalent to one of the most important shelves (higher in the hierarchy) of set theory.
He started with a class on network problems from computer science lectures, focusing on his overarching rule – that an algorithm for any node uses only information about its local neighborhood, whether the graph has a thousand nodes or a billion.
To run properly, the algorithm simply needs to label each node in a given neighborhood with a unique number, so that it can log information about nearby nodes and give instructions about them. This is quite easy to do in a finite graph: simply give each node in the graph a different number.
<a href