A young computer scientist and two colleagues show that searches within data structures called hash tables can be much faster than previously deemed possible.
Here’s a link to the paper “Tiny Pointers” https://arxiv.org/pdf/2111.12800 those editors at Quantamagazine writes their summary in a strange fashion, for instance using x in stead of n which is normally used in computer science when talking about big O notation.
You are correct it’s an confusing article Quantamagazine have written, why do they start highlighting “Tiny Pointers” https://arxiv.org/pdf/2111.12800 when “Optimal Bounds for Open Addressing Without Reordering” https://arxiv.org/pdf/2501.02305 is the main paper, and it disproves part of Tiny Pointers.
Here’s a link to the paper “Tiny Pointers” https://arxiv.org/pdf/2111.12800 those editors at Quantamagazine writes their summary in a strange fashion, for instance using x in stead of n which is normally used in computer science when talking about big O notation.
This is the paper the article is about: https://arxiv.org/pdf/2501.02305
You are correct it’s an confusing article Quantamagazine have written, why do they start highlighting “Tiny Pointers” https://arxiv.org/pdf/2111.12800 when “Optimal Bounds for Open Addressing Without Reordering” https://arxiv.org/pdf/2501.02305 is the main paper, and it disproves part of Tiny Pointers.