In a 1985 paper, the pc scientist Andrew Yao, who would go on to win the A.M. Turing Award, asserted that amongst hash tables with a particular set of properties, the easiest way to search out a person component or an empty spot is to only undergo potential spots randomly—an strategy often called uniform probing. He additionally said that, within the worst-case situation, the place you’re looking for the final remaining open spot, you possibly can by no means do higher than x. For 40 years, most pc scientists assumed that Yao’s conjecture was true.
Krapivin was not held again by the traditional knowledge for the straightforward motive that he was unaware of it. “I did this with out understanding about Yao’s conjecture,” he mentioned. His explorations with tiny pointers led to a brand new form of hash desk—one which didn’t depend on uniform probing. And for this new hash desk, the time required for worst-case queries and insertions is proportional to (log x)2—far quicker than x. This end result instantly contradicted Yao’s conjecture. Farach-Colton and Kuszmaul helped Krapivin present that (log x)2 is the optimum, unbeatable sure for the favored class of hash tables Yao had written about.
“This result’s stunning in that it addresses and solves such a basic downside,” mentioned Guy Blelloch of Carnegie Mellon.
“It’s not simply that they disproved [Yao’s conjecture], in addition they discovered the very best reply to his query,” mentioned Sepehr Assadi of the College of Waterloo. “We may have gone one other 40 years earlier than we knew the proper reply.”
Along with refuting Yao’s conjecture, the brand new paper additionally comprises what many contemplate an much more astonishing end result. It pertains to a associated, although barely completely different, state of affairs: In 1985, Yao appeared not solely on the worst-case instances for queries, but in addition on the common time taken throughout all potential queries. He proved that hash tables with sure properties—together with these which can be labeled “grasping,” which implies that new components should be positioned within the first out there spot—may by no means obtain a mean time higher than log x.
Farach-Colton, Krapivin, and Kuszmaul needed to see if that very same restrict additionally utilized to non-greedy hash tables. They confirmed that it didn’t by offering a counterexample, a non-greedy hash desk with a mean question time that’s a lot, a lot better than log x. Actually, it doesn’t rely upon x in any respect. “You get a quantity,” Farach-Colton mentioned, “one thing that’s only a fixed and doesn’t rely upon how full the hash desk is.” The truth that you possibly can obtain a relentless common question time, whatever the hash desk’s fullness, was wholly sudden—even to the authors themselves.
The crew’s outcomes might not result in any instant functions, however that’s not all that issues, Conway mentioned. “It’s essential to grasp these sorts of information buildings higher. You don’t know when a end result like this may unlock one thing that allows you to do higher in observe.”
Original story reprinted with permission from Quanta Magazine, an editorially unbiased publication of the Simons Foundation whose mission is to reinforce public understanding of science by masking analysis developments and tendencies in arithmetic and the bodily and life sciences.
