AF: Small: Communication and Resource Tradeoffs

AF：小：通信和资源权衡

• 批准号: 1524246
• 负责人: Paul Beame
• 金额: $ 40万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-08-15 至 2019-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1524246&HistoricalAwards=false
• 关键词: AF; Small; Communication; Resource; Tradeoffs

This project will focus on several problems in computational complexity involving tradeoffs among computational resources. These include an analysis of tradeoffs between the communication load, processors, and rounds of communication required to do data analysis on massively parallel systems, an analysis of tradeoffs between the computation time and memory (space) needed to analyze basic statistical properties of data, and an analysis of the role of nondeterminism versus determinism in tradeoffs between time and space. The project will also focus on counting problems for functions computed by simple classes of circuits.A large portion of computations today is being done on a massively parallel basis in cloud data centers. Though there are programming constructs that are convenient for using this computing power, there is only a limited understanding of the extent to which these constructs are using this parallel computing architecture efficiently. The project work on communication load for massively parallel systems focuses on developing a broad understanding of this question, ideally developing more efficient algorithms in the process. Efficient algorithms to use these data centers are critical since the energy requirements of data centers are an increasingly significant portion of the total use of the electric grid. The part of this project on finding tradeoffs between time and space required to solve computational problems involves advancing the fundamental understanding of how to use these resources most efficiently. It also will examine a special case involving time-bounded computation of an open question of much wider general interest in computational complexity: How much easier is it to check a proof of an answer to a problem than to determine whether that answer is yes or no? Finally, the portion of the project on the analysis of counting problems is motivated both by fundamental questions about what simple circuits can compute and by potential application to efficient reasoning about uncertain environments.

这个项目将专注于计算复杂性中的几个问题，涉及计算资源之间的权衡。其中包括在大规模并行系统上进行数据分析所需的通信负载、处理器和通信轮次之间的权衡分析，分析数据的基本统计属性所需的计算时间和内存(空间)之间的权衡，以及非确定性与确定性在时间和空间之间权衡中的作用的分析。该项目还将专注于计算由简单电路类别计算的函数的问题。目前，云数据中心的大部分计算都是在大规模并行的基础上进行的。尽管有一些编程构造可以方便地使用这种计算能力，但人们对这些构造有效地使用这种并行计算体系结构的程度了解有限。关于大规模并行系统的通信负载的项目工作集中在对这个问题的广泛理解上，理想的情况是在这个过程中开发更有效的算法。使用这些数据中心的高效算法至关重要，因为数据中心的能源需求在电网总使用量中所占的比例越来越大。这个项目关于寻找解决计算问题所需的时间和空间之间的权衡的部分涉及促进对如何最有效地使用这些资源的基本理解。它还将研究一个特殊情况，涉及对一个在计算复杂性中具有更广泛兴趣的公开问题的有限时间计算：检查一个问题的答案的证明比确定答案是或否容易多少？最后，分析计数问题的项目部分的动机既有关于什么简单电路可以计算的基本问题，也有潜在的关于不确定环境的有效推理的应用。

项目成果

Stabbing Planes

刺击飞机

• DOI: 10.48550/arxiv.1710.03219
• 发表时间: 2022
• 期刊: ArXivorg
• 作者: Beame, Paul;Fleming, Noah;Impagliazzo, Russell;Pankratov, Denis;Pitassi, Toniann;Robere, Robert
• 通讯作者: Robere, Robert