Open Problems:15 - Revision history

Krzysztof Onak at 01:41, 7 March 2013

2013-03-07T01:41:31Z

Krzysztof Onak at 05:10, 16 November 2012

2012-11-16T05:10:33Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:50Z

1 revision

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 15: Semi-Random Streams}} {{Infobox |label1 = Proposed by |data1 = Andrew McGregor |label2 = Source |data2 = Kanpur 2006 |labe..."

2012-10-15T20:10:40Z

Created page with "{{DISPLAYTITLE:Problem 15: Semi-Random Streams}} {{Infobox |label1 = Proposed by |data1 = Andrew McGregor |label2 = Source |data2 = Kanpur 2006 |labe..."

New page

{{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 “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 {{cite|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 {{cite|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 {{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 “less-random” using either definition? For a given application, which notion is more appropriate? Are there other useful definitions for semi-random order?

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur06
 |who=Andrew McGregor

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 15: Semi-Random Streams}}
+{{Header
-{{Infobox
+|title=Semi-Random Streams
-|label1 = Proposed by
+|source=kanpur06
-|data1 = Andrew McGregor
+|who=Andrew McGregor
 }}
 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}}.

← Older revision	Revision as of 05:33, 8 November 2012
(No difference)