Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-142 | 28th August 2015 19:45

A Compression Algorithm for $AC^0[\oplus]$ circuits using Certifying Polynomials


Authors: Srikanth Srinivasan
Publication: 28th August 2015 20:00
Downloads: 1780


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).

ISSN 1433-8092 | Imprint