CAREER: Developing a unified theory of descriptive combinatorics and local algorithms

This project brings together two scientific fields: distributed computing and descriptive set theory. Distributed computing is the area of computer science that studies distributed systems, i.e., decentralized networks of computers that communicate with each other by passing messages. Distributed computing is especially relevant in the modern era of large networks, such as the Internet, where millions of machines are interconnected. On the other hand, descriptive set theory investigates the structure of subsets of the real line and other well-behaved spaces. It is used to understand the complexity of various sets defined by mathematical formulas and to classify them according to their complexity. Surprisingly, it turns out that these two areas are closely related, and that ideas and results from one can often be applied in the other. As this relationship has only recently been discovered, it is still poorly understood. This project will explore it in depth with the ultimate aim of developing a unified theory that integrates the two subjects. The educational component of this project is focused on creating opportunities for junior researchers to enter this rapidly developing field. Specifically, it will support training of graduate students and designing a suite of materials (textbooks and lecture notes, instructional videos, workshops, and courses) aimed at students and scholars with background in combinatorics or computer science but no prior exposure to descriptive set theory. Known interactions between descriptive combinatorics and distributed computing take place in the framework of locally checkable labeling (LCL) problems, where the objective is to assign labels to the vertices of a given graph subject to some "local" constraints. Part of the project is to investigate the following general question: Given an LCL problem that can be solved with some degree of regularity (e.g., Borel, measurable, etc.) on Borel graphs, when can we find an efficient algorithm for this problem in some model of distributed computation? Currently, the answer is only known in a few special cases, and this project aims to extend it to a much wider context. Another goal of this project is to develop an effective classification of the complexity of LCL problems from the perspective of descriptive set theory and distributed computing, or to prove that such classification is impossible. Thirdly, this project will study specific problems of particular interest, such as graph coloring and perfect matchings. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.