Computer scientists want to know how many steps a given algorithm requires. For example, any local algorithm that can solve the router problem using only two colors must be extremely unskilled, but a very productive local algorithm can be found if it is allowed to exploit three.
During a lecture that Bernshteyn attended, the speaker discussed these thresholds for different types of problems. He realized that one of the thresholds sounded very similar to a threshold that existed in the world of descriptive set theory – it concerned the number of colors required to color certain infinite graphs in a measurable way.
To Bernshteyn this seemed more than a coincidence. It wasn’t just that computer scientists are also like librarians who shelve problems based on how efficiently their algorithms work. It wasn’t just that these problems could also be written down with graphs and coloring.
Perhaps, he thought, these two bookshelves have more in common. Perhaps the connection between the two fields ran much, much deeper.
Perhaps all the books and their shelves were identical, just written in different languages and needed a translator.
Opening the door
Bernshteyn decided to make this connection explicit. He wanted to show that any productive local algorithm could be transformed into a Lebesgue-measurable way of coloring an infinite graph (which satisfies several additional vital properties). This means that one of the most vital shelves of computer science is equivalent to one of the most vital shelves of set theory (high in the hierarchy).
He started with a class on network problems from a computer science class, focusing on their overarching principle – that any node’s algorithm uses information only about its local neighborhood, regardless of whether the graph has a thousand nodes or a billion.
For the algorithm to work properly, it only needs to tag each node in a given neighborhood with a unique number so that it can record information about nearby nodes and issue instructions about them. For a finite graph, this is quite basic: just give each node in the graph a different number.