A new bridge connects the exotic mathematics of Infinity with computer science

Computer scientists want to know how many steps a particular algorithm requires. For example, any local algorithm that can solve the router problem using only two colors must be incredibly inefficient, but it is possible to find a local algorithm that is extremely efficient if you are allowed to use three colors.

At the talk Bernstein was attending, the speaker discussed these thresholds for different types of problems. He realized that one threshold looked like the threshold found in the world of descriptive set theory—about the number of colors required to color some infinite graphs in a measurable way.

To Bernstein, it seemed like more than just a coincidence. It’s not just that computer scientists are like librarians either, shelving problems based on how well their algorithms work. It was not just that these problems could be written in terms of graphs and colours.

Perhaps he thought the two bookshelves had more in common than that. The relationship between these two areas was probably much deeper.

Perhaps all the books and their shelves were identical, written in different languages, and needed a translator.

Open the door

Bernstein set out to make this connection explicit. He wanted to show that every efficient local algorithm can be transformed into a measurable way by Lebesgue to color an infinite graph (satisfying some additional important properties). This means that one of the most important shelves in computer science is equivalent to one of the most important shelves in set theory (at the top of the hierarchy).

He began by separating network problems from a computer science lecture, focusing on their universal rule—that any given node’s algorithm uses information only about its local neighborhood, whether the graph contains a thousand nodes or a billion nodes.

To work properly, all the algorithm has to do is label each node in a given neighborhood with a unique number, so it can record information about nearby nodes and give instructions about them. This is easy to do in a finite graph: just give each node in the graph a different number.