id: 06086149
dt: a
an: 06086149
au: Kinne, Jeff
ti: On TC$^{0}$ lower bounds for the permanent.
so: Gudmundsson, Joachim (ed.) et al., Computing and combinatorics. 18th annual
    international conference, COCOON 2012, Sydney, Australia, August
    20‒22, 2012. Proceedings. Berlin: Springer (ISBN
    978-3-642-32240-2/pbk). Lecture Notes in Computer Science 7434, 420-432
    (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-32241-9_36
ab: Summary: In this paper we consider the problem of proving lower bounds for
    the permanent. An ongoing line of research has shown super-polynomial
    lower bounds for slightly-non-uniform small-depth threshold and
    arithmetic circuits [1,2,3,4]. We prove a new parameterized lower bound
    that includes each of the previous results as sub-cases. Our main
    result implies that the permanent does not have Boolean threshold
    circuits of the following kinds. 1 Depth $O(1)$, poly-$\log (n)$ bits
    of non-uniformity, and size $s(n)$ such that for all constants $c, s
    ^{(c)}(n) < 2^{n }$. The size $s$ must satisfy another technical
    condition that is true of functions normally dealt with (such as
    compositions of polynomials, logarithms, and exponentials). 2 Depth
    $o(\log \log n)$, poly-$\log (n)$ bits of non-uniformity, and size $n
    ^{O(1)}$. 3 Depth $O(1), n ^{o(1)}$ bits of non-uniformity, and size $n
    ^{O(1)}$. Our proof yields a new “either or” hardness result. One
    instantiation is that either NP does not have polynomial-size
    constant-depth threshold circuits that use $n ^{o(1)}$ bits of
    non-uniformity, or the permanent does not have polynomial-size general
    circuits.
rv: