Revision #1 Authors: Ruiwen Chen, Valentine Kabanets, Jeff Kinne

Accepted on: 24th October 2012 20:11

Downloads: 2122

Keywords:

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.

TR12-007 Authors: Ruiwen Chen, Valentine Kabanets

Publication: 28th January 2012 23:24

Downloads: 3109

Keywords:

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}.