ERC Starting Grant · 2017
Complexity Inside NP - A Computational Geometry Perspective
Traditional complexity theory focuses on the dichotomy between P and NP-hard problems. Lately, it has become increasingly clear that this misses a major part of the picture. Results by the PI and others offer glimpses on a fascinating structure hiding inside NP: new computational problems that seem to lie between polynomial and NP-hard have been identified; new conditional lower bounds for problems with large polynomial running times have been found; long-held beliefs on the difficulty of problems in P have been overturned. Computational geometry plays a major role in these developments, providing some of the main questions and concepts. We propose to explore this fascinating landscape…
From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.