Opendata, web and dolomites

AUTAR SIGNED

A Unified Theory of Algorithmic Relaxations

Total Cost €

0

EC-Contrib. €

0

Partnership

0

Views

0

Project "AUTAR" data sheet

The following table provides information about the project.

Coordinator
UNIVERSITAT POLITECNICA DE CATALUNYA 

Organization address
address: CALLE JORDI GIRONA 31
city: BARCELONA
postcode: 8034
website: www.upc.edu

contact info
title: n.a.
name: n.a.
surname: n.a.
function: n.a.
email: n.a.
telephone: n.a.
fax: n.a.

 Coordinator Country Spain [ES]
 Project website http://www.cs.upc.edu/
 Total cost 1˙725˙656 €
 EC max contribution 1˙725˙656 € (100%)
 Programme 1. H2020-EU.1.1. (EXCELLENT SCIENCE - European Research Council (ERC))
 Code Call ERC-2014-CoG
 Funding Scheme ERC-COG
 Starting year 2015
 Duration (year-month-day) from 2015-06-01   to  2020-05-31

 Partnership

Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 
1    UNIVERSITAT POLITECNICA DE CATALUNYA ES (BARCELONA) coordinator 1˙725˙656.00

Map

 Project objective

For a large family of computational problems collectively known as constrained optimization and satisfaction problems (CSPs), four decades of research in algorithms and computational complexity have led to a theory that tries to classify them as algorithmically tractable vs. intractable, i.e. polynomial-time solvable vs. NP-hard. However, there remains an important gap in our knowledge in that many CSPs of interest resist classification by this theory. Some such problems of practical relevance include fundamental partition problems in graph theory, isomorphism problems in combinatorics, and strategy-design problems in mathematical game theory. To tackle this gap in our knowledge, the research of the last decade has been driven either by finding hard instances for algorithms that solve tighter and tighter relaxations of the original problem, or by formulating new hardness-hypotheses that are stronger but admittedly less robust than NP-hardness.

The ultimate goal of this project is closing the gap between the partial progress that these approaches represent and the original classification project into tractable vs. intractable problems. Our thesis is that the field has reached a point where, in many cases of interest, the analysis of the current candidate algorithms that appear to solve all instances could suffice to classify the problem one way or the other, without the need for alternative hardness-hypotheses. The novelty in our approach is a program to develop our recent discovery that, in some cases of interest, two methods from different areas match in strength: indistinguishability pebble games from mathematical logic, and hierarchies of convex relaxations from mathematical programming. Thus, we aim at making significant advances in the status of important algorithmic problems by looking for a general theory that unifies and goes beyond the current understanding of its components.

 Publications

year authors and title journal last update
List of publications.
2017 Gogacz, Tomasz, Torunczyk, Szymon
Entropy Bounds for Conjunctive Queries with Functional Dependencies
published pages: 15:1--15:17, ISSN: , DOI: 10.4230/LIPIcs.ICDT.2017.15
20th International Conference on Database Theory (ICDT 2017) LIPIcs 68 2020-04-23

Are you the coordinator (or a participant) of this project? Plaese send me more information about the "AUTAR" project.

For instance: the website url (it has not provided by EU-opendata yet), the logo, a more detailed description of the project (in plain text as a rtf file or a word file), some pictures (as picture files, not embedded into any word file), twitter account, linkedin page, etc.

Send me an  email (fabio@fabiodisconzi.com) and I put them in your project's page as son as possible.

Thanks. And then put a link of this page into your project's website.

The information about "AUTAR" are provided by the European Opendata Portal: CORDIS opendata.

More projects from the same programme (H2020-EU.1.1.)

NanoPD_P (2020)

High throughput multiplexed trace-analyte screening for diagnostics applications

Read More  

DISINTEGRATION (2019)

The Mass Politics of Disintegration

Read More  

PROGRESS (2019)

The Enemy of the Good: Towards a Theory of Moral Progress

Read More