in 1985 paperComputer Scientist Andrew YaoAM Turing Award winners argued that in a hashtable with a specific set of properties, the best way to find individual elements or empty spots is to randomly pass through potential spots, i.e., approach known as uniform research. He also stated that in the worst case scenario you are looking for the last remaining open spot, you can never do well. x. For 40 years, most computer scientists assumed that Yao’s guess was true.
Kurapivin was not hampered by conventional wisdom, simply because he didn’t know it. “I did this without knowing about Yao’s speculation,” he said. His exploration using his small pointer led to a new kind of hashtable. And for this new hashtable, the worst Kelly and time required for insertion is proportional to the log x))2– Fast x. This result was directly contradicted Yao’s speculation. Farach-Colton and Kuszmaul helped Krapivin show it (log x))2 It is an invincible bounce with a popular class of hashtables written by Yao.
“The results are beautiful in terms of addressing and solving these classic problems,” he said. Guy Brelock Carnegie Melon.
“It’s not just that they disprove it. [Yao’s conjecture]they found the best possible answer to his question.” Sepehr Assadi of the University of Waterloo. “We could have gone another 40 years ago before we knew the correct answer.”
In addition to rebutting Yao’s speculation, the new paper also includes what many consider to be even more surprising results. It relates to related, slightly different situations. In 1985, Yao considered not only the worst time of the query, but also the average time taken on all possible queries. He proved that a hash table with certain properties (a hash table containing ones labeled “greedy” means that new elements should be placed in the first available location. x.
Farach-Colton, Krapivin, and Kuszmaul wanted to see if the same restrictions apply to non-greedy hash tables as well. They showed that it was not to provide a counter-exam. Non-greedy hashtables with average query time are much better than logs. x. In fact, it’s not dependent x Totally. “You get the numbers,” said Falak Colton, “it’s just constant and doesn’t depend on how perfect the hashtable is.” The fact that constant average query time can be achieved regardless of the bloating of the hashtable was completely unexpected, even for the authors themselves.
Team results may not lead to immediate applications, but that’s not the only thing, Conway said. “It’s important to understand these types of data structures better. I don’t know when these outcomes will unlock something that you can actually do better.”
Original Story Reprinted with permission from Quanta Magazineeditorially independent publications of Simons Foundation Its mission is to enhance public understanding of science by covering research and development and trends in mathematics and physical sciences and life sciences.
