RIMACO

Rigorous Mathematical Connections between the Theory of Computations and Statistical Physics

Coordinatore	COMPUTER TECHNOLOGY INSTITUTE & PRESS DIOPHANTUS    more Spiacenti, non ci sono informazioni su questo coordinatore. Contattare Fabio per maggiori infomrazioni, grazie.
Nazionalità Coordinatore	Greece [EL]
Totale costo	749˙996 €
EC contributo	749˙996 €
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-2007-StG
Funding Scheme	ERC-SG
Anno di inizio	2008
Periodo (anno-mese-giorno)	2008-07-01   -   2014-06-30

 Partecipanti

#	participant	country	role	EC contrib. [€]
1	COMPUTER TECHNOLOGY INSTITUTE & PRESS DIOPHANTUS  Organization address address: N KAZANTZAKI CAMPUS city: RIO PATRAS postcode: 26500 contact info Titolo: Ms. Nome: Eleni Cognome: Anisiou Email: send email Telefono: +30 2610 960200 Fax: +30 2610 960490	EL (RIO PATRAS)	hostInstitution	0.00
2	COMPUTER TECHNOLOGY INSTITUTE & PRESS DIOPHANTUS  Organization address address: N KAZANTZAKI CAMPUS city: RIO PATRAS postcode: 26500 contact info Titolo: Prof. Nome: Dimitris Cognome: Achlioptas Email: send email Telefono: +30 210 9617572 Fax: +30 2610 960490	EL (RIO PATRAS)	hostInstitution	0.00

Mappa

 Word cloud

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

 Obiettivo del progetto (Objective)

'The proposed research aims to enhance the study of randomness in computation by using ideas of statistical physics. In particular, it aims to place the connection between computation and statistical physics --- the subject of wide heuristic discussion for more than three decades --- on rigorous mathematical ground. Its main methodological vehicle is the study of random Constraint Satisfaction Problems (CSPs). CSPs are the common abstraction of numerous real-life problems and occur in areas ranging from aerospace design to biochemistry. Their ubiquity makes the design of efficient algorithms for CSPs extremely important. At the foundation of this endeavor lies the question of why certain CSP instances are exceptionally hard while other, seemingly similar, instances are easy. Probability distributions over instances allow us to study this phenomenon in a principled way, with each CSP distribution controlled by its ratio of constrains to variables (known as constraint density). By now, it has been established that random CSPs have solutions at densities much beyond the reach of any known efficient algorithm. Understanding the origin of this gap and designing algorithms that overcome it is the main focus of the proposed research. Ideas from statistical physics will play an important role here. Specifically, in recent years, physicists have proposed a heuristic but deep theory for the evolution of the solution-space geometry of random CSPs according to which algorithmic barriers correspond to phase transitions in this evolution. Examining the validity of the physics theory is a major research undertaking that must develop and reconcile notions shared by computation and statistical physics, e.g., the role of long-range correlations. A rigorous mathematical theory of such notions will enable a much more energetic exchange of ideas between the two fields, and has the potential to bring substantial fresh ideas to the study of efficient computation.'