Abstract
A recent work of Chen, Kabanets, Kolokolova, Shaltiel and Zuckerman (CCC 2014, Computational Complexity 2015) introduced the notion of the Compression problem for a class 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 C, find in time 2^{O(n)} 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[p], the class of circuits obtained by augmenting AC^0 with unbounded fan-in MOD_p gates.
We answer the question positively, using techniques from work of Kopparty and the author (FSTTCS 2012).