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.