Data Stream Algorithms via Expander Graphs

摘要

We present a simple way of designing deterministic algorithms for problems in the data stream model via lossless expander graphs. We illustrate this by considering two problems, namely, k-sparsity testing and estimating frequency of items.