15 citations · 32 across the 25 of their papers we have counts for
26 papers
Homomorphism Indistinguishability Beyond Graphs: Relational Weisfeiler--Leman and Hypertree Width
Panagiotis Aivasiliotis, Andreas Göbel, Matthias Lanzinger +1
The Weisfeiler--Leman (WL) algorithm is one of the most influential heuristics for the graph isomorphism problem. The expressive power of WL has been extensively studied in the con…
Uniqueness, analyticity and mixing for Gibbs point processes via spectral gaps
Andreas Göbel, Matthew Jenssen, Marcus Michelen +3
A Gibbs point process models particles interacting in the continuum through a potential. Among the most classical examples is the hard-sphere model, where given an activity paramet…
A simple proof of rapid mixing on random regular graphs beyond uniqueness
Andreas Göbel, Matthew Jenssen, Marcus Michelen +3
A recent breakthrough of Chen, Chen, Chen, Yin, and Zhang shows rapid mixing for Glauber dynamics for the hard-core model on random regular graphs beyond the tree uniqueness thresh…
Reemergence of the Epidemic Threshold in SIRS Infections on Connected Stars
Andreas Göbel, Nicolas Klodt, Martin S. Krejca
The SIRS process is a continuous-time process for how infections spread on a graph. In this model, each vertex is in one of the following three states: susceptible (to the infectio…
Temporal Exploration of Random Spanning Tree Models
Samuel Baguley, Andreas Göbel, Nicolas Klodt +3
The Temporal Graph Exploration problem (TEXP) takes as input a temporal graph, i.e., a sequence of graphs on the same vertex set, and asks for a walk of s…
Testing Thresholds and Spectral Properties of High-Dimensional Random Toroidal Graphs via Edgeworth-Style Expansions
Samuel Baguley, Andreas Göbel, Marcus Pappik +1
We study high-dimensional random geometric graphs (RGGs) of edge-density with vertices uniformly distributed on the -dimensional torus and edges inserted between sufficientl…
Gradually Declining Immunity Retains the Exponential Duration of Immunity-Free Diffusion
Andreas Göbel, Nicolas Klodt, Martin S. Krejca +1
Diffusion processes pervade numerous areas of AI, abstractly modeling the dynamics of exchanging, oftentimes volatile, information in networks. A central question is how long the i…
Perfect sampling from rapidly mixing Markov chains
Andreas Göbel, Jingcheng Liu, Pasin Manurangsi +1
We show that efficient approximate sampling algorithms, combined with a slow exponential time oracle for computing its output distribution, can be combined into constructing effici…
Uniqueness of locally stable Gibbs point processes via spatial birth-death dynamics
Samuel Baguley, Andreas Göbel, Marcus Pappik
We prove that for every locally stable and tempered pair potential with bounded range, there exists a unique infinite-volume Gibbs point process on for every act…
From Market Saturation to Social Reinforcement: Understanding the Impact of Non-Linearity in Information Diffusion Models
Tobias Friedrich, Andreas Göbel, Nicolas Klodt +2
Diffusion of information in networks is at the core of many problems in AI. Common examples include the spread of ideas and rumors as well as marketing campaigns. Typically, inform…
The Weisfeiler-Leman Dimension of Conjunctive Queries
Andreas Göbel, Leslie Ann Goldberg, Marc Roth
The Weisfeiler-Leman (WL) dimension of a graph parameter is the minimum such that, if and are indistinguishable by the -dimensional WL-algorithm then $f(G_1)…
Real-World Networks are Low-Dimensional: Theoretical and Practical Assessment
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann +1
Detecting the dimensionality of graphs is a central topic in machine learning. While the problem has been tackled empirically as well as theoretically, existing methods have severa…
Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann +1
A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations, by focusing the studies on random graph models that are used to rep…
Analysis of the survival time of the SIRS process via expansion
Tobias Friedrich, Andreas Göbel, Nicolas Klodt +2
We study the SIRS process, a continuous-time Markov chain modeling the spread of infections on graphs. In this model, vertices are either susceptible, infected, or recovered. Each…
Using random graphs to sample repulsive Gibbs point processes with arbitrary-range potentials
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann +2
We study computational aspects of repulsive Gibbs point processes, which are probabilistic models of interacting particles in a finite-volume region of space. We introduce an appro…
Algorithms for hard-constraint point processes via discretization
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann +2
We study algorithmic applications of a natural discretization for the hard-sphere model and the Widom-Rowlinson model in a region . These models are…
A spectral independence view on hardspheres via block dynamics
Tobias Friedrich, Andreas Göbel, Martin S. Krejca +1
The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core i…
On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order
J. A. Gregor Lagodzinski, Andreas Göbel, Katrin Casel +1
We study the problem of counting the number of homomorphisms from an input graph to a fixed (quantum) graph in any finite field of prime order . The sub…
Polymer Dynamics via Cliques: New Conditions for Approximations
Tobias Friedrich, Andreas Göbel, Martin S. Krejca +1
Abstract polymer models are systems of weighted objects, called polymers, equipped with an incompatibility relation. An important quantity associated with such models is the partit…
The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability
Thomas Bläsius, Tobias Friedrich, Andreas Göbel +2
Satisfiability is considered the canonical NP-complete problem and is used as a starting point for hardness reductions in theory, while in practice heuristic SAT solving algorithms…
Zeros and approximations of Holant polynomials on the complex plane
Katrin Casel, Philipp Fischbeck, Tobias Friedrich +2
We present fully polynomial approximation schemes for a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into…
Intuitive Analyses via Drift Theory
Andreas Göbel, Timo Kötzing, Martin S. Krejca
Drift theory is an intuitive tool for reasoning about random processes: It allows turning expected stepwise changes into expected first-hitting times. While drift theory is used ex…
Amplifiers for the Moran Process
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg +2
The Moran process, as studied by Lieberman, Hauert and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlyin…
Counting Homomorphisms to Square-Free Graphs, Modulo 2
Andreas Göbel, Leslie Ann Goldberg, David Richerby
We study the problem HomsTo of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph . A characteristic feature of modular counting is that ca…