Computer scientists aim to determine how many steps a certain algorithm takes to solve a problem. For instance, a local algorithm that addresses the router problem using only two colors is likely to be highly inefficient. However, if you’re allowed to use three colors, a much more efficient local algorithm can be developed. During a talk Bernshteyn attended, the speaker delved into these thresholds for various types of problems. One threshold discussed was reminiscent of a concept in descriptive set theory regarding the number of colors needed to color certain infinite graphs in a measurable way.
To Bernshteyn, this seemed more than coincidental. It wasn’t just that computer scientists resemble librarians, organizing problems according to the efficiency of their algorithms, or that these problems could also be framed in terms of graphs and colorings. He began to think that these two fields might share a deeper connection. Perhaps all the books—and their shelves—were fundamentally the same, merely expressed in different languages, and in need of a translator.
Opening the Door
Bernshteyn set out to clarify this connection. He aimed to demonstrate that every efficient local algorithm could be transformed into a Lebesgue-measurable method for coloring an infinite graph (which meets certain additional important criteria). Essentially, one of the key categories in computer science is equivalent to one of the fundamental categories in set theory (high up in its hierarchy).
He concentrated on the class of network problems discussed in the computer science lecture, focusing on their key principle—that any algorithm for a given node relies solely on information from its local neighborhood, regardless of whether the graph comprises a thousand nodes or a billion. To function effectively, the algorithm only needs to assign a unique number to each node in that local neighborhood, allowing it to gather information about nearby nodes and provide instructions. This process is straightforward in a finite graph: simply give every node a different number.
