European Companies Search Engine
EU funding (€1,486,800): Complexity Inside NP - A Computational Geometry Perspective Hor30 Oct 2017 EU Research and Innovation programme "Horizon"
Overview
Text
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 inside NP from the perspective of computational geometry, guided by three complementary questions: (A) What can we say about the complexity of search problems derived from existence theorems in discrete geometry? These problems offer a new perspective on complexity classes previously studied in algorithmic game theory (PPAD, PLS, CLS). Preliminary work indicates that they have the potential to answer long-standing open questions on these classes. (B) Can we provide meaningful conditional lower bounds on geometric problems for which we have only algorithms with large polynomial running time? Prompted by a question raised by the PI and collaborators, such lower bounds were developed for the Frechet distance. Are similar results possible for problems not related to distance measures? If so, this could dramatically extend the traditional theory based on 3SUM-hardness to a much more diverse and nuanced picture. (C) Can we find subquadratic decision trees and faster algorithms for 3SUM-hard problems? After recent results by Pettie and Gronlund on 3SUM and by the PI and collaborators on the Frechet distance, we have the potential to gain new insights on this large class of well-studied problems and to improve long-standing complexity bounds for them.
Funded Companies:
| Company name | Funding amount |
| FREIE UNIVERSITAET BERLIN | €1,486,800 |
Source: https://cordis.europa.eu/project/id/757609
The filing refers to a past date, and does not necessarily reflect the current state. The current state is available on the following page: Freie Universität Berlin, Berlin, Germany.
The visualizations for "FREIE UNIVERSITAET BERLIN - EU funding (€1,486,800): Complexity Inside NP - A Computational Geometry Perspective"
are provided by
North Data
and may be reused under the terms of the
Creative Commons CC-BY license.
