We present an algorithm, Parallel-$\ell_0$, for {\em combinatorial compressed sensing} (CCS), where the sensing matrix $A \in \mathbb{R}^{m\times n}$ is the adjacency matrix of an expander graph. The information preserving nature of expander graphs allow the proposed algorithm to provably recover a $k$-sparse vector $x\in\mathbb{R}^n$ from $m = \mathcal{O}(k \log (n/k))$ measurements $y = Ax$ via $\mathcal{O}(\log k)$ simple and parallelizable iterations when the non-zeros in the support of the signal form a dissociated set, meaning that all of the $2^k$ subset sums of the support of $x$ are pairwise different. In addition to the low computational cost, Parallel-$\ell_0$ is observed to be able to recover vectors with $k$ substantially larger than previous CCS algorithms, and even higher than $\ell_1$-regularization when the number of measurements is significantly smaller than the vector length.
