Understanding complexity through function composition

关于有效计算本质的基本问题具有巨大的理论、哲学和实践意义。然而，尽管它们非常重要，但由于排除了大多数方法的元数学障碍，进展缓慢。在现存的少数几种方法中，一种基于计算和通信之间基本联系的方法最近出现了令人振奋的发展。在这个提议中，我们关注以下仍然悬而未决的基本问题：1.有没有并行计算不能提供(指数)加速比的任务？2.我们能否将计算难度从弱计算模型转换为更强模型中的计算难度？这些问题与一种称为函数合成的基本运算的复杂性密切相关。函数合成抽象了计算中的一种常见策略：给定一个复杂的任务：1)将任务划分为子任务，2)求解任务，3)合并子任务的结果，产生原始任务的结果。自然的问题是，这种策略在什么时候是最优的？在并行算法和通信协议模型中回答这个问题可以回答上面列出的两个基本问题。研究各种计算模型中的函数组合，包括并行算法和通信协议，与关系(函数的严格泛化)的通信复杂性密切相关。不幸的是，通信复杂性中的大多数工具和技术都是为函数而设计的，无法为关系工作。因此，我们建议在上述基本问题的指导下，对关系的沟通复杂性进行系统的研究。我们将使用计算机科学的各个领域的工具和技术，如通信复杂性、信息论、提升定理、量子计算、电路复杂性、布尔函数分析、伪随机性和组合学。在神经网络、量子电路、并行算法、密码原语等各种计算环境中，函数组合是基本的。更重要的是，许多重要问题的最佳算法都是在许多设置中仅使用此操作构建的。因此，理解复杂函数组成这一研究方向的长期目标是对这些模型的力量和局限性的突破性见解。这项提议的长期目标将导致理论计算机科学的重大突破。即使在目标(长期和短期)上取得部分进展，也将意味着在许多领域取得新的重要成果，如证明复杂性、量子通信和组合优化。由于函数组合的无处不在的性质，我们开发的工具和技术也将在计算机科学的许多其他领域提供帮助。此外，HQP所接受的培训将在工业界和学术界有广泛的应用。

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.