AF: EAGER: The Power of Isolation in Computing

AF：EAGER：计算中隔离的力量

• 批准号: 1838434
• 负责人: Dieter van Melkebeek
• 金额: $ 12.5万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2021-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1838434&HistoricalAwards=false
• 关键词: AF; EAGER; Power; Isolation; Computing

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.

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

项目成果

Polynomial Identity Testing via Evaluation of Rational Functions

• DOI: 10.4230/lipics.itcs.2022.119
• 发表时间: 2022-11
• 期刊: ArXiv
• 作者: D. Melkebeek;Andrew Morgan

Minimum Circuit Size, Graph Isomorphism, and Related Problems

最小电路尺寸、图同构及相关问题

• DOI: 10.1137/17m1157970
• 发表时间: 2018
• 期刊: SIAM Journal on Computing
• 影响因子: 1.6
• 作者: Allender, Eric;Grochow, Joshua A.;van Melkebeek, Dieter;Moore, Cristopher;Morgan, Andrew
• 通讯作者: Morgan, Andrew

Derandomizing Isolation in Space-Bounded Settings

空间有限环境中的去随机化隔离

• DOI: 10.1137/17m1130538
• 发表时间: 2019
• 期刊: SIAM Journal on Computing
• 影响因子: 1.6
• 作者: van Melkebeek, Dieter;Prakriya, Gautam
• 通讯作者: Prakriya, Gautam