LFCS seminar: Andreas Galanis: Inapproximability of the independent set polynomial in the complex plane
—
filed under:
LFCS Seminar,
Upcoming events
What 


When 
Apr 24, 2018 from 04:00 PM to 05:00 PM 
Where  IF 4.31/4.33 
Add event to calendar 
vCal iCal 
For a graph G, let p_G(λ) denote the independent set polynomial of G with parameter λ.
For which λ can we approximate the value p_G(λ) on graphs G of maximum degree D?
This problem is already well understood when λ is a real number using connections
to phase transitions in statistical physics on the Dregular tree.
Understanding the case where λ is complex turns out to be more challenging.
Peters and Regts studied an analogue of the phase transition on the Dregular tree
for general complex values of λ. They identified a region Λ(D) in the complex plane and,
motivated by the real case, they asked whether Λ(D) marks the approximability threshold
for general complex values λ.
We show that for every λ outside of Λ(D), the problem of approximating p_G(λ) on graphs G
with max degree D is indeed NPhard. In fact, when λ is outside of the region and is not a
positive real number, we give the stronger result that approximating p_G(λ) is actually #Phard.
This is joint work with Ivona Bezakova, Leslie Ann Goldberg, and Daniel Stefankovic.