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.