Approximation von Zustandssummen in geometrischen Räumen

• Antragsteller: Dr. Andreas Göbel
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 467516565

Wahrscheinlichkeitsverteilungen beschreiben das makroskopische Verhalten komplexer Systeme, welches aus der Interaktion einzelner Einheiten auf der mikroskopischen Ebene entsteht. Solche aus der statistischen Physik stammenden Modelle ermöglichen ein mathematisches Verständnis realweltlicher Phänomene von der Flüssigkeitsverdampfung über die Rassentrennung bis hin zur Evolution. Eine typische Kenngröße dieser Modelle ist hierbei die Zustandssumme, eine gewichtete Summe aller möglichen Zustände der jeweiligen Systeme. Die Berechnung der Zustandssumme ist ein klassisches Zählproblem mit zahlreichen Anwendungsbereichen innerhalb der Informatik wie Datenbanken, Computer Vision und maschinellem Lernen. Die exakte Berechnung der Zustandssumme ist typischerweise schwer. Jedoch ist für den Großteil der Anwendungsfälle eine Approximation ausreichend.Die verschiedenen Blickwinkel der Informatik und statistischen Physik auf komplexe Systeme haben zu einem fruchtbaren Austausch geführt: Algorithmische Verfahren wurden durch Methoden der statistischen Physik beeinflusst, während Werkzeuge aus der algorithmischen Analyse zum Verständnis des makroskopischen Verhaltens der untersuchten Systeme beigetragen haben. Bemerkenswert hierbei ist die Übereinstimmung der Phasenübergangspunkte, die jeweils in der statistischen Physik und der Algorithmik mit ihren unterschiedlichen Herangehensweisen identifiziert wurden. Die Literatur zur statistischen Physik umfasst darüber hinaus zahlreiche Ergebnisse zu geometrischen Modellen realweltlicher Systeme. Vergleichbare Ergebnisse im Bereich rigoroser, algorithmischer Analysen sind hingegen bisher selten; dies gilt insbesondere für die Approximation von Zustandssummen.Das Forschungsprojekt zielt auf eine neue Form des approximativen Zählens, indem es den Effekt von Geometrie auf die algorithmische Komplexität approximierter Zustandssummen einbezieht. Wir erwarten, dass die algorithmische Untersuchung von Zustandssummen mit geometrischen Eigenschaften zu neuartigen Approximationsalgorithmen aber auch neuen unteren Schranken führt. Diese Erwartung gründet auf der Beobachtung, dass die am häufigsten verwendeten Beweis-Gadgets für approximative Schwere in geometrischen Räumen nicht konstruiert werden können. Zudem existiert eine Reihe von jüngeren Ergebnissen, bei denen NP-schwere Probleme unter Einbeziehung von geometrischen Eigenschaften, algorithmisch berechenbar werden. Dies ermöglicht die Entwicklung neuartiger Approximationsalgorithmen für Abzählvarianten dieser Probleme, die schwerer sind als deren Entscheidungsvarianten. Um das skizzierte Ziel zu erreichen, fokussieren wir uns auf die algorithmische Analyse klassischer kontinuierlicher Spinsysteme und auf Zustandssummen randomisierter geometrischer Modelle realweltlicher Netzwerke. Wir erwarten, dass unsere algorithmischen Ergebnisse zu neuartigen Resultaten auf dem Gebiet der statistischen Physik führen.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Großbritannien
• Kooperationspartner: Professor Andreas Galanis, Ph.D.
• Mitverantwortlich: Professor Dr. Thomas Bläsius