# Problem 15: Semi-Random Streams

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
1. $t$-Bounded-Adversary-Random: A $t$-bounded adversary is a space-bounded adversary that can delay at most $t$ elements at a time, i.e., can transform a stream $\langle x_1, \ldots, x_m \rangle$ into a stream of the form $\langle x_{\sigma(1)}, \ldots x_{\sigma(m)}\rangle$ if the permutation $\sigma$ satisfies,$$\forall i\in [m], \ |\{j\in [m]: j<i \mbox{ and } \sigma(i)<\sigma(j)\}|\leq t \enspace .$$The order of a stream is $t$-bounded-adversary-random if it is generated by a $t$-bounded adversary acting on a stream whose order is random.
2. $\epsilon$-Generated-Random: Consider a set of elements $\{x_1,\ldots, x_m\}$. Then a permutation $\sigma$ defines a stream $\langle x_{\sigma(1)},\ldots, x_{\sigma(m)}\rangle$. We say the ordering of this stream is $\epsilon$-Generated Random if $\sigma$ is chosen according to some distribution $\nu$ such that $\|\mu-\nu\|_1\leq \epsilon$, where $\mu$ is the uniform distribution over all possible orderings.