# What is largest class of functions $C$ such that we know $\#P$ in not contained in $C$-generated $TC^0$?

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"
• @Kaveh You can keep your answer. Maybe you can remark it was for an erroneous version. – T.... Aug 6 '15 at 6:38
• I don't think it answers the question, so it is not really an answer. :) – Kaveh Aug 6 '15 at 6:39
• Well it had some nice details. – T.... Aug 6 '15 at 6:42

## 1 Answer

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).

• 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. $\;\;\:\:$ – user6973 Aug 12 '15 at 22:24
• @Ricky Demer, that is already known. See for example Chen and Kabanets eccc.hpi-web.de/report/2012/007/download – Ryan Williams Aug 13 '15 at 19:56
• 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. – user6973 Aug 13 '15 at 20:43
• Exactly... So, lower bounds for the uniformity you mentioned above are already known. – Ryan Williams Aug 14 '15 at 5:34
• ... and, those lower bounds are not mentioned in your answer. $\;$ – user6973 Aug 14 '15 at 7:39