8 citations · 11 across the 9 of their papers we have counts for
7 papers · 1 filter
An FPRAS for Antiferromagnetic Ising Models on Random Regular Bipartite Graphs
Zhidan Li, Kuan Yang
We design randomized approximation schemes for the partition function of antiferromagnetic Ising models with uniform external field on random regular bipartite graphs. Our algorith…
Counting and Sampling Anti-ferromagnetic Potts Models on Random Regular Bipartite Graphs in the Non-uniqueness Regime
Zhidan Li, Siyu Liu, Kuan Yang
The anti-ferromagnetic multi-state Potts model, a generalization of the Ising model, is one of the most fundamental models in statistical physics. It was conjectured by Kotecký (Ph…
Improved Bounds for Sampling Solutions of Random CNF Formulas
Kun He, Kewen Wu, Kuan Yang
Let be a random -CNF formula on variables and clauses, where each clause is a disjunction of literals chosen independently and uniformly. Our goal is to sample a…
Counting solutions to random CNF formulas
Andreas Galanis, Leslie Ann Goldberg, Heng Guo +1
We give the first efficient algorithm to approximately count the number of solutions in the random -SAT model when the density of the formula scales exponentially with . The…
An FPTAS for Counting Proper Four-Colorings on Cubic Graphs
Pinyan Lu, Kuan Yang, Chihao Zhang +1
Graph coloring is arguably the most exhaustively studied problem in the area of approximate counting. It is conjectured that there is a fully polynomial-time (randomized) approxima…
Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems
Andreas Galanis, Leslie Ann Goldberg, Kuan Yang
We study the complexity of approximate counting Constraint Satisfaction Problems (#CSPs) in a bounded degree setting. Specifically, given a Boolean constraint language and a de…
FPTAS for Hardcore and Ising Models on Hypergraphs
Pinyan Lu, Kuan Yang, Chihao Zhang
Hardcore and Ising models are two most important families of two state spin systems in statistic physics. Partition function of spin systems is the center concept in statistic phys…