A Compression Algorithm for AC 0 ( ) circuits using Certifying Polynomials
Srikanth Srinivasan · Electronic colloquium on computational complexity · 2015
A recent work of Chen, Kabanets, Kolokolova, Shaltiel and Zuckerman (CCC 2014, Computational Complexity 2015) introduced the Compression problem for a classC of circuits, dened as follows. Given as input the truth table of a Boolean function