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 的法定使命，并被认为值得通过以下方式获得支持：使用基金会的智力价值和更广泛的影响审查标准进行评估。

项目成果

期刊论文数量（3）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Minimum Circuit Size, Graph Isomorphism, and Related Problems

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

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

Polynomial Identity Testing via Evaluation of Rational Functions

通过有理函数的评估进行多项式恒等性测试