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

该项目汇集了两个科学领域：分布式计算和描述集合论。分布式计算是研究分布式系统的计算机科学领域，即通过传递消息相互通信的分散的计算机网络。分布式计算在大型网络的现代时代尤其重要，例如互联网，其中数百万台机器相互连接。另一方面，描述集论研究实线和其他行为良好的空间的子集的结构。它用来理解由数学公式定义的各种集合的复杂性，并根据它们的复杂性对它们进行分类。令人惊讶的是，事实证明，这两个领域是密切相关的，一个领域的想法和结果往往可以应用于另一个领域。由于这种关系是最近才被发现的，人们对它的了解仍然很少。本项目将深入探讨这一问题，最终目的是开发一种整合这两个学科的统一理论。该项目的教育部分侧重于为初级研究人员创造进入这一快速发展领域的机会。具体地说，它将支持研究生的培训和设计一套材料(教科书和课堂讲稿、教学视频、研讨会和课程)，目标是具有组合学或计算机科学背景但事先没有接触过描述集合论的学生和学者。描述组合学和分布式计算之间的已知交互发生在局部可检查标记(LCL)问题的框架中，其中的目标是为给定的图的顶点分配标签，该问题受制于一些局部约束。项目的一部分是调查以下一般性问题：给定一个LCL问题，该问题可以用一定程度的正则性(例如，Borel，可测量等)来解决。在Borel图上，我们什么时候才能在一些分布式计算模型中找到解决这个问题的有效算法？目前，答案只在少数几个特殊情况下才知道，本项目旨在将其扩展到更广泛的背景下。本项目的另一个目标是从描述集合论和分布式计算的角度对LCL问题的复杂性进行有效的分类，或者证明这种分类是不可能的。第三，这个项目将研究特别感兴趣的具体问题，如图形着色和完美匹配。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.