Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
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 $...
Louis's user avatar
  • 775
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 ...
Ryan Williams's user avatar
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 ...
Denis's user avatar
  • 8,883
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. ...
Louis's user avatar
  • 775
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 ...
Louis's user avatar
  • 775
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.
Georg Zetzsche's user avatar
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 ...
D.W.'s user avatar
  • 12.1k
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 ...
Massimo Cafaro's user avatar
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'...
Rajat De's user avatar
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 ...
D.W.'s user avatar
  • 12.1k
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.
jbapple's user avatar
  • 11.2k

Only top scored, non community-wiki answers of a minimum length are eligible