ERC Consolidator Grant · 2020
Efficient Proofs and Computation: A Unified Algebraic Approach
Computational complexity lies at the heart of information and computer science. Its aim is to formally understand the boundary between problems that can be solved efficiently and those that cannot. This has many applications: new algorithms are important to make progress in domains such as machine learning and optimization, and new complexity lower bounds (namely, computational impossibility results) are essential to provably secure cryptography. Beyond practical applications, these questions reveal deep mathematical and natural phenomena. One of the prominent directions to attack the fundamental lower bound questions in complexity comes from the study of resource bounded provability,…
From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.