Είστε εδώ:Αρχική/Research Projects/Rimaco

Rimaco

RIMACO

This project 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.

This project 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.

Πρόσθετες Πληροφορίες

Τελευταία άρθρα από τον/την Ερευνητική Μονάδα 1 - Θεμελιώσεις της Επιστήμης των Υπολογιστών

Περισσότερα σε αυτή την κατηγορία: « ROTA ARACNE: Approximation and Randomized Algorithms in Communication Networks »