ERC Consolidator Grant · 2025
Proof complexity of circuit lower bounds
One of the most fundamental and notorious open problems in theoretical computer science is the possible existence of highly efficient algorithms solving NP problems: there might be fast algorithms breaking established cryptosystems, automating theorem proving, making contemporary approaches to AI obsolete, and solving practically every computational task. This issue lies at the heart of the P versus NP problem, a central question of computational complexity, and particularly in the investigation of lower bounds on the efficiency of concrete computational models such as Boolean circuits. The notorious difficulty of proving complexity lower bounds became evident already in the early days of…
From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.