Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Lower Bounds against Weakly-Uniform Threshold Circuits

RSS-Feed

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


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