SYCLE - Synergies Between Complexity and Learning

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.