Open Problems:15

Proposed by	Andrew McGregor
Source	Kanpur 2006
Short link	http://sublinear.info/15

What is the right notion of “semi-random” 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 [MunroP-80,DemaineLM-02,GuhaMV-06,GuhaM-06,GuhaM-07,GuhaM-07a]. This “full-random” 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 [GuhaM-07a]. More generally, it would be interesting to develop algorithms whose performance degraded smoothly as the stream ordering became “less-random.” This begs the question of what it means to be “semi-random.”

The following notions were recently proposed [GuhaM-06]:

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.

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