MCC

Mapping the Complexity of Counting

Coordinatore	THE CHANCELLOR, MASTERS AND SCHOLARS OF THE UNIVERSITY OF OXFORD    more Spiacenti, non ci sono informazioni su questo coordinatore. Contattare Fabio per maggiori infomrazioni, grazie.
Nazionalità Coordinatore	United Kingdom [UK]
Totale costo	2˙499˙093 €
EC contributo	2˙499˙093 €
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-ADG
Funding Scheme	ERC-AG
Anno di inizio	2014
Periodo (anno-mese-giorno)	2014-03-01   -   2019-02-28

 Partecipanti

#	participant	country	role	EC contrib. [€]
1	THE CHANCELLOR, MASTERS AND SCHOLARS OF THE UNIVERSITY OF OXFORD  Organization address address: University Offices, Wellington Square city: OXFORD postcode: OX1 2JD contact info Titolo: Ms. Nome: Gill Cognome: Wells Email: send email Telefono: +44 1865 289800 Fax: +44 1865 289801	UK (OXFORD)	hostInstitution	2˙499˙093.00
2	THE CHANCELLOR, MASTERS AND SCHOLARS OF THE UNIVERSITY OF OXFORD  Organization address address: University Offices, Wellington Square city: OXFORD postcode: OX1 2JD contact info Titolo: Prof. Nome: Leslie Ann Cognome: Goldberg Email: send email Telefono: +44 1865 610755 Fax: +44 01865 273839	UK (OXFORD)	hostInstitution	2˙499˙093.00

Mappa

 Word cloud

Esplora la "nuvola delle parole (Word Cloud) per avere un'idea di massima del progetto.

 Obiettivo del progetto (Objective)

'Just as advances in engineering rely on a deep foundational knowledge of physics, so too advances in algorithms and programming rely on a deep knowledge of the intrinsic nature of computation. Significant progress has been made, particularly in the field of computational complexity, which aims to discover which computational problems are feasible, which are inherently infeasible, and why. However, huge theoretical challenges remain: many problem classes are poorly understood, including those containing problems arising in practical applications. The MCC project will enable significant computational advances in a host of application areas through the development of a comprehensive theory of counting problems. These problems, which involve the computation of weighted sums, are common and important, arising in practical applications from diverse fields including statistics, statistical physics, information theory, coding, and machine learning. Thus, it is of fundamental importance to understand their complexity. We propose a coherent and systematic study of the complexity of counting problems. A sequence of exciting recent developments, pioneered by the PI and others, makes it plausible that we now have the tools needed to make substantial progress. The overall objectives of MCC are (1) Map out the landscape of computational counting problems (exact and approximate), determining which problems are tractable, and which are intractable (quantifying the extent of tractability), and (2) Develop complexity characterisations elucidating the features that make counting problems tractable or intractable, not only discovering which problems are tractable, but also discovering a characterisation telling us why. The project encompasses a large range of wide-open problems. However, the strength of the PI, the scale of the project, the timeliness of the project (given recent results), and the novel methods proposed make it certain that the research will produce breakthroughs.'