@[email protected] to [email protected]English • 3 months agoA young computer scientist and two colleagues show that searches within data structures called hash tables can be much faster than previously deemed possible.www.quantamagazine.orgexternal-linkmessage-square17fedilinkarrow-up166arrow-down11cross-posted to: [email protected][email protected][email protected][email protected][email protected]
arrow-up165arrow-down1external-linkA young computer scientist and two colleagues show that searches within data structures called hash tables can be much faster than previously deemed possible.www.quantamagazine.org@[email protected] to [email protected]English • 3 months agomessage-square17fedilinkcross-posted to: [email protected][email protected][email protected][email protected][email protected]
minus-square@[email protected]linkfedilinkEnglish13•edit-23 months agoThis is very cool news. Would be nice if it had some details on the implementation though Time to read the paper I guess
minus-squarebrvslvrnstlinkfedilinkEnglish5•3 months agoAgreed, I figured they’d have at least some psuedocode but alas
minus-squaresp3ctr4llinkfedilinkEnglish6•3 months agoFor those in a rush: Initial paper outlining theorem (2021): https://arxiv.org/pdf/2111.12800 Paper that demonstrates and proves its validity (2025): https://arxiv.org/pdf/2501.02305 I tried a quick search, but I’m not seeing any public implementations that specifically mention or cite ‘Krapavin’ or ‘Tiny Pointers’ anywhere.
This is very cool news. Would be nice if it had some details on the implementation though
Time to read the paper I guess
Agreed, I figured they’d have at least some psuedocode but alas
For those in a rush:
Initial paper outlining theorem (2021):
https://arxiv.org/pdf/2111.12800
Paper that demonstrates and proves its validity (2025):
https://arxiv.org/pdf/2501.02305
I tried a quick search, but I’m not seeing any public implementations that specifically mention or cite ‘Krapavin’ or ‘Tiny Pointers’ anywhere.