AF: EAGER: The Power of Isolation in Computing

计算机科学和工程在构建高性能的软件和硬件系统方面取得了巨大的进步。硬件方面的进一步发展要求多个处理器并行处理同一任务。为了充分利用并行硬件，软件也需要并行化——它需要指定如何在不同的处理器之间分解任务。一个给定的问题可能有几个解决方案，这一事实经常使软件并行化复杂化。这是因为处理器之间没有太多的时间进行协调。如果没有协调，他们可能会朝着不同的、不相容的解决方案努力。隔离是一种确保所有处理器朝着相同解决方案工作的策略。它还具有广泛的其他算法用途。本项目侧重于隔离的力量，这是针对可能有许多解决方案的计算问题挑选出解决方案的过程。虽然本质上是基本的，旨在发展基础理论，但该项目可能会带来实际的改进，例如，涉及检测某些类型结构之间相似性的计算问题。研究生培训和教育是该项目的核心。该项目包括围绕隔离概念的几个重点：(1)对捕获各种计算模型的问题的已知隔离程序进行非随机化。已知的方法是基于隔离引理，它为解的组成部分分配小的随机权重，以使总权重最小的解唯一。该项目旨在减少所需的随机比特数，并最终在保持效率的同时完全消除对随机性的需求。(2)为研究充分的中间问题，即图和更具表达性的结构上的同构问题，开发确定性或随机隔离程序。这涉及到关于这些问题的许多已知的开放问题，包括与结构的测试刚度和寻找结构的规范形式的联系。(3)驳斥唯一对策猜想，这是一个与其他几个数学领域有联系的近似硬度领域的中心猜想。这个猜想表明，对于满足某种类似隔离属性的情况，近似所谓的标签覆盖游戏的策略的最优收益与一般情况一样困难。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Computer science and engineering have made great strides in building high-performing software and hardware systems. Further progress on the hardware front requires multiple processors to work in parallel on the same task. To make adequate use of the parallel hardware, the software needs to be parallelized as well - it needs to specify how to break up the task among the various processors. The fact that a given problem may have several solutions often complicates software parallelization. This is because the processors do not have much time to coordinate among themselves. Without coordination, they may be working towards different, incompatible solutions. Isolation is a strategy to ensure all processors work towards the same solution. It also has a wide range of other algorithmic uses. This project focuses on the power of isolation, which is the process of singling out a solution to a computational problem that may have many solutions. Though fundamental in nature and aimed at developing the underlying theory, the project may lead to practical improvements, e.g., for computational problems that involve detecting similarities between certain types of structures. Graduate training and education are core to the project. The project consists of several thrusts that center around the notion of isolation: (1) Derandomizing known isolation procedures for problems that capture various models of computation. Known procedures are based on the Isolation Lemma, which assigns small random weights to the components of a solution so as to make the solution of minimum total weight unique. The project aims to reduce the number of random bits needed and ultimately remove the need for randomness completely while maintaining efficiency. (2) Developing deterministic or randomized isolation procedures for well-studied intermediate problems, namely, isomorphism problems on graphs and more expressive structures. This relates to a number of known open questions regarding these problems, including the connection with testing rigidity of structures and with finding a canonical form for the structures. (3) Refuting the Unique Games Conjecture, a central conjecture in the area of hardness of approximation with ties to several other mathematical fields. The conjecture states that approximating the optimal yield of strategies for so-called label cover games is as hard for cases that satisfy a certain isolation-like property as it is in general.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.