15 citations · 32 across the 25 of their papers we have counts for
6 papers · 1 filter
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…
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…
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…
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…
The Complexity of Counting Homomorphisms to Cactus Graphs Modulo 2
Andreas Göbel, Leslie Ann Goldberg, David Richerby
A homomorphism from a graph G to a graph H is a function from V(G) to V(H) that preserves edges. Many combinatorial structures that arise in mathematics and computer science can be…
Counting list matrix partitions of graphs
Andreas Göbel, Leslie Ann Goldberg, Colin McQuillan +2
Given a symmetric D*D matrix M over {0,1,*}, a list M-partition of a graph G is a partition of G's vertices into D parts associated with the rows of M. The part of each vertex is c…