Algorithmen und Dynamik unter Phasenübergangsphänomenen

• Antragsteller: Dr. Charilaos Efthymiou
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2015 bis 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 265444125

Ziel des Projekts ist es, grundlegende Optimierungsprobleme, insbesondere zufällige Erfüllbarkeitsprobleme ("Random Constraint Satisfaction Problems", kurz "rCSP"), besser zu erforschen. Dank tiefer aber mathematisch nichtrigoroser Ansätze aus der Statistischen Mechanik hat sich im Studium der rCSP eine neue Perspektive eröffnet: die sogenannte Cavity-Mehtode trifft eindrucksvolle Voraussagen über grundlegende Eigenschaften von rCSP.Unser Ziel ist es, die Korrektheit einiger wichtiger Vorhersagen der Cavity-Methode bezüglich der Struktur von Gibbs-Verteilungen in verschiedenen rCSP Modellen zu untersuchen. Des Weiteren möchten wir wichtige lokale Algorithmen für rCSP wie Message-Passing-Algorithmen, Glauber-Dynamics, Metropolis-Prozesse und einen neuen, kürzlich vom Antragssteller entwickelten Algorithmus analysieren.

• DFG-Verfahren: Sachbeihilfen