5
$F_0$ counting (or estimating distinct elements, or "cardinality estimation") is very useful.
Example: when you're doing profiling at the router level, you often want to estimate functions of distinct IP addresses, and since you can't just maintain counters for each possible address, $F_0$ counting turns out to be quite useful.
$F_1$ counting, or ...
2
I don't know if there's a list of canonical hard problems, but there is a list of open problems in streaming as maintained by Andrew McGregor. This is not limited to the specific models you're referring to though.
2
This is not an answer but a method which I believe would leave to an improved lower bound. Let us cut the problem after $a$ letters are read. Denote the family of $a$ element sets of $[n]$ by $\mathcal A$ and the family of $b=k-a$ element sets of $[n]$ by $\mathcal B$. Denote the states that can be reach after reading the elements of $A$ (in any order) by $...
1
Gan et al. address this in Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries. The answers are rather nuanced.
1
The definition says that every edge that exists has to go from some $V_i$ to $V_{i+1}$. It doesn't say that every possible edge from $V_i$ to $V_{i+1}$ has to be there. For example, $V_1=\{a,b\}$, $V_2=\{c,d\}$ with edges $ac$ and $bd$ gives a disconnected graph.
Only top voted, non community-wiki answers of a minimum length are eligible
