Lower bounds against weakly-uniform threshold circuits

Ruiwen Chen, Valentine Kabanets, and Jeff Kinne

Abstract

An ongoing line of research has shown super-polynomial lower bounds for uniform and slightly-non-uniform small-depth threshold and arithmetic circuits {Allender'99,Koiran&Perifel'09,Janson&Santhanam'11}. We give a unified framework that captures and improves each of the previous results. Our main results are that Permanent does not have threshold circuits of the following kinds:

  1. Depth $O(1)$, $n^{o(1)}$ bits of non-uniformity, and size $n^{O(1)}$.
  2. Depth $O(1)$, $polylog(n)$ bits of non-uniformity, and size $s(n)$ such that for all constants $c$ the $c$-fold composition of $s$, $s^{(c)}(n)$, is less than $2^n$.
  3. Depth $o(\log\log n)$, $polylog(n)$ bits of non-uniformity, and size $n^{O(1)}$.

Item 1 strengthens a result of Jansen and Santhanam, who obtained similar parameters but for arithmetic circuits of constant depth rather than Boolean threshold circuits. Items 2 and 3 strengthen results of Allender, and Koiran and Perifel, respectively, who obtained results with similar parameters but for completely uniform circuits.

Our main technical contribution is to simplify and unify earlier proofs in this area, and adapt the proofs to handle some amount of non-uniformity. We also develop a notion of circuits with a small amount of non-uniformity that naturally interpolates between fully uniform and fully non-uniform circuits. We use this notion, which we term weak uniformity, rather than the earlier and essentially equivalent notion of succinctness used by Jansen and Santhanam because the notion of weak uniformity more fully and easily interpolates between full uniformity and non-uniformity of circuits.

Keywords: advice complexity classes, alternating Turing machines, counting hierarchy, permanent, succinct circuits, threshold circuits, uniform circuit lower bounds, weakly-uniform circuits

Versions