welcome
Quanta Magazine

Quanta Magazine

Technology

Technology

Undergraduate Upends a 40-Year-Old Data Science Conjecture | Quanta Magazine

Quanta Magazine
Summary
Nutrition label

84% Informative

Andrew Krapivin invented a new kind of hash table, one that worked faster than expected.

The first hash tables date back to the early 1950s , and computer scientists have studied and used them ever since.

They’re designed to allow users to do exactly three things: search for an element, delete an element or insert one into an empty slot.

New paper refutes Yao ’s conjecture that, in the worst-case scenario, you can never do better than x.

In 1985 , Yao proved that hash tables with certain properties could never achieve an average time better than log x.

The new paper also contains what many consider an even more astonishing result: It doesn’t depend on x at all.

VR Score

89

Informative language

90

Neutral language

45

Article tone

informal

Language

English

Language complexity

42

Offensive language

not offensive

Hate speech

not hateful

Attention-grabbing headline

not detected

Known propaganda techniques

not detected

Time-value

long-living

Affiliate links

no affiliate links