SYCLE - Synergies Between Complexity and Learning
Description
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 project, 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.
Duration
The project runs from November 2023 to October 2028.
Host Institution
The project is hosted by the Department of Computer Science and the Centre for Discrete Mathematics and Its Applications (DIMAP) at the University of Warwick.
Funding Information
This project was awarded an ERC Starting Grant in December 2022, making it one of only two ERC StG awards in Computer Science and Informatics (PE6 panel) in the UK for that round. However, due to the UK's non-association with the ERC at the time, the grant was converted into an equivalent UKRI Guarantee Grant.
