George Giakkoupis and Dimitrios Los from the WIDE team, jointly with Marcos Kiwi (Universidad de Chile), had their paper entitled “Naively Sorting Evolving Data is Optimal and Robust” accepted at FOCS 2024, one of the leading conferences in computer science!
In this paper, the authors study sorting in the evolving data model, where the true ordering of the data changes as the sorting algorithm is executing. The authors prove that a very simple algorithm which randomly samples an adjacent pair of elements and sorts them if they are out of order, achieves the optimal maximum and total deviation. Their analysis is applicable to variety of different settings, resolving several conjectures and open problems from previous works.
Some interactive visualisations of involved processes can be found here.
