Timeline for Complexity class of efficient streaming algorithms
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 17, 2020 at 9:38 | history | edited | CommunityBot |
Commonmark migration
|
|
| May 3, 2020 at 20:36 | history | edited | Hermann Gruber |
Added tag
|
|
| Apr 26, 2020 at 18:00 | history | tweeted | twitter.com/StackCSTheory/status/1254470312080674816 | ||
| Apr 25, 2020 at 0:48 | vote | accept | Caleb Stanford | ||
| Apr 24, 2020 at 22:38 | answer | added | Ryan Williams | timeline score: 11 | |
| Apr 24, 2020 at 7:23 | comment | added | Ryan Williams | Using the diajointness function (an AND of ORs) you can construct functions in NC1, even in AC0, that is not in StreamL (for communication complexity reasons). StreamL would be a very weak class indeed. | |
| Apr 24, 2020 at 2:47 | comment | added | polar_bear_cheese | I don't think there are many studies on this. It seems to me that for most purposes, we still study the one-way communication complexity which can be applied to proving lower bound for streaming algorithms. | |
| Apr 23, 2020 at 17:19 | history | asked | Caleb Stanford | CC BY-SA 4.0 |