Spring 2016

Approximation Algorithms for Partition Functions of Edge-Coloring Models

Tuesday, March 29th, 2016 11:45 am12:30 pm

Add to Calendar

Partition functions of edge-coloring models are graph parameters closely related to counting graph homomorphisms. They appear in several academic disciplines; e.g. as Lie algebra weight systems in the theory of Vassiliev knot invariants, as Holant problems in theoretical computer science, as tensor networks in quantum information theory and as partition functions of vertex models in statistical physics.  In this talk I will describe a quasi polynomial time approximation algorithm for partition functions of a certain class of edge-coloring models.