期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：A family of Boolean circuits Cnn0 is called \emph{(n) -weakly uniform} if
there is a polynomial-time algorithm for deciding the direct-connection language of every Cn,
given \emph{advice} of size (n) . This is a relaxation of the usual notion of uniformity, which allows one
to interpolate between complete uniformity (when (n)=0 ) and complete non-uniformity (when (n)Cn ).
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
no(1)-weakly uniform \TC0 circuits. This strengthens the
results by Allender~\cite{All99} (for \emph{uniform} \TC0) 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 (logn)O(1)-weakly uniform
threshold circuits of depth o(loglogn), generalizing the result
by Koiran and Perifel~\cite{KP09}.
