AF: Small: Communication and Resource Tradeoffs

University Of Washington, Seattle WA

Investigators

Abstract

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.