ERC Consolidator Grant · 2023
Algebraic Formula Lower Bounds and Applications
Does efficient verification imply efficient search? Can randomness provide massive speed-ups in computation? These are fundamental questions in theoretical computer science, known as P vs. NP and P vs. BPP respectively. Progress on these questions requires us to to show that certain computational problems are inherently intractable, i.e. do not admit efficient solutions. An important, and concrete, approach to such questions is to understand the complexity of algebraic problems such as the Determinant and the Permanent, in algebraic models of computation. The aim of this project is to tackle these questions head on. Recent results of the PI and his collaborators have made progress on these…
From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.