A recent work of Chen, Kabanets, Kolokolova, Shaltiel and Zuckerman (CCC 2014, Computational Complexity 2015) introduced the Compression problem for a class $\mathcal{C}$ of circuits, defined as follows. Given as input the truth table of a Boolean function $f:\{0,1\}^n \rightarrow \{0,1\}$ that has a small (say size $s$) circuit from $\mathcal{C}$, find in time $2^{O(n)}$ \emph{any} Boolean circuit for $f$ of size less than trivial, i.e. much smaller than $2^n/n$.

The work of Chen et al. gave compression algorithms for many classes of circuits including $AC^0$ (the class of constant-depth unbounded fan-in circuits made up of AND, OR, and NOT gates) and Boolean formulas of size nearly $n^2$. They asked if similar results can be obtained for the circuit class $AC^0[\oplus]$, the class of circuits obtained by augmenting $AC^0$ with unbounded fan-in parity gates.

We answer the question positively here, using techniques from work of Kopparty and the author (FSTTCS 2012).