A New Bridge Links the Strange Math of Infinity to Computer Science

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 it’s possible to find a very efficient local algorithm if you’re allowed to use three.

At the talk Bernshteyn was attending, the speaker discussed these thresholds for different kinds of problems. One of the thresholds, he realized, sounded a lot like a threshold that existed in the world of descriptive set theory—about the number of colors required to color certain infinite graphs in a measurable way.

To Bernshteyn, it felt like more than a coincidence. It wasn’t just that computer scientists are like librarians too, shelving problems based on how efficiently their algorithms work. It wasn’t just that these problems could also be written in terms of graphs and colorings.

Perhaps, he thought, the two bookshelves had more in common than that. Perhaps the connection between these two fields went much, much deeper.

Perhaps all the books, and their shelves, were identical, just written in different languages—and in need of a translator.

Opening the Door

Bernshteyn set out to make this connection explicit. He wanted to show that every efficient local algorithm can be turned into a Lebesgue-measurable way of coloring an infinite graph (that satisfies some additional important properties). That is, one of computer science’s most important shelves is equivalent to one of set theory’s most important shelves (high up in the hierarchy).

He began with the class of network problems from the computer science lecture, focusing on their overarching rule—that any given node’s algorithm uses information about just its local neighborhood, whether the graph has a thousand nodes or a billion.

To run properly, all the algorithm has to do is 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. That’s easy enough to do in a finite graph: Just give every node in the graph a different number.