<p>Another tool are $\epsilon$-biased spaces, used e.g., in</p>

<p><em>J. Feldman, S. Muthukrishnan, A. Sidiropoulos, C. Stein, Z. Svitkina, "On Distributing Symmetric Streaming Computations", SODA 2008.</em></p>

CC BY-SA 2.5
2010-08-26T03:13:14.077Z
2010-08-26T03:13:14.077Z
Piotr
<p>In many geometric algorithms random sampling can be replaced by ε-nets and ε-approximations (of some appropriate range space with finite VC dimension) and these can be maintained efficiently by a streaming algorithm — see my paper "Deterministic Sampling and Range Counting in Geometric Data Streams" with Bagchi, Chaudhari, and Goodrich from SoCG 2004 and <a href="http://doi.acm.org/10.1145/1240233.1240239" rel="nofollow">ACM Trans. Alg. 2007</a>.</p>

CC BY-SA 2.5
2010-08-26T04:12:59.990Z
yes, that's another good example. I forgot about that.
Suresh Venkat
CC BY-SA 2.5
2010-08-26T02:26:10.690Z
2010-08-26T02:26:10.690Z
David Eppstein
<p>Some streaming algorithms use expander graphs. This is a somewhat extreme form of de-randomization though (no random bits, in principle).</p>

CC BY-SA 2.5
2010-08-26T01:30:37.680Z
Do you have a reference for such examples ?
Suresh Venkat
CC BY-SA 2.5
2010-08-26T02:42:31.810Z
One such reference is: S. Ganguly, "Data stream algorithms via expander graphs",  ISAAC 2008. There are also several algorithms for sparse recovery (a closely related problem) that use expander matrices. See the following survey for an overview:
A. Gilbert, P. Indyk, "Sparse recovery using sparse matrices", Proceedings of IEEE, 2010.
Piotr
CC BY-SA 2.5
2010-08-25T23:35:33.107Z
2010-08-25T23:35:33.107Z
Piotr
<p>Stream algorithms require randomization for the most part to do anything nontrivial, and because of the small-space constraint, need PRGs that use little space. I know of two methods that have been cited for use in stream algorithms thus far:</p>

<ul>
<li>$k$-wise independent PRGs like the 4-wise independent family used by Alon/Matias/Szegedy for the original $F_2$ estimation problem, and generalizations for 2-stability-based methods for (say) $\ell_2$ sketching</li>
<li>Nisan's PRG that works in general for any kind of small-space problem.</li>
</ul>

<p>I'm particular interested in methods that can be implemented. On the face of it, both of the above approaches seem relatively easy to implement, but I'm curious if there are any others out there. </p>

<ds.algorithms><derandomization><streaming><pseudorandom-generators>
Streaming derandomization
Suresh Venkat
# Streaming derandomization

(Asked by: username_0 on 2010-08-25)

Stream algorithms require randomization for the most part to do anything nontrivial, and because of the small-space constraint, need PRGs that use little space. I know of two methods that have been cited for use in stream algorithms thus far:

* $k$-wise independent PRGs like the 4-wise independent family used by Alon/Matias/Szegedy for the original $F\_2$ estimation problem, and generalizations for 2-stability-based methods for (say) $\ell\_2$ sketching
* Nisan's PRG that works in general for any kind of small-space problem.

I'm particular interested in methods that can be implemented. On the face of it, both of the above approaches seem relatively easy to implement, but I'm curious if there are any others out there.

**Tags:** ds.algorithms, derandomization, streaming, pseudorandom-generators

---

## 3 answers

### Answer by username_1 on 2010-08-25. Score: 10 | Accepted answer

Some streaming algorithms use expander graphs. This is a somewhat extreme form of de-randomization though (no random bits, in principle).

> **Comments:**
> **username_0**: Do you have a reference for such examples ?  
> **username_1**: One such reference is: S. Ganguly, "Data stream algorithms via expander graphs",  ISAAC 2008. There are also several algorithms for sparse recovery (a closely related problem) that use expander matrices. See the following survey for an overview: A. Gilbert, P. Indyk, "Sparse recovery using sparse matrices", Proceedings of IEEE, 2010.  

---

### Answer by username_1 on 2010-08-26. Score: 6

Another tool are $\epsilon$-biased spaces, used e.g., in

*J. Feldman, S. Muthukrishnan, A. Sidiropoulos, C. Stein, Z. Svitkina, "On Distributing Symmetric Streaming Computations", SODA 2008.*


---

### Answer by username_2 on 2010-08-26. Score: 6

In many geometric algorithms random sampling can be replaced by ε-nets and ε-approximations (of some appropriate range space with finite VC dimension) and these can be maintained efficiently by a streaming algorithm — see my paper "Deterministic Sampling and Range Counting in Geometric Data Streams" with Bagchi, Chaudhari, and Goodrich from SoCG 2004 and [ACM Trans. Alg. 2007](http://doi.acm.org/10.1145/1240233.1240239).

> **Comments:**
> **username_0**: yes, that's another good example. I forgot about that.  

---

