  In this paper we initiate the study of expander decompositions of a graph
$G=(V, E)$ in the streaming model of computation. The goal is to find a
partitioning $\mathcal{C}$ of vertices $V$ such that the subgraphs of $G$
induced by the clusters $C \in \mathcal{C}$ are good expanders, while the
number of intercluster edges is small. Expander decompositions are classically
constructed by a recursively applying balanced sparse cuts to the input graph.
In this paper we give the first implementation of such a recursive sparsest cut
process using small space in the dynamic streaming model.
  Our main algorithmic tool is a new type of cut sparsifier that we refer to as
a power cut sparsifier - it preserves cuts in any given vertex induced subgraph
(or, any cluster in a fixed partition of $V$) to within a $(\delta,
\epsilon)$-multiplicative/additive error with high probability. The power cut
sparsifier uses $\tilde{O}(n/\epsilon\delta)$ space and edges, which we show is
asymptotically tight up to polylogarithmic factors in $n$ for constant
$\delta$.

Data Structures and Algorithms