Imre Simon Test-of-Time Award 2026

An article by Veli Mäkinen and Gonzalo Navarro from LATIN 2006 conference won the Imre Simon Test-of-Time Award 2026.
Result behind the award

The awarded article was published in LATIN 2006 under title "Position-Restricted Substring Search" and extended later into Theoretical Computer Science "Rank and Select Revisited and Extended". 

The main contribution of the article was to draw connections between results discovered in different subfields. For example, fractional cascading to speed-up geometric data structures was shown to be efficiently implementable with wavelet trees developed for string algorithms. Later research has benefited from these insights to e.g. cast known lower-bounds from the geometric setting to string algorithms.