Inapproximability of the Independent Set Polynomial in the Complex Plane - Daniel Stefankovic

views comments

Hard-core model (also known as independent set polynomial) is one of the simplest models in statistical physics. The complexity of approximating the value of the partition function of the model on max-degree-Delta graphs (and also sampling from the Gibbs distribution) is now understood for positive values of the parameter (Weitz'2005, Sly'2009)---the complexity threshold aligns with the uniqueness/non-uniqueness threshold for the existence of multiple Gibbs measures on Delta-regular tree.

In the case of complex parameter the complexity of approximating the partition function is not yet understood---the complexity threshold appears to align with the existence of zeros of the partition function on trees of max-degree-Delta. We show that outside of the conjectured zero-free region the problem of approximating the value of the partition function is hard (#P-hard). Joint work with Ivona Bezakova, Andreas Galanis, and Leslie Ann Goldberg.

https://mediaspace.gatech.edu/media/stefankovic.mpg/1_chxid39i

Tags

Inapproximability of the Independent Set Polynomial in the Complex Plane - Daniel Stefankovic

Related Media