Abstract
The independence polynomial is one of the most well-studied graph polynomials, arising in both combinatorics and computer science. It is also known in statistical physics as the “partition function of the hard-core model”. I’ll describe the polynomial —what it is and why people care about it. Then I will tell you what is known about the complexity of approximating this polynomial. There is a lot of recent work, including both algorithms and hardness results. An emerging trend is that, in order to really understand the complexity, it is useful to work over complex numbers, rather than just over the reals. If time permits I will tell you about recently-discovered approximation algorithms in the so-called “low temperature regime” when the input graph is a bipartite expander. The talk will be a survey, based on work by many authors.Time
2019-12-09 09:00 ~ 10:00Speaker
Leslie Ann Goldberg, University of OxfordRoom
First floor, New Lab building, Shanghai University of Finance & Economics
