A family of Boolean circuits $\{C_n\}_{n\geq 0}$ is called \emph{$\gamma(n)$-weakly uniform} if
there is a polynomial-time algorithm for deciding the direct-connection language of every $C_n$,
given \emph{advice} of size $\gamma(n)$. This is a relaxation of the usual notion of uniformity, which allows one
to interpolate between complete uniformity (when $\gamma(n)=0$) and complete non-uniformity (when $\gamma(n)> |C_n|$).
Weak uniformity is essentially equivalent to \emph{succinctness}
introduced by Jansen and Santhanam~\cite{JS11}.

Our main result is that \Perm is not computable by polynomial-size
$n^{o(1)}$-weakly uniform $\TC^0$ circuits. This strengthens the
results by Allender~\cite{All99} (for \emph{uniform} $\TC^0$) and by
Jansen and Santhanam~\cite{JS11} (for weakly uniform \emph{arithmetic}
circuits of constant depth).
Our approach is quite general, and can be used to extend to the
``weakly uniform'' setting all currently known circuit lower bounds
proved for the ``uniform'' setting. For example, we show that \Perm is
not computable by polynomial-size $(\log n)^{O(1)}$-weakly uniform
threshold circuits of depth $o(\log\log n)$, generalizing the result
by Koiran and Perifel~\cite{KP09}.

merged with a COCOON paper by Jeff Kinne who had similar results with a different proof.

A family of Boolean circuits $\{C_n\}_{n\geq 0}$ is called \emph{$\gamma(n)$-weakly uniform} if
there is a polynomial-time algorithm for deciding the direct-connection language of every $C_n$,
given \emph{advice} of size $\gamma(n)$. This is a relaxation of the usual notion of uniformity, which allows one
to interpolate between complete uniformity (when $\gamma(n)=0$) and complete non-uniformity (when $\gamma(n)> |C_n|$).
Weak uniformity is essentially equivalent to \emph{succinctness}
introduced by Jansen and Santhanam~\cite{JS11}.

Our main result is that \Perm is not computable by polynomial-size
$n^{o(1)}$-weakly uniform $\TC^0$ circuits. This strengthens the
results by Allender~\cite{All99} (for \emph{uniform} $\TC^0$) and by
Jansen and Santhanam~\cite{JS11} (for weakly uniform \emph{arithmetic}
circuits of constant depth).
Our approach is quite general, and can be used to extend to the
``weakly uniform'' setting all currently known circuit lower bounds
proved for the ``uniform'' setting. For example, we show that \Perm is
not computable by polynomial-size $(\log n)^{O(1)}$-weakly uniform
threshold circuits of depth $o(\log\log n)$, generalizing the result
by Koiran and Perifel~\cite{KP09}.