Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

17.05.2021

Two papers accepted at ICALP

The International Colloquium on Automata, Languages and Programming (ICALP) is one of the prime theory venues in Europe and the annual meeting of the European Association for Theoretical Computer Science (EATCS). The 2021 edition will be held virtually July 12-16, organized by the University of Glasgow. Authors of the Algorithm Engineering group contribute two papers, both are motivated by statistical physics.

The first one investigates the hard-spheres model, which is widely used for particle dynamics in fluids and solids. The particles follow a continuous probability distribution in space, an important property of this distribution is its normalizing factor, the partition function. The paper presents the first FPRAS for the partition function for the whole range of parameters for which the hard-sphere model is known to be free of a phase transition.

The second work is on counting the number of homomorphisms from an input graph to a fixed quantum graph, which is a formal linear combination of graphs. Most graph parameters have an equivalent expression as the number of homomorphisms to a quantum graph, whose affiliated counting problem in a finite field of prime order is not well understood. The paper shows that its complexity is entirely characterized by the complexity of counting the homomorphisms to each of the quantum graph's constituents. Focusing on the latter problem, the paper advances the complexity map towards a conjectured dichotomy.

  • Friedrich, Tobias; Göbel, Andreas; Krejca, Martin; Pappik, MarcusA spectral independence view on hard spheres via block dynamics. International Colloquium on Automata, Languages and Programming (ICALP) 2021
     
  • On Counting (Quantum-)Gra... - Download
    Lagodzinski, J. A. Gregor; Göbel, Andreas; Casel, Katrin; Friedrich, TobiasOn Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order. International Colloquium on Automata, Languages and Programming (ICALP) 2021: 86:1 -- 86:15