In this paper we consider the problem of proving lower bounds for the permanent. An ongoing line of research has shown super-polynomial lower bounds for slightly-non-uniform small-depth threshold and arithmetic circuits [1,2,3,4]. We prove a new parameterized lower bound that includes each of the previous results as sub-cases. Our main result implies that the permanent does not have Boolean threshold circuits of the following kinds. 1. Depth O(1), poly-log(n) bits of non-uniformity, and size s(n) such that for all constants c, s~((c))(n) < 2~n. The size s must satisfy another technical condition that is true of functions normally dealt with (such as compositions of polynomials, logarithms, and exponentials). 2. Depth o(log log n), poly-log(n) bits of non-uniformity, and size n~(O~(1)). 3. Depth O(1), n~(o(1)) bits of non-uniformity, and size n~(O(1)). Our proof yields a new "either or" hardness result. One instantiation is that either NP does not have polynomial-size constant-depth threshold circuits that use n~(o(1)) bits of non-uniformity, or the permanent does not have polynomial-size general circuits.
展开▼
