The WG Test of Time Award is given for a highly influential paper presented at a previous WG conference. The award is handed out at the conference, and the authors of the winning paper are invited to give a WG Test of Time Award lecture.
2023: Alistair Sinclair, Mark Jerrum: Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains. WG 1987: 134-148, DOI, Laudatio.
2019: Reuven Bar-Yehuda, Shimon Even: A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem. WG 1983: 17-28, DOI (journal version), Laudatio.
2018: Burkhard Monien, Ivan Hal Sudborough: Bounding the Bandwidth of NP-Complete Problems. WG 1980: 279-292, DOI, Laudatio.