## 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:

- Depth $O(1)$, $n^{o(1)}$ bits of non-uniformity, and size $n^{O(1)}$.
- 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$.
- 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

- journal version
*Algorithmica*, volume 70, issue 1, pages 47-75, 2014 {special COCOON'12 issue}. -
extended abstract
in
*Proceedings of the Eighteenth Annual International Computing and Combinatorics Conference 2012, COCOON'12*, pages 408-419, 2012. - early version ECCC-TR12-007.