Bernard Chazelle wins the 2018 ESA Test-of-Time Award

The European Symposia on Algorithms (ESA) Test-of-Time Award (ToTA) recognizes excellent papers in algorithms research that were published in the ESA proceedings 19-21 years ago and which are still influential and stimulating for the field today. For the 2018 award, papers from ESA'97 to ESA'99 were considered. Bernard Chazelle's paper stands out as a classic in efficient data structure design and provides what is still an essential building block in the fastest-possible deterministic comparison-based minimum spanning tree algorithm.

The paper presents an ingenious data structure, the soft heap, which realizes an intricate compromise between what is possible (speed) and what is useful (accuracy). The soft heap is an approximate priority queue, in the sense that the items it returns are not necessarily items of minimum key. A soft heap is allowed to increase the keys of some, but not too many, of its items, to facilitate what Chazelle calls the "car-pooling equivalent of data structures". All soft heap operations take constant amortized time, given a desired level of accuracy. Soft heaps were devised by Chazelle to obtain a deterministic, comparison-based O(mα(m,n))-time algorithm for the fundamental minimum spanning tree problem. Twenty years on, this is still the fastest algorithm of its kind. Soft heaps were also used by Pettie and Ramachandran (2002) to obtain an optimal algorithm for the problem, i.e., with algorithmic complexity equal to its decision-tree complexity, albeit with an as yet unknown running time. The soft heaps paper has not aged over the years and continues to inspire as a fundamental achievement.

Award Committee: Giuseppe F. Italiano (Rome), Jan van Leeuwen (Utrecht), Uri Zwick (Tel Aviv)