Graph Polynomials and Computational Complexity

interesting information about the graph. Many different graph
polynomials have been studied since the beginning of the last
century. This talk will provide an insight into graph polynomials from
the complexity theory point of view. In particular, we will see how
graph polynomials establish reductions between graph-related
computational problems. A key ingredient for this are graph
transformations. As an example, we will consider the interlace
polynomial and observe how "cloning of vertices" can be used to prove
that the interlace polynomial is hard to evaluate almost everywhere
and that the independent set polynomial is hard to approximate almost
everywhere.