Paper Info
Title
Inapproximability of the independent set polynomial below the Shearer threshold.
Abstract
We study the problem of approximately evaluating the independent set polynomial of bounded-degree graphs at a point lambda or, equivalently, the problem of approximating the partition function of the hard-core model with activity lambda on graphs G of max degree D. lambdau003e0, breakthrough results of Weitz and Sly established a computational transition from easy to hard at lambda_c(D)=(D-1)^(D-1)/(D-2)^D, which coincides with the tree uniqueness phase transition from statistical physics. For lambdau003c0, the evaluation of the independent set polynomial is connected to the conditions of the Lovasz Local Lemma. Shearer identified the threshold lambda*(D)=(D-1)^(D-1)/D^D as the maximum value p such that every family of events with failure probability at most p and whose dependency graph has max degree D has nonempty intersection. Very recently, Patel and Regts, and Harvey et al. have independently designed FPTASes for approximating the partition function whenever |lambda|u003clambda*(D). Our main result establishes for the first time a computational transition at the Shearer threshold. We show that for all Du003e=3, for all lambda -lambda*(D), establishes a phase transition for negative activities. In fact, we now have the following picture for the problem of approximating the partition function with activity lambda on graphs G of max degree D. 1. -lambda*(D)u003clambdau003clambda_c(D), the problem admits an FPTAS. 2. lambda lambda_c(D), the problem is NP-hard. Rather than the tree uniqueness threshold of the positive case, the phase transition for negative activities corresponds to the existence of zeros for the partition function of the tree below -lambda*(D).
Year
DOI
Venue
2017
10.4230/LIPIcs.ICALP.2017.28
international colloquium on automata, languages and programming
DocType
Volume
Citations 
Conference
abs/1612.05832
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
andreas galanis16815.13
leslie ann goldberg21411125.20
Daniel Stefankovic324328.65