AF: Small: Communication and 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.