Two fields that seem to have nothing in common turn out to be studying the same problems. Descriptive set theory, a branch of mathematical logic that deals with the strange world of infinite sets, and distributed computing, the study of how networks of computers coordinate, are linked by a theorem from UCLA mathematician Anton Bernshteyn. His result shows that fast network algorithms can be translated directly into well behaved solutions of infinite coloring problems, and researchers have since used the bridge in both directions.
The two sides of the bridge
Distributed algorithms. Picture a huge network of routers or processors. Each node can talk only to its direct neighbors, and everyone works in synchronized rounds. In the standard model, introduced by computer scientist Nathan Linial, the only cost that counts is the number of rounds. A typical task is coloring: give every node a label, such as a radio frequency, so that no two neighbors share one. A local algorithm is efficient if each node can decide its color after looking only a few steps out into the network, even when the network has billions of nodes.
Descriptive set theory. Mathematicians in this field sort infinite sets by how complicated they are to describe. Borel sets, for example, can be built from simple intervals using countably many basic operations, while measurable sets are those you can assign a meaningful size. Strange objects that only exist thanks to the axiom of choice, which lets you make infinitely many arbitrary choices at once, sit outside these well behaved classes.
Where the coincidence showed up
Both fields care about coloring graphs, and both found the same kind of threshold. Consider a ring of computers. Coloring it with three colors is fast: there are classic local algorithms that finish in a number of rounds that grows so slowly with network size it is practically constant. Coloring the same ring with only two colors is hopeless locally, because a node must essentially see around the entire ring to know which color to take.
Now take an infinite graph built on a circle: connect each point to the point you reach by rotating it through a fixed irrational angle. Every connected piece is an endless chain, so in principle two colors suffice. But no measurable two coloring exists, while a well behaved Borel three coloring does. The jump from two to three colors appears in both worlds. Bernshteyn suspected this was not a coincidence but evidence that the two fields describe the same structures in different languages.
What Bernshteyn proved
His paper, titled Distributed Algorithms, the Lovász Local Lemma, and Descriptive Combinatorics, was first posted in April 2020 and published in 2023 in a leading mathematics journal. The core statement is short: efficient deterministic distributed algorithms produce Borel colorings, and efficient randomized algorithms produce measurable colorings. In technical terms, efficient means the number of rounds grows more slowly than the logarithm of the network size.
The main obstacle was identity. On a finite network, an algorithm can give every node a unique ID number so nodes can tell each other apart. On an infinite graph you cannot hand out distinct numbers in a well behaved way. The key insight is that a local algorithm never needs globally unique IDs. It only needs labels that are distinct within the small neighborhood each node inspects, and that kind of labeling can be done in a Borel way on graphs where every node has a bounded number of neighbors. With those local labels in place, the algorithm can be run on the infinite graph as if it were a finite network.
In the paper, Bernshteyn writes that his original motivation was to understand the Lovász Local Lemma, a probabilistic tool for showing that rare good outcomes exist. The paper proves measurable versions of that lemma, using recent distributed algorithms for it, and then uses them to handle randomized algorithms.
Fast local algorithms using ID numbers translate into Borel colorings.
Fast algorithms using random bits translate into measurable colorings.
A measurable version of a classic probability tool connects the two.
Traffic in both directions
The bridge quickly started carrying ideas both ways. In 2021, a team of six researchers, Sebastian Brandt, Yi Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhoň and Zoltán Vidnyánszky, studied local problems on regular trees from the distributed, probabilistic and descriptive viewpoints at once. They borrowed a technique from descriptive set theory, developed by mathematician Andrew Marks, to prove new lower bounds on how many rounds certain distributed problems require. They also showed that on these trees a problem has a Baire measurable solution exactly when it can be solved in a logarithmic number of rounds, while identifying cases where the different perspectives come apart.
In other words, a classification built by logicians to sort infinite sets now doubles as a map of how hard network problems are, and computer science arguments help settle questions about infinity.
Why it matters
For computer science, the link offers a new toolbox for proving that some network tasks cannot be done quickly. For mathematics, it turns decades of algorithm design into ready made constructions of well behaved colorings. The work has also brought recognition: Bernshteyn was named a 2025 Sloan Research Fellow, and he was invited to speak in the logic section of the International Congress of Mathematicians held in Philadelphia in July 2026.
FAQ
What is descriptive set theory?
It is a branch of mathematical logic that classifies sets, especially infinite sets of real numbers and similar spaces, by how complex they are to define.
What is a distributed algorithm?
An algorithm run by many connected processors at once, where each one only communicates with its neighbors. Its efficiency is measured by how many rounds of communication it needs.
Does this help build faster networks?
Not directly. The result is theoretical, but it gives researchers new ways to prove limits on what fast network algorithms can achieve.
Who is Anton Bernshteyn?
A mathematics professor at UCLA who works in descriptive set theory and combinatorics, with a focus on their connections to computer science and dynamical systems.
The verdict
Bernshteyn’s theorem shows that a question about infinite, abstract objects and a question about real computer networks are two versions of the same problem. Fast local algorithms become well behaved infinite colorings, and the hierarchy of set theory lines up with the hierarchy of algorithmic difficulty. Few results connect such distant fields so cleanly, which is why the bridge keeps attracting traffic.
Updated October 2026: rewritten as an explainer of the result, its follow up work and recent recognition, checked against the original paper and UCLA pages.
Featured photo: Erwan Hesry on Unsplash.
About this article: GeekBlog covers U.S. technology news, AI, phones, smartwatches and gaming. Every story is written and checked under our Editorial Policy. Spotted a mistake or have a story tip? Contact our editors.
