Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR12-007 | 24th October 2012 20:11

#### Lower Bounds against Weakly-Uniform Threshold Circuits

Revision #1
Authors: Ruiwen Chen, Valentine Kabanets, Jeff Kinne
Accepted on: 24th October 2012 20:11
Keywords:

Abstract:

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

Changes to previous version:

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

### Paper:

TR12-007 | 28th January 2012 23:23

#### Lower Bounds against Weakly Uniform Circuits

TR12-007
Authors: Ruiwen Chen, Valentine Kabanets
Publication: 28th January 2012 23:24
Keywords:

Abstract:

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

ISSN 1433-8092 | Imprint