A new bridge connects the strange mathematics 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 just two colors must be incredibly inefficient, but it is possible to find a very efficient local algorithm if you are allowed to use three.

At the conference Bernshteyn attended, the speaker discussed these thresholds for different types of problems. One of the thresholds, he realized, was a lot like a threshold that existed in the world of descriptive set theory, namely the number of colors required to color certain infinite graphs in a measurable way.

For Bernshteyn, it was more than a coincidence. Computer scientists are not just like librarians, setting aside problems based on the effectiveness of their algorithms. These problems couldn’t just be written in terms of graphics and coloring.

Perhaps, he thought, the two shelves had more in common than that. Perhaps the connection between these two areas was much deeper.

Maybe all the books and their shelves were the same, just written in different languages ​​and needed a translator.

Open the door

Bernshteyn set out to make this connection explicit. He wanted to show that any efficient local algorithm can be transformed into a Lebesgue-measurable way of coloring an infinite graph (which satisfies some important additional properties). That is, 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 started with the network problems course in computer science class, focusing on their general rule: A given node’s algorithm uses information only about its local neighborhood, whether the graph has a thousand 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 that it can record information about nearby nodes and give instructions about them. This is quite simple to do in a finite graph: just give each node in the graph a different number.