20 citations · 20 across the 2 of their papers we have counts for
4 papers
Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model
Andreas Galanis, Qi Ge, Daniel Stefankovic +2
We study the computational complexity of approximately counting the number of independent sets of a graph with maximum degree Delta. More generally, for an input graph G=(V,E) and…
Strong spatial mixing of -colorings on Bethe lattices
Qi Ge, Daniel Stefankovic
We investigate the problem of strong spatial mixing of -colorings on Bethe lattices. By analyzing the sum-product algorithm we establish the strong spatial mixing of -colorin…
The Complexity of Counting Eulerian Tours in 4-Regular Graphs
Qi Ge, Daniel Stefankovic
We investigate the complexity of counting Eulerian tours ({\sc #ET}) and its variations from two perspectives---the complexity of exact counting and the complexity w.r.t. approxima…
A graph polynomial for independent sets of bipartite graphs
Qi Ge, Daniel Stefankovic
We introduce a new graph polynomial that encodes interesting properties of graphs, for example, the number of matchings and the number of perfect matchings. Most importantly, for b…