\n<\/p>\n
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\u2019s possible to find a very efficient local algorithm if you\u2019re allowed to use three.<\/p>\n
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\u2014about the number of colors required to color certain infinite graphs in a measurable way.<\/p>\n
To Bernshteyn, it felt like more than a coincidence. It wasn\u2019t just that computer scientists are like librarians too, shelving problems based on how efficiently their algorithms work. It wasn\u2019t just that these problems could also be written in terms of graphs and colorings.<\/p>\n
Perhaps, he thought, the two bookshelves had more in common than that. Perhaps the connection between these two fields went much, much deeper.<\/p>\n
Perhaps all the books, and their shelves, were identical, just written in different languages\u2014and in need of a translator.<\/p>\n
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\u2019s most important shelves is equivalent to one of set theory\u2019s most important shelves (high up in the hierarchy).<\/p>\n
He began with the class of network problems from the computer science lecture, focusing on their overarching rule\u2014that any given node\u2019s algorithm uses information about just its local neighborhood, whether the graph has a thousand nodes or a billion.<\/p>\n
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\u2019s easy enough to do in a finite graph: Just give every node in the graph a different number.<\/p>\n<\/div>\n