Understanding complexity through function composition

通过函数组合理解复杂性

• 批准号: RGPIN-2022-05211
• 负责人: Koroth, Sajin
• 金额: $ 2.48万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=749847
• 关键词: 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.

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