Approximating partition functions on geometric spaces

• Applicant: Dr. Andreas Göbel
• Subject Area: Theoretical Computer Science
• Term: since 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 467516565

Probability distributions can model the macroscopic behaviour of complex systems consisting of microscopic interactions. Such models, which originate from statistical physics, explain mathematically a variety of prominent real-world phenomena from liquid evaporation or racial segregation to evolution. An important quantity associated with such models is the partition function, a weighted sum over all possible states of the respective systems. Computing the partition function is a computational counting problem with many applications in computer science including databases, computer vision or machine learning. Approximating the partition function suffices for most applications, while computing it exactly is typically a hard problem.The two different viewpoints of complex systems, the computational and the statistical-physics viewpoint, have led to a two-way exchange: algorithmic techniques are inspired by methods of statistical physics, while tools developed for algorithmic analysis help us understand the macroscopic behaviour of these systems. This exchange illustrates remarkable concurrences of several system’s computational and macroscopic phase transition points. Geometric models of real-world systems are commonly studied in the statistical-physics literature, but rigorous computational results for geometric inputs are sparse. This holds in particular for approximating partition functions.The proposed research aspires to start a new direction in approximate counting by investigating the effect of geometry on the computational complexity of approximating partition functions. We expect that the computational study of partition functions on geometric inputs leads to novel approximation algorithms and hardness results. These expectations are justified by the fact that the most frequent gadget used to show hardness of approximation cannot be constructed under geometric restrictions. Furthermore, recent results show a multitude of NP-hard decision problems that become tractable when their input is restricted by the effect of some geometry. This provides the opportunity to design new approximation algorithms also for the - typically even harder - counting versions of these problems. In order to achieve these goals, we propose tangible work packages which include the computational analysis of classical continuous spin systems and the analysis of partition functions restricted to random geometric models of real-world networks. Outside the algorithmic interest of our results, we also expect new insights on the statistical physics side.

• DFG Programme: Research Grants
• International Connection: United Kingdom
• Cooperation Partner: Professor Andreas Galanis, Ph.D.
• Co-Investigator: Professor Dr. Thomas Bläsius