International Acknowledgements: Paolo Ferragina, Full Professor of Computer Science, has been awarded the ESA Test-of-Time Award during the European Symposium on Algorithms (ESA 2024) for the significance and impact of his algorithmic research

New international acknowlegment for Paolo Ferragina, Full Professor of Computer Science at the Scuola Superiore Sant’Anna and member of the Department of Excellence L'EMbeDS, who has been awarded the prestigious “ESA Test-of-Time Award”, together with his colleague Giovanni Manzini, Full Professor of Computer Science at the University of Pisa, during the European Symposium on Algorithms (ESA 2024) held this year in London, a key international scientific event for algorithm researchers. The award has been given since 2015 to papers published approximately 20 years earlier in the Symposium proceedings that have played a significant role in the evolution of algorithmic research, inspiring considerable theoretical and engineering follow-up work, and accumulating a significant citation record, thus demonstrating their relevance over time.

For the 2023 edition, the award was given to two papers, the one edited by Ferragina and Manzini was published in 2002 and titled “Engineering a Lightweight Suffix Array Construction Algorithm”, where they designed a new space and time efficient algorithm for constructing the data structure known as the Suffix Array. This algorithm allows to compute the lexicographic sorting of all the suffixes of a given string using a limited amount of additional space and efficiently in time. The algorithm was based on a new deep–shallow sorting method that used 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 in time when the input string contained many repeated substrings. The work included an extensive experimental study demonstrating the practicality of the new approach. The award recognizes the paper for making a significant step towards the efficient solution of an important practical problem, bridging the gap between theory and practice, and having a widespread influence on subsequent research, paving the way for numerous other theoretical and engineering results with applications in various fields, including the most recent ones in Genomics and Generative AI.