Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

05.09.2024

Two Papers accepted at RANDOM and ESA

Recently two papers of our group members were accepted: First, the paper Fast and Slow Mixing of the Kawasaki Dynamics on Bounded-Degree Graphs was accepted at the International Conference on Randomization and Computation (RANDOM) which took place on 28-30 August in London, UK. The authors study the worst-case mixing time of the Kawasaki dynamics for the fixed magnetization Ising model on bounded-degree graphs, relating it to various phase transition thresholds of the grand-canonical Ising model. The main result is to partially disprove a conjecture by Carlson, Davies, Kolla and Perkins by showing that, above the tree uniqueness threshold, Kawasaki dynamics are not rapidly mixing throughout the entire tractable magnetization regime.

The second paper with the title How to Reduce Temporal Cliques to Find Sparse Spanners was the result of a master project. It is published at the European Symposium on Algorithms (ESA) which took place in Egham, UK on 2-4 September. Many real-world networks, such as transportation or trade networks, are dynamic in the sense that the connections may change over time, but these changes are known in advance. This behavior is captured by the temporal graphs model, which has recently become a trending topic in theoretical computer science. A core open problem in the field is to prove the existence of linear-size temporal spanners in temporal cliques, i.e., sparse subgraphs of complete temporal graphs that ensure all-pairs reachability via temporal paths. The authors present significant progress towards proving whether linear-size temporal spanners exist in all temporal cliques by providing novel techniques to tackle the problem.

 

  • Angrick, Sebastian; Bals, Ben; Friedrich, Tobias; Gawendowicz, Hans; Hastrich, Niko; Klodt, Nicolas; Lenzner, Pascal; Schmidt, Jonas; Skretas, George; Wells, Armin How to Reduce Temporal Cliques to Find Sparse SpannersEuropean Symposium on Algorithms (ESA) 2024