11
votes
Accepted
How to show that the median cannot be maintained in $O(1)$ time?
If you can maintain the median of $n$ objects in $O(1)$, then you can sort a sequence $x_1, \dots, x_n$ in $O(n)$:
first you compute a value $a$ smaller than all elements in the sequence and a value $...
- 820
11
votes
Accepted
Complexity class of efficient streaming algorithms
Along with my comment above (noting that not even AC0 is in "StreamL"), let me say that that this class has been studied before; you just need to know what they used to call it.
Search for "one-way ...
- 27.7k
8
votes
Constraints on sliding windows
It seems it would depend on your particular model, in particular what information you have access to.
From what I infer, you are thinking of the following model:
you have a memory $m$, for instance ...
- 9,018
6
votes
Accepted
Constraints on sliding windows
Here is a second, simpler and more general answer that was obtained after discussing with a3nm.
Problem
We fix a regular language $\mathcal{L}$ and we are interested in the following word problem. ...
- 820
6
votes
Constraints on sliding windows
Context
Let $\mathcal{L}$ be a fixed regular language and let ($\mathcal{Q}, \Sigma, \delta, q_0, \mathcal{F})$ be an automaton recognizing $\mathcal{L}$.
I will suppose in this post that we are ...
- 820
4
votes
Constraints on sliding windows
This seems to be exactly the type of question studied by Moses Ganardi and
coauthors in recent years. In particular this paper and this extension
prove nice trichotomies.
- 349
3
votes
Sublinear finite-precision sampling in a stream
The strategy will be to use Vitter's algorithm, but replace the arbitrary-precision random number with online generation of the bits of that random number.
Building block: sampling without arbitrary ...
- 12.4k
1
vote
Finding top-K items in a sliding window
Your problem may be solved (perhaps with small modifications) by the algorithms TiTiCount, TiTiCount+ and TiTiCount+h. These are algorithms that allows you estimating the frequencies and finding ...
- 2,216
1
vote
Accepted
Reducing disjoint or indexing or inner-product problem to s-t connectivity problem in directed graph
Consider the communication problem INDEX where Alice has a $n$ bit string $x_1x_2x_3...x_n$ and Bob has an index $i \in [n]$ where Bob's goal is to learn whether the bit $i$ of $x$ is $1$ or not.
It'...
- 94
1
vote
Estimate the maximum frequency of substring with given length in a very long character stream
If $D$ has high min-entropy, then there's a "sharp cut-off" phenomenom: there's a value $l_0$ depending only on $n,B$ such that the value of $l$ is almost always very close to $l_0$, when $S$ is drawn ...
- 12.4k
1
vote
Accepted
Single-pass streaming quantile estimation using moments
Gan et al. address this in Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries. The answers are rather nuanced.
- 11.2k
Only top scored, non community-wiki answers of a minimum length are eligible