given a distribution D with a random rank ordering, a non-adversarialoracle would output a random rank ordering that is not necessarily the same as the rank orderingof D.
What on earth does this mean?
4 Matching Annotations
- Jun 2023
-
www.semanticscholar.org www.semanticscholar.org
-
-
Therefore, under a noisy oracle, the learned Treap is at most an additive constant worse than alearned Treap with a perfect oracle
Wouldn't each element have at most constant added? Doesn't this add O(N)?
-
Since the oracle is non-adversarial, the expected depth of any element is still bounded by2Hn − 1 by Theorem 3.1
This is because 2H_n - 1 is the expected depth of the Random Treap, this isn't a bound, it's an expectation
-
ˆri ≤ εr + δ for some constants ε, δ ≥ 1
Their bound on error is constant factor for scale and bias, can we do better with BTR?
-