Understanding complexity through function composition

点击翻译按钮获取中文摘要

Fundamental problems about the nature of efficient computation are of immense theoretical, philosophical and practical importance. However, despite their immense importance, the progress has been slow due to meta-mathematical barriers which rule out most approaches. Of a handful that remains, an approach based on fundamental connections between computation and communication has seen promising developments recently. In this proposal, we focus on the following fundamental questions that remain wide open: 1. Are there tasks for which parallel computing does not offer (exponential) speedup? 2. Can we translate computational hardness from weak models of computation to hardness in stronger models? These questions are tightly related to the complexity of a basic operation known as function composition. Function composition abstracts a common strategy in computing: Given a complex task 1) divide the tasks into sub-tasks, 2) solve them, 3) and then combine the results of the sub-tasks to produce the result for the original task. The natural question is, when is this strategy optimal? Answering this question in the model of parallel algorithms and communication protocols would answer the two fundamental questions listed above. Studying function composition in various computational models, including parallel algorithms and communication protocols, is tightly related to the communication complexity of relations (a strict generalization of functions). Unfortunately, most tools and techniques from communication complexity are made for functions and fail to work for relations. Thus, we propose a systematic study of the communication complexity of relations guided by the fundamental questions above. We will use tools and techniques from various areas of computer science like communication complexity, information theory, lifting theorems, quantum computation, circuit complexity, analysis of Boolean functions, pseudo-randomness, and combinatorics. Function composition is fundamental in diverse computational settings like neural networks, quantum circuits, parallel algorithms, cryptographic primitives. More importantly, the best algorithms for many important problems are built using this operation alone in many settings. Thus, the long-term goal of this research direction of understanding the complexity function composition results in breakthrough insights about the powers and limitations of these models. The long-term goals of this proposal will result in significant breakthroughs in theoretical computer science. Even partial progress on the goals (both long-term and short-term) would imply new and important results in many areas like proof complexity, quantum communication, and combinatorial optimization. Because of the ubiquitous nature of function composition, the tools and techniques we develop would also help in many other areas of computer science. Moreover, the training HQP receive will have broad applications in industry and academia.