ECCC-Report TR12-007https://eccc.weizmann.ac.il/report/2012/007Comments and Revisions published for TR12-007en-usWed, 24 Oct 2012 20:11:55 +0200
Revision 1
| Lower Bounds against Weakly-Uniform Threshold Circuits |
Ruiwen Chen,
Valentine Kabanets,
Jeff Kinne
https://eccc.weizmann.ac.il/report/2012/007#revision1A 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}.Wed, 24 Oct 2012 20:11:55 +0200https://eccc.weizmann.ac.il/report/2012/007#revision1
Paper TR12-007
| Lower Bounds against Weakly Uniform Circuits |
Ruiwen Chen,
Valentine Kabanets
https://eccc.weizmann.ac.il/report/2012/007A 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}.Sat, 28 Jan 2012 23:24:27 +0200https://eccc.weizmann.ac.il/report/2012/007