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

职业：发展描述性组合学和局部算法的统一理论

• 批准号: 2239187
• 负责人: Anton Bernshteyn
• 金额: $ 50.03万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-07-01 至 2028-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2239187&HistoricalAwards=false
• 关键词: CAREER; Developing; unified; theory; descriptive

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.

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