Synergies Between Complexity and Learning (SYCLE)

复杂性理论研究有效计算的本质和限制。它的圣杯是展示不可能的结果，称为复杂性下限：定理，建立了感兴趣的问题不能用有限的资源解决，如多项式时间。相比之下，学习理论从理论的角度研究机器学习算法，为设计和分析具有可证明保证的学习算法提供了严格的基础。这些领域有不同的哲学和目标。然而，近年来，有迹象表明它们之间存在着深刻而深远的联系。在本提案中，我们的目标是以系统的方式发展和探索复杂性与学习之间的联系。一方面，我们将采用学习理论的思想和观点来建立复杂性下限，这些下限抵制了更传统的方法。另一方面，我们建议从复杂性理论中探索技术，以进一步发展学习理论和设计新的学习算法。更广泛地说，我们的目标是在复杂性和学习之间交换思想和技术，以加速这两个领域的进展，扩大可用的工具库来解决他们的开放问题，以及获得更深入的理解有效计算的本质及其逻辑方面。这个项目建立在一个跨学科的方法，使近年来取得了重大进展。它有可能在算法和复杂性方面产生变革性的影响，并在我们对有效计算的限制和可能性的理解方面产生变革性的影响。强大的复杂性下限将允许设计无条件安全的加密应用程序和概率算法的去随机化，而计算学习的进步可以帮助弥合机器学习理论和实践之间的差距，并为多个领域的应用铺平道路。

Complexity Theory studies the nature and limits of efficient computation. Its holy grail is to show impossibility results known as complexity lower bounds: theorems which establish that problems of interest cannot be solved with limited resources, such as polynomial time. In contrast, Learning Theory investigates machine learning algorithms from a theoretical perspective, providing a rigorous foundation for the design and analysis of learning algorithms with provable guarantees. These fields have distinct philosophies and objectives. However, in recent years there have been indications of deep and far-reaching connections between them.In this proposal, we aim to develop and explore connections between complexity and learning in a systematic way. On the one hand, we will employ ideas and perspectives from learning theory to establish complexity lower bounds that have resisted more traditional approaches. On the other hand, we propose to explore techniques from complexity theory to further develop learning theory and to design new learning algorithms. More broadly, we aim to exchange ideas and techniques between complexity and learning to accelerate progress in both fields, broaden the arsenal of tools available to attack their open problems, as well as to obtain a deeper understanding of the nature of efficient computation and its logical aspects.This project builds on an interdisciplinary methodology that has enabled significant progress in recent years. It has potential for a transformative impact in algorithms and complexity and in our understanding of what can be proved about the limits and possibilities of efficient computation. Strong complexity lower bounds would allow the design of unconditionally secure cryptographic applications and the derandomisation of probabilistic algorithms, while advances in computational learning can help bridge the gap between the theory and practice of machine learning and pave the way to applications in several domains.