A Uniform Circuit Lower Bound for the Permanent

Abstract

The authors show that uniform families of ACC circuits of subexponential size cannot compute the permanent function. This also implies similar lower bounds for certain sets in PP This is one of the very few examples of a lower bound in circuit complexity whose proof hinges on the uniformity condition; it is still unknown if there is any set in ${\operatorname{Ntime}}(2^{n^{O(1)} } )$ that does not have nonuniform ACC circuits.