Martin Farach-Colton and his Ph.D. student help find an almost-perfect solution to decades old “list-labeling” problem

In 1981, computer scientists began discussing what they term the “list-labeling” problem, also known as the “library-sorting” problem, since that analogy makes it easier to explain the matter to laypeople. Consider a librarian who must determine how best to arrange a shelf so that new books can be added efficiently. If there’s not enough of a gap left in the T section, for example, that newly acquired Tolstoy novel will be harder to place. And what happens after you’ve juggled things around, and the library acquires a volume by Anne Tyler; the juggling would start all over again. Strategically placed gaps would help, but how would that librarian even begin to predict where to place them.

That same issue applies to records arranged in a database or hard drive, and the authors of that 1981 paper began exploring algorithmic ways to make the process more efficient, since inefficiencies result in major computational costs, excessive energy use, and long lag times. It was a daunting task considering how many items comprise large datasets.

While much progress was made on variants of the problem — and in proving its intractability — over the years, little progress was made in improving the efficiency of algorithms that solve the general version of the problem. Martin Farach-Colton, Tandon’s Leonard J. Shustek Professor of Computer Science and Chair of the Department of Computer Science and Engineering, was confident that even better solutions could be found.

He first turned his attention to the list-labeling problem in 1999, returning to it from time to time every few years thereafter, in between other projects. “Luckily, I don’t mind tilting at windmills,” he explains. When Hanna Komlós began studying with him in 2020, she became a valued collaborator.

In 2024, the two — along with colleagues from Stony Brook University, Charles University in Prague, Carnegie Mellon, Cornell, and Rutgers — published “Nearly Optimal List Labeling,” which detailed their development of an algorithm that supports insertions and deletions while moving around elements within the array as little as possible.

“When we presented it at conferences, people were stunned, since no faster algorithm had been found for decades,” Komlós said, “just as stunned as we were to have finally found a nearly optimal solution.”

Their discovery, dubbed the “See-Saw Algorithm,” leveraged techniques from learning-augmented algorithms to analyze past organizational patterns and predict future needs, while using randomness to prevent overcompensation. So groundbreaking was their work — which closed the gap between the best-known upper and lower bounds of the problem (in other words, between the maximum possible time needed to insert a new datapoint and the fastest possible time) — that it was featured in a recent issue of the highly regarded magazine Quanta.

Now that theoretically, an ideal solution has been reached, what practical applications (aside from book-sorting) might be possible? “This is a foundational issue that arises a lot in computation and data storage,” Farach-Colton says. “Hanna will be earning her Ph.D. shortly, and she has a brilliant career ahead of her finding answers to that.”