Test-of-Time Award

The ESA Test-of-Time Award recognizes papers from ESA proceedings from 19-21 years prior that have best met the “test of time”. The winner is selected by a committee of three members appointed by the ESA Steering Committee. The prize may be shared by more than one paper, and the Award Committee reserves the right to declare no winner at all.

ESA Test-of-Time Award 2023

The award committee selected the following papers for the ESA ToTA 2023. The papers stand out for their impact in the algorithms field that also inspired important follow-up work, and by their significant citation record which shows that the papers are still relevant today.

Raphael Yuster, Uri Zwick: Fast Sparse Matrix Multiplication. In ESA 2004, pp. 604-615. Also, in ACM Transactions on Algorithms 1(1):2-13, 2005.

The paper studies the fundamental problem of computing the product of two n x n sparse matrices over a ring R, where each matrix contains at most m non-zero elements. It presents a new algorithm that, for certain values of m, multiplies the two matrices using an almost optimal or faster number of algebraic operations over R compared to best-known algorithms. The paper introduces a new way of partitioning the matrices into a dense and a sparse part that influenced subsequent work and can be used to improve the bounds of multiplying more than just two matrices.

Giovanni Manzini, Paolo Ferragina: Engineering a Lightweight Suffix Array Construction Algorithm. In ESA 2002, pp. 698-710. Also, in Algorithmica 40:33–50, 2004.

The paper provides a new algorithm for computing the suffix array of a string (lexicographically sorting all the suffixes of the given string). The new algorithm is lightweight (uses very small additional space to that required by the suffix array) and is based on a new deep–shallow sorting method that uses a “shallow” sorter for suffixes with a short common prefix, and a “deep” sorter for suffixes with a long common prefix. This new key idea allowed to overcome the drawbacks of previous approaches that either required a large amount of space or were inefficient when the input string contained many repeated substrings. The work included an extensive experimental study that demonstrated the practicality of the new approach. It constitutes a significant step forward towards (i) the efficient solution of an important practical problem, (ii) bridging the gap between theory and practice, and (iii) influencing subsequent work.

Award Committee: Christos Zaroliagis, Andrew Goldberg, Susanne Albers

ESA Test-of-Time Award 2022

The award committee selected the following papers for the ESA ToTA 2022. The papers stand out for their impact in the algorithms field that also inspired significant follow-up work, and by their excellent citation record which shows that the papers are still relevant today.

Marianne Durand, Philippe Flajolet: Loglog Counting of Large Cardinalities (Extended Abstract). In ESA 2003, pp. 605-617.

The paper studies the problem of approximately counting the number (cardinality) of distinct elements in a large dataset. It presents a very efficient probabilistic approach that computes an estimate with a small relative error via a single pass over the input that uses very little auxiliary memory (a small number of words of log log N bits each, where N is the maximum possible cardinality). Since this is the size needed to represent the answer, this asymptotic dependence is optimal. The work included an empirical evaluation that demonstrates the practicality of the new approach. The paper introduced key new ideas that laid the foundations to subsequent research work on double-logarithmic size sketches and to implementations with a profound impact and widespread use in industry.

Ulrik Brandes, Marco Gaertler, Dorothea Wagner: Experiments on Graph Clustering Algorithms. In ESA 2003, pp. 568-579.

The paper provides a thorough analysis of indices that formalize the relation between the number of intra- and inter-cluster edges for measuring the quality of graph clustering, for which there was no conclusive algorithmic evaluation. The paper proposed a new heuristic and experimentally evaluated it against two other theoretically grounded algorithms, making a significant step forward towards the efficient solution of an important practical problem, as well as bridging the gap between theory and practice. Beyond its particular contribution, this paper influenced subsequent work by broadening the scope and refining the methodology of modern experimental evaluation of algorithms.

Award Committee: Edith Cohen, Christos Zaroliagis, Andrew Goldberg

ESA Test-of-Time Award 2021

The award committee selected the following two papers for the ESA ToTA 2021.

Andrew Goldberg, Jason Hartline:
Competitive Auctions for Multiple Digital Goods
Proceedings ESA’01

The paper is part of a foundational line of work by the authors on designing auctions for digital goods, which are goods such as software, music, and videos that are in unlimited supply. The work focuses on competitive auctions that encourage consumers to bid their utility values by providing yield revenue within a constant factor of the optimal fixed pricing. The paper initiates a study of the important case of multiple digital goods and extends on prior work focused on a single digital good.

Giuseppe Lancia, Vineet Bafna, Sorin Istrail, Ross Lippert, and Russell Schwartz:
SNPs Problems, Complexity, and Algorithms
Proceedings ESA’01

This paper contributed to foundational work of understanding emerging problems in genetics through the computational lens. Single nucleotide polymorphisms (SNPs) are the most frequent form of human genetic variation. They are of fundamental importance in medical diagnostic, drug design, and are a fingerprint of disease genes. This work studied problems related to computational SNPs validation based on genome assemblies of diploid organisms (those with two copies of each chromosome) and presented both hardness results and efficient algorithms, using graph modeling.

Award Committee: Samir Khuller, Edith Cohen, Christos Zaroliagis

ESA Test-of-Time Award 2020

The 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 2019 Award, papers from ESA 1999 to ESA 2001 were considered. Because WAE merged in with ESA, the Steering Committee decided that the papers from WAE 1999 to WAE 2001 were also to be considered.

The award committee selected the following paper for the ESA ToTA 2020. The paper stands out for its rare combination of simplicity and elegance and has become a textbook classic with significant followup work and practical use.

Rasmus Pagh, Flemming Friche Rodler
Cuckoo Hashing
Proceedings of ESA 2001, pp. 121-133
Appeared also in J. Algorithms 41(2): 122-144 (2004)

The paper on Cuckoo Hashing by Rasmus Pagh and Flemming Friche Rodler addresses the fundamental problem of designing an efficient data structure that supports key lookups under insertions and deletions. The Cuckoo Hashing design facilitates lookup and deletion of keys in worst-case constant time and insertions of keys in expected constant time. With its rare combination of simplicity and elegance, the work has been highly influential both in theory and in practice. In the two decades since its introduction in ESA 2001, the data structure has become a textbook classic and initiated significant followup work with well over a thousand citations. Cuckoo hashing and its variations are broadly implemented and used in critical applications that require small worst-case lookup times, such as computation on Graphic Processing Units (GPUs) or internet routing.

Award Committee: Uri Zwick, Samir Khuller, Edith Cohen

ESA Test-of-Time Award 2019

The 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 2019 Award, papers from ESA 1998 to ESA 2000 were considered. Because WAE merged in with ESA, the Steering Committee decided that the papers from WAE 1998 to WAE 2000 were also to be considered.

The award committee selected the following paper for the ESA ToTA 2019. The paper stands for its impact in the design of efficient parallel algorithms for shortest path problems.

Ulrich Meyer, Peter Sanders
Delta-Stepping: A Parallel Single Source Shortest Path Algorithm.
Proceedings of ESA 1998, pp. 393-404.
Appeared also in J. Algorithms 49(1): 114-152 (2003)

The paper presents an ingenious algorithm, dubbed Delta-stepping, for the Single-Source Shortest Path Problem (SSSP). This problem is well understood in the sequential setting (i.e., Dijkstra’s algorithm) but its ubiquitous applications call for efficient parallelizations. Most of the sequential SSSP algorithms are based either on label-setting or on label-correcting methods. Label-setting algorithms, like Dijkstra’s algorithm, settle at each iteration the distance label of one vertex. Label-correcting algorithms work instead by relaxing edges incident to unsettled vertices: all labels are temporary until the final step, when they all become permanent. In spite of the great practical performance of label-correcting methods, label-setting algorithms have been known to be asymptotically superior. In their paper, Meyer and Sanders show how to fill this gap by presenting Delta-stepping, a new label-correcting algorithm for SSSP which runs in optimal linear time with high probability for a large class of graphs with random edge weights. They further provide an efficient parallel implementation of their Delta-stepping algorithm, which has been a reference method and has inspired much subsequent work in parallel algorithms for many years.

Award Committee: Giuseppe F. Italiano, Uri Zwick, Samir Khuller

ESA Test-of-Time Award 2018

The 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. Because WAE merged in with ESA, the Steering Committee decided that the papers from WAE’97 to WAE’99 were also to be considered.

The award committee selected the following paper for the ESA ToTA 2018. The 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.

Bernard Chazelle
Car-Pooling as a Data Structuring Device: The Soft Heap
Proceedings ESA’98, pp. 35-42, also in: Journal of the ACM 47(6): 1012-1027 (2000)

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)

ESA Test-of-Time Award 2017

The award committee selected the following paper for the ESA ToTA 2017. The paper stands out as a classic in the algorithms field and continues to be cited as an exemplary study in its field.

James Abello, Adam L. Buchsbaum, and Jeffery R. Westbrook
A Functional Approach to External Graph Algorithms
Proceedings ESA’98, pp. 332-343, also in: Algorithmica 32 (2002) 437-458

The paper deals with the design of algorithms that operate on massive data sets in external memory. Building on the well-known I/O model of complexity by Aggarwal and Vitter, the authors introduce a novel design principle for external algorithms based purely on functional transformations of the data, which facilitates standard checkpointing and program optimization techniques. Illustrated on a variety of graph problems, their approach is proved to be elegant and versatile in the design of both deterministic and randomized external algorithms while the resulting I/O complexities remain competitive. Functional algorithms are also designed for semi-external problems, in which the nodes fit in main memory but the connecting edges are abundant and only available in external memory. The paper is an excellent illustration of how general principles of functional program design and model-based complexity can remain in harmony in the field of external algorithms.

Award Committee: Giuseppe F. Italiano (Rome), Mike Paterson (Warwick), Jan van Leeuwen (Utrecht)

ESA Test-of-Time Award 2016

The ESA Test-of-Time Award (ESA 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. In this second year in which the award is given, papers from ESA’95 to ESA’97 were considered.

The award committee selected the following paper for the ESA ToTA 2016. The paper stands out as a classic in the algorithms field and by its excellent citation record still relevant today.

From ESA 95-97:

Boris V. Cherkassky, Andrew V. Goldberg:
Negative-cycle detection algorithms
Proceedings ESA’96, also in: Mathematical Programming 85:2 (1999) 277-311

The paper by Cherkassky and Goldberg deals with the problem of finding a negative-length cycle in a network or proving that there is none. Algorithms for this are a combination of a shortest-path algorithm and a negative-cycle detection strategy. The authors analyse known algorithms and some new ones and determine the best combinations. Novel instance generators are used in this study. The paper is a model experimental paper in algorithms. Award Committee: Kurt Mehlhorn (Saarbrucken), Mike Paterson (Warwick), and Jan van Leeuwen (Utrecht)

ESA Test-of-Time Award 2015

The ESA Test-of-Time Award (ESA ToTA) recognizes outstanding 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. Exceptionally, in this first year in which award is given, the ESA ToTA 2015 committee was asked to consider all qualifying papers from ESA 93-95 and ESA 94-96, respectively.

The award committee selected the following two papers for the ESA ToTA 2015. The papers stand out for their impact and wide use in the algorithms field, and for their excellent citation records up to the present day.

From ESA 93-95:

Mechthild Stoer, Frank Wagner:
A Simple Min Cut Algorithm
Proceedings ESA’94, also in: JACM 44:4 (1997) 585-591

The minimum cut problem in graphs is a basic problem in network analysis and is needed, for example, as the separation routine in branch-and-cut algorithms for the Traveling Salesman problem. Stoer and Wagner gave an elegant and efficient algorithm for the problem that avoids the computation of maximum flows, building upon previous work by Nagamochi and Ibaraki. The same algorithm was independently found by Frank. The algorithm continues to be taught because of its elegance and used because of its efficiency and ease of implementation.

From ESA 94-96:

Sudipto Guha, Samir Khuller:
Approximation Algorithms for Connected Dominating Sets
Proceedings ESA’96, also in: Algorithmica 20:4 (1998) 374-387

It is natural to require connectedness as an additional constraint for a dominating set, for example, in ad hoc wireless networks. Domination guarantees coverage and connectedness guarantees communication between the selected nodes. Guha and Khuller gave polynomial algorithms for a logarithmic-factor approximation to its solution. Under the usual assumptions, this is the best possible. Their much-cited work has stimulated similar research for connected variants of many other graph problems. Award Committee: Jan van Leeuwen, Kurt Mehlhorn and Mike Paterson

Guidelines for the ESA Test-of-Time Award

The ESA Test-of-Time Award would like to recognize paper(s) from ESA Procs. from 19-21 years prior (i.e., in year X papers from Procs. ESA X-21, ESA X-20, ESA X-19 are considered) that have best met the “test of time”. Only for the first year, the ESA Test-of-Time Award 2015 considered papers from Procs. ESA 1993, ESA 1994, ESA 1995, ESA 1996.

The winner of the ESA Test-of-Time Award is selected by a committee of three members, appointed by the ESA Steering Committee. The prize may be shared by more than one paper, and the Award Committee reserves the right to declare no winner at all.

All papers from given years are eligible for the award, except those that are authored or co-authored by members of the Awards Committee. Although the Award Committee is encouraged to consult with the theoretical computer science community at large, the Award Committee is solely responsible for the selection of the winner of the award. All matters relating to the selection process that are not specified here are left to the discretion of the Award Committee.