In 1987, Mark Jerrum (Queen Mary) and Alistair Sinclair (Berkley) submitted a paper to the 13th Workshop on Graph-theoretic Concepts in Computer Science (WG) held in Staffelstein, Germany. This summer their paper has been awarded a WG Test of Time Award at the 49th WG in Switzerland.
In 1987, Mark Jerrum (Queen Mary) and Alistair Sinclair (Berkley), both then at the University of Edinburgh, submitted a paper to the 13th Workshop on Graph-theoretic Concepts in Computer Science (WG) held in Staffelstein, Germany. The paper ‘Approximate counting, uniform generation and rapidly mixing Markov chains’ – an early contribution to the non-asymptotic analysis of the mixing time of Markov chains, and to the foundations of counting and sampling algorithms – was presented by Alistair Sinclair.
Thirty six years later, their paper has been given the WG Test of Time Award which is awarded to highly influential paper presented at a previous WG conference. Earlier this summer Professor Mark Jerrum was invited to the 49th WG in Fribourg, Switzerland to present a WG Test of Time Award lecture on the 1987 paper. Professor Jerrum reflects on the award and lecture saying ‘It was a fascinating opportunity to look back at the topic from a 21st century perspective. In the eighties, similar ideas were surfacing independently in theoretical computer science, statistical physics and probability theory, and in time their development became an interdisciplinary enterprise. The advances made over three-and-a-half decades have been remarkable. It's been a fun 36-year journey so far!’