"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.
Quicksort, mergesort and heapsort are commonly analyzed with worst case / adversaries based decisions.
I know that binary trees (especially red-black trees, AVL trees and other self balancing trees) have huge studies into adversaries picking the worse case scenario.
And finally, error correction coding schemes / hamming distances and other data reliability (ex: CRC32 checks) have proofs based on the worst case adversary bounds.
-------
If anything, I'm struggling to think of a case where the adversary / worst case performance is NOT analyzed. In many cases, worst case bounds are easier to prove than average case... So I'd assume most people start with worst case analysis before moving to average case analysis
For some types of problems, identifying worst-case behavior is straightforward. For example, in a hash table lookup the worst-case is when all keys hash to the same value. To me, it seems like overkill to think in terms of an intelligent adversary in that case.
But in the problem described here, the worst-case is harder to construct. Especially while exploring the solution space given that slight tweaks to the solution can significantly change the nature of the worst-case. Thinking of it as adversarial implies thinking in terms of algorithms that dynamically produce the worst-case rather than trying to just identify a static worst-case that is specific to one solution. I can imagine that approach significantly speeding up the search for more optimal solutions.
I think _technically_ there is no difference - it does not matter if the worst-case-behavior is triggered by an "adversary" or by chance.
It _does_ give a different mental model though.
I think your statement makes sense for say, Quicksort or simple Binary Trees. In this case, the worst-case scenario is a "simple" reversed list. (ex: sorting [5 4 3 2 1] into [1 2 3 4 5]).
The worst-case insertion into an AVL-balanced tree however is a "Fibonacci Tree". AVL trees have a strange property where sorted lists [1 2 3 4 5 6 7] or [7 6 5 4 3 2 1] actually leads to optimal balancing. The sequence for worst case insertion into AVL Tree is something like [1 2 3 4 5 1.5 6] (1.5 to prevent the far-left tree from being perfectly balanced, and then 6 further unbalances the far-right branches)
Some algorithms have very non-intuitive worst-case scenarios.
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.
Adjacent to this topic is algorithms for two-player games, like minimax, which depend on imagining an adversary that plays perfect counter moves.
In a similar vein, in ML, there is a model called generative adversarial networks (GANs) in which 2 networks (a generator and discriminator) play a minimax game against each other, improving the capability of both models at once.
Here is a 2011 article about DOS attacks against web apps enable by hash table-based dicts: https://www.securityweek.com/hash-table-collision-attacks-co...
djb has long advocated “crit bit trees”, ie tries: https://cr.yp.to/critbit.html
Oh jeez now I have to read the rest.
More people need to read Blellochs PH.D Thesis. Vector models for data-parallel computing. It's a mind blowing way to think of parallel computation.
This is perhaps one of the best parallel programming / parallel data structures professors on the planet.
------
Awwww it's not so much about Blellochs work but I steady he's probably the guy ACM had to help explain and understand this new paper on the Bookshelf problem. Still great read though, but I was hoping for some crazy parallel programming application here.
skeeter2020•7mo ago
frutiger•7mo ago