Open Problems:28 - Revision history

Krzysztof Onak: updated header

2013-03-07T01:50:41Z

updated header

Krzysztof Onak at 05:24, 16 November 2012

2012-11-16T05:24:06Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:51Z

1 revision

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 28: Randomness of Partially Random Streams}} {{Infobox |label1 = Proposed by |data1 = Sudipto Guha |label2 = Source |data2 = [[Workshops:Kanpur_2009|Kan..."

2012-10-19T15:07:18Z

Created page with "{{DISPLAYTITLE:Problem 28: Randomness of Partially Random Streams}} {{Infobox |label1 = Proposed by |data1 = Sudipto Guha |label2 = Source |data2 = [[Workshops:Kanpur_2009|Kan..."

New page

{{DISPLAYTITLE:Problem 28: Randomness of Partially Random Streams}}
{{Infobox
|label1 = Proposed by
|data1 = Sudipto Guha
|label2 = Source
|data2 = [[Workshops:Kanpur_2009|Kanpur 2009]]
|label3 = Short link
|data3 = http://sublinear.info/28
}}
Many streaming algorithms are designed for worst-case inputs and the first step of analysis is conducted using truly random hash functions, which in the second step are replaced by hash functions that can be described using a small number of truly random bits. In practice, the input stream is often a result of some random process. Mitzenmacher and Vadhan {{cite|MitzenmacherV-08}} show that as long as it has sufficiently large entropy, hash functions from a restricted family are essentially as good as truly hash functions. On a related note, Gabizon and Hassidim {{cite|GabizonH-10}} show that algorithms for random-order streams need essentially no additional entropy apart from what can be extracted from the input.

In these two cases, the input can be seen as a source of randomness for the algorithm. How can one quantify the randomness of the stream in a natural way? For instance, Mitzenmacher and Vadhan set a lower bound for the Renyi entropy of each element of the stream, conditioned on the previous elements of the stream. Are there measures that are likely to be useful in practice and that are possible to verify?

Once we fix a measure of randomness, how much randomness according to this measure is necessary to derandomize or simplify specific streaming algorithms?

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur09
 |who=Sudipto Guha

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 28: Randomness of Partially Random Streams}}
+{{Header
-{{Infobox
+|title=Randomness of Partially Random Streams
-|label1 = Proposed by
+|source=kanpur09
-|data1 = Sudipto Guha
+|who=Sudipto Guha
 }}
 Many streaming algorithms are designed for worst-case inputs and the first step of analysis is conducted using truly random hash functions, which in the second step are replaced by hash functions that can be described using a small number of truly random bits. In practice, the input stream is often a result of some random process. Mitzenmacher and Vadhan {{cite|MitzenmacherV-08}} show that as long as it has sufficiently large entropy, hash functions from a restricted family are essentially as good as truly hash functions. On a related note, Gabizon and Hassidim {{cite|GabizonH-10}} show that algorithms for random-order streams need essentially no additional entropy apart from what can be extracted from the input.

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