←back to thread

An Algorithm for a Better Bookshelf

(cacm.acm.org)
114 points pseudolus | 1 comments | 01 Jul 25 10:12 UTC | HN request time: 0.272s | source
Show context
jasonthorsness ◴[03 Jul 25 20:48 UTC] No.44459044[source]▶
"Their new algorithm adapts to an adversary’s strategy, but on time scales that it picks randomly"

"Even though many real-world data settings are not adversarial, situations without an adversary can still sometimes involve sudden floods of data to targeted spots, she noted."

This is pretty neat. I bet this will find practical applications.

replies(2): >>44459183 #>>44459434 #
troelsSteegin ◴[03 Jul 25 21:45 UTC] No.44459434[source]▶
Are "adversaries" broadly used in algorithm design? I've not seen that before. I'm used to edge cases and trying to break things, but an "adversary", especially white box, seems different.
replies(4): >>44459936 #>>44460066 #>>44460159 #>>44461092 #
1. o11c ◴[03 Jul 25 23:48 UTC] No.44460066[source]▶
It really depends on the particular group of algorithms. I'm only considering non-cryptographic algorithms here.

As a general rule, any algorithm that involves a hash or a random/arbitrary choice has historically been based on "assume no adversary" and even now it has only advanced to "assume an incompetent adversary".

By contrast, most tree-adjacent algorithms have always been vigilant against competent adversaries.