A research collaboration between the School of Mathematical Sciences at Queen Mary and the Department of Computer Science at Liverpool received recognition at the recent "International Colloquium on Automata, Languages and Programming" (ICALP) held at the University of Warwick. ICALP is the premier European meeting for theoretical computer science. Professor Mark Jerrum (Queen Mary) and Professor Leslie Ann Goldberg (Liverpool) received the best paper award in Track A (Algorithms, Complexity and Games) for "The complexity of computing the sign of the Tutte polynomial (and consequent #P-hardness of Approximation)".
The Tutte polynomial of a graph is a two-variable polynomial that encodes much interesting information about the graph: it includes as specialisations the chromatic polynomial from combinatorics and the Potts partition function from statistical physics. The authors show that determining the sign of the Tutte polynomial at a given point can be computationally "much harder" than a typical decision problem, even though there are just three outcomes (positive, negative and zero) to distinguish. The results build on earlier work by Professor Bill Jackson (also of the School of Mathematical Sciences) and Professor Alan Sokal (NYU and UCL).