Solving Infinite Problems: Anton Bernshteyn awarded NSF CAREER grant for developing a new, unified theory of descriptive combinatorics and distributed algorithms

Anton Bernshteyn is forging connections and creating a language to help computer scientists and mathematicians collaborate on new problems — in particular, bridging the gap between solvable, finite problems and more challenging, infinite problems. Now, an NSF CAREER grant will help him achieve that goal.

The National Science Foundation Faculty Early Career Development Award is a five-year grant designed to help promising researchers establish a foundation for a lifetime of leadership in their field. Known as CAREER awards, the grants are NSF’s most prestigious funding for untenured assistant professors.

Bernshteyn, an assistant professor in the School of Mathematics, will focus on “Developing a unified theory of descriptive combinatorics and local algorithms” — connecting concepts and work being done in two previously separate mathematical and computer science fields. “Surprisingly,” Bernshteyn says, “it turns out that these two areas are closely related, and that ideas and results from one can often be applied in the other.” 

“This relationship is going to benefit both areas tremendously,” Bernshteyn says. “It significantly increases the number of tools we can use”

By pioneering this connection, Bernshteyn hopes to connect techniques that mathematicians use to study infinite structures (like dynamic, continuously evolving  structures found in nature), with the algorithms computer scientists use to model large – but still limited – interconnected networks and systems (like a network of computers or cell phones).

“The final goal, for certain types of problems,” he continues, “is to take all these questions about complicated infinite objects and translate them into questions about finite structures, which are much easier to work with and have applications in practical large-scale computing.”

Creating a unified theory

It all started with a paper Bernshteyn wrote in 2020, which showed that mathematics and computer science could be used in tandem to develop powerful problem-solving techniques. Since the fields used different terminology, however, it soon became clear that a “dictionary” or a unified theory would need to be created to help specialists communicate and collaborate. Now that dictionary is being built, bringing together two previously-distinct fields: distributed computing (a field of computer science), and descriptive set theory (a field of mathematics). 

Computer scientists use distributed computing to study so-called “distributed systems,” which model extremely large networks — like the Internet — that involve millions of interconnected machines that are operating independently (for example, blockchain, social networks, streaming services, and cloud computing systems).

“Crucially, these systems are decentralized,” Bernshteyn says. ”Although parts of the network can communicate with each other, each of them has limited information about the network’s overall structure and must make decisions based only on this limited information.” Distributed systems allow researchers to develop strategies — called distributed algorithms — that “enable solving difficult problems with as little knowledge of the structure of the entire network as possible,” he adds.

At first, distributed algorithms appear entirely unrelated to the other area Bernshteyn’s work brings together: descriptive set theory, an area of pure mathematics concerned with infinite sets defined by “simple” mathematical formulas. 

“Sets that do not have such simple definitions typically have properties that make them unsuitable for applications in other areas of mathematics. For example, they are often non-measurable – meaning that it is impossible, even in principle, to determine their length, area, or volume," Bernshteyn says.

Because undefinable sets are difficult to work with, descriptive set theory aims to understand which problems have “definable”— and therefore more widely applicable— solutions. Recently, a new subfield called descriptive combinatorics has emerged. “Descriptive combinatorics focuses specifically on problems inspired by the ways collections of discrete, individual objects can be organized,” Bernshteyn explains. “Although the field is quite young, it has already found a number of exciting applications in other areas of math.”

The key connection? Since the algorithms used by computer scientists in distributed computing are designed to perform well on extremely large networks, they can also be used by mathematicians interested in infinite problems.

Solving infinite problems

Infinite problems often occur in nature, and the field of descriptive combinatorics has been particularly successful in helping to understand dynamical systems: structures that evolve with time according to specified laws (such as the flow of water in a river or the movement of planets in the Solar System). “Most mathematicians work with continuous, infinite objects, and hence they may benefit from the insight contributed by descriptive set theory,” Bernshteyn adds.

However, while infinite problems are common, they are also notoriously difficult to solve. “In infinite problems, there is no software that can tell you if the problem is solvable or not. There are infinitely many things to try, so it is impossible to test all of them. But if we can make our problems finite, we can sometimes determine which ones can and cannot be solved efficiently,” Bernshteyn says. “We may be able to determine which combinatorial problems can be solved in the infinite setting and get an explicit solution.”

“It turns out that, with some work, it is possible to implement the algorithms used in distributed computing on infinite networks, providing definable solutions to various combinatorial problems,” Bernshteyn says. “Conversely, in certain limited settings it is possible to translate definable solutions to problems on infinite structures into efficient distributed algorithms — although this part of the story is yet to be fully understood.”

A new frontier

As a recently emerged field, descriptive combinatorics is rapidly evolving, putting Bernshteyn and his research on the cutting edge of discovery. “There’s this new communication between separate fields of math and computer science—this huge synergy right now—it’s incredibly exciting,” Bernshteyn says.

Introducing new researchers to descriptive combinatorics, especially graduate students, is another priority for Bernshteyn. His CAREER grant funds will be especially dedicated to training graduate students who might not have had prior exposure to descriptive set theory. Bernshteyn also aims to design a suite of materials ranging from textbooks, lecture notes, instructional videos, workshops, and courses to support students and scholars as they enter this new field.

“There’s so much knowledge that’s been acquired,” Bernshteyn says. “There’s work being done by people within computer science, set theory, and so on. But researchers in these fields speak different languages, so to say, and a lot of effort needs to go into creating a way for them to understand each other. Unifying these fields will ultimately allow us to understand them all much better than we did before. Right now we’re only starting to glimpse what’s possible.”