Editing Open Problems:28
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| Line 1: | Line 1: | ||
| β | {{ | + | {{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. | 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. | ||
