BONN, Germany — The problem sounds like something a child could settle with a pencil: given a list of numbers, how many times must you compare two of them before you can be sure which one is in the middle? Computer scientists have known since 1973 that the answer grows in proportion to the length of the list. What they have not known, for 50 years, is the constant of proportionality, and on that constant hangs the speed of a great deal of software.
Hanna Steinbach, a 29-year-old postdoctoral researcher at the Max Planck Institute for Mathematics here, posted a 140-page paper to a preprint server on Oct. 3 claiming to have pinned it down. Her result, if it holds up, proves that no procedure can find the median of a list of n numbers with fewer than 2.5n comparisons in the worst case, matching a lower bound conjectured in 1976 by Dieter Kallenberg, a German mathematician who died in 2011 without seeing it settled.
“Everyone believed the number was 2.5. The best anyone could prove was about 2,” Dr. Steinbach said in her office, where the proof’s structure covers two whiteboards. “The gap between 2 and 2.5 does not sound like much. It was, as it turned out, 50 years wide.”
The question matters because finding a median, or more generally the k-th smallest element of a list, is a building block of sorting, statistics, and database queries performed trillions of times a day. The best known algorithms use just under 3n comparisons; Dr. Steinbach’s proof says that they can be improved by at most a sixth, and that any claim of a faster method must be wrong.
Her approach, colleagues say, is as notable as the result. Rather than tracking the comparisons directly, she represents each possible state of knowledge as a point in a geometric space and shows that an adversary choosing the numbers can always force the algorithm to travel a minimum distance. “She turned a counting problem into a geometry problem, and the geometry problem had a floor,” said Gerd Wittmann, a professor at the institute who was among the first to read the manuscript. “I have checked the central lemma three times. I keep hoping to find a mistake, because that would be more comfortable.”
The paper is now under review at a leading journal and is being scrutinized by a working group of about a dozen researchers in Germany, Israel, and the United States. Ayşe Demir, a theoretical computer scientist at Boğaziçi University in Istanbul who is part of the group, said a verdict could take a year. “A proof this long has many places to be wrong,” she said. “But the idea is beautiful, and beautiful ideas are usually right eventually, even if the first draft is not.”
Dr. Steinbach, who grew up in Leipzig and began working on the problem as a diversion during her doctorate, said she was not thinking about what came next. “I have been looking for the floor for six years,” she said. “I would like to stand on it for a while.”
A version of this article appears in print on Oct. 12, 2026, Section A, Page 13 of the European edition with the headline: A 29-Year-Old in Bonn Says She Has Settled a 50-Year-Old Question About Finding the Middle.
