ALUNIF
Algorithms and Lower Bounds: A Unified Approach
| Coordinatore | THE UNIVERSITY OF EDINBURGH
Spiacenti, non ci sono informazioni su questo coordinatore. Contattare Fabio per maggiori infomrazioni, grazie. |
| Nazionalità Coordinatore | United Kingdom [UK] |
| Totale costo | 1˙274˙496 € |
| EC contributo | 1˙274˙496 € |
| Programma | FP7-IDEAS-ERC
Specific programme: "Ideas" implementing the Seventh Framework Programme of the European Community for research, technological development and demonstration activities (2007 to 2013) |
| Code Call | ERC-2013-CoG |
| Funding Scheme | ERC-CG |
| Anno di inizio | 2014 |
| Periodo (anno-mese-giorno) | 2014-03-01 - 2019-02-28 |
Partecipanti
| # | ||||
|---|---|---|---|---|
| 1 |
THE UNIVERSITY OF EDINBURGH
Organization address
address: OLD COLLEGE, SOUTH BRIDGE contact info |
UK (EDINBURGH) | hostInstitution | 1˙274˙496.00 |
| 2 |
THE UNIVERSITY OF EDINBURGH
Organization address
address: OLD COLLEGE, SOUTH BRIDGE contact info |
UK (EDINBURGH) | hostInstitution | 1˙274˙496.00 |
Mappa
Word cloud
Esplora la "nuvola delle parole (Word Cloud) per avere un'idea di massima del progetto.
Obiettivo del progetto (Objective)
'One of the fundamental goals of theoretical computer science is to understand the possibilities and limits of efficient computation. This quest has two dimensions. The theory of algorithms focuses on finding efficient solutions to problems, while computational complexity theory aims to understand when and why problems are hard to solve. These two areas have different philosophies and use different sets of techniques. However, in recent years there have been indications of deep and mysterious connections between them.
In this project, we propose to explore and develop the connections between algorithmic analysis and complexity lower bounds in a systematic way. On the one hand, we plan to use complexity lower bound techniques as inspiration to design new and improved algorithms for Satisfiability and other NP-complete problems, as well as to analyze existing algorithms better. On the other hand, we plan to strengthen implications yielding circuit lower bounds from non-trivial algorithms for Satisfiability, and to derive new circuit lower bounds using these stronger implications.
This project has potential for massive impact in both the areas of algorithms and computational complexity. Improved algorithms for Satisfiability could lead to improved SAT solvers, and the new analytical tools would lead to a better understanding of existing heuristics. Complexity lower bound questions are fundamental but notoriously difficult, and new lower bounds would open the way to unconditionally secure cryptographic protocols and derandomization of probabilistic algorithms. More broadly, this project aims to initiate greater dialogue between the two areas, with an exchange of ideas and techniques which leads to accelerated progress in both, as well as a deeper understanding of the nature of efficient computation.'