Editing Open Problems:15

{{DISPLAYTITLE:Problem 15: Semi-Random Streams}}
{{Infobox
|label1 = Proposed by
|data1 = Andrew McGregor
|label2 = Source
|data2 = [[Workshops:Kanpur_2006|Kanpur 2006]]
|label3 = Short link
|data3 = http://sublinear.info/15
}}
What is the right notion of &ldquo;semi-random&rdquo; order streams? While streams are normally assumed to be ordered by some omnipotent adversary, there is a growing body of work in which the order of the stream is assumed to be chosen uniformly from the set of all possible orderings {{cite|MunroP-80|DemaineLM-02|GuhaMV-06|GuhaM-06|GuhaM-07|GuhaM-07a}}.
This &ldquo;full-random&rdquo; ordering is interesting as a form of average-case analysis or in a stochastic setting in which each element of the stream is an independent sample drawn from some fixed unknown distribution {{cite|GuhaM-07a}}. More generally, it would be interesting to develop algorithms whose performance degraded smoothly as the stream ordering became &ldquo;less-random.&rdquo; This begs the question of what it means to be &ldquo;semi-random.&rdquo; 

The following notions were recently proposed {{cite|GuhaM-06}}:
# ''$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.
# ''$\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.

How do these notions relate to each other? Can we develop algorithms whose performance degrades smoothly as the stream ordering becomes &ldquo;less-random&rdquo; using either definition? For a given application, which notion is more appropriate? Are there other useful definitions for semi-random order?