8
$\begingroup$

In [1] it is stated that

"It remains an open question as to whether every function in $\#P$ has $TC^0$ circuits (although it is at least known that not all $\#P$ functions have DLogTime-uniform $TC^0$ circuits)."

$TC^0$ circuits generated by DLogTime functions does not contain $\#P$. We don't know if $TC^0$ circuits generated by arbitrary functions does not contain $\#P$.

Is there anything known about the cases in between these two? E.g. is it known if $TC^0$ circuits generated by $L$ does not contain $\#P$?

  • [1] Agarwal, Allender, and Datta, "On $TC^0$, $AC^0$, and Arithmetic Circuits"
Improve this question
$\endgroup$
3
  • $\begingroup$ @Kaveh You can keep your answer. Maybe you can remark it was for an erroneous version. $\endgroup$
    – Turbo
    Aug 6 '15 at 6:38
  • $\begingroup$ I don't think it answers the question, so it is not really an answer. :) $\endgroup$
    – Kaveh
    Aug 6 '15 at 6:39
  • 1
    $\begingroup$ Well it had some nice details. $\endgroup$
    – Turbo
    Aug 6 '15 at 6:42
6
$\begingroup$

This is an (interesting) open problem, as far as I know. Rahul Santhanam and I explicitly mention the problem of proving Permanent is not in LOGSPACE-uniform TC0 in our CCC'13 paper (On Medium-Uniformity and Circuit Lower Bounds).

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ More conservatively, one could ask about DTISP $\hspace{-0.04 in}\left(\log(n)\hspace{-0.04 in}\cdot \hspace{-0.03 in}(\log(\log(n)))^{o(1)}\hspace{-0.02 in},\hspace{-0.02 in}O(\log(n))\right)\hspace{-0.02 in}$-uniformity. $\;\;\:\:$ $\endgroup$
    – user6973
    Aug 12 '15 at 22:24
  • $\begingroup$ @Ricky Demer, that is already known. See for example Chen and Kabanets eccc.hpi-web.de/report/2012/007/download $\endgroup$
    – Ryan Williams
    Aug 13 '15 at 19:56
  • $\begingroup$ Well, by that paper, POLYLOGTIME is a "class of functions C such that we know #P is not contained in" C-uniform TC0. $\:$ Furthermore, by padding, POLYLOGTIME is larger than DLOGTIME. $\endgroup$
    – user6973
    Aug 13 '15 at 20:43
  • $\begingroup$ Exactly... So, lower bounds for the uniformity you mentioned above are already known. $\endgroup$
    – Ryan Williams
    Aug 14 '15 at 5:34
  • $\begingroup$ ... and, those lower bounds are not mentioned in your answer. $\;$ $\endgroup$
    – user6973
    Aug 14 '15 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.