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

CC BY-SA 3.0
2015-08-13T19:56:50.240Z
@Ricky Demer, that is already known. See for example Chen and Kabanets http://eccc.hpi-web.de/report/2012/007/download/
Ryan Williams
CC BY-SA 3.0
2015-08-14T05:34:14.997Z
Exactly... So, lower bounds for the uniformity you mentioned above are already known.
Ryan Williams
CC BY-SA 4.0
2021-02-04T05:32:53.613Z
Which section are referring permanent in people.csail.mit.edu/rrw/WeakUniformityCCC.pdf (searching permanent in the document is empty result)?
Turbo
CC BY-SA 4.0
2021-02-04T15:17:02.990Z
Hmm I guess we only mentioned the open problem during the CCC talk, but not in the actual paper :) Sorry about that. I assure you, we were certainly trying to prove it!
Ryan Williams
CC BY-SA 3.0
2015-08-11T17:37:00.077Z
2015-08-11T17:37:00.077Z
Ryan Williams
<p>In [1] it is stated that </p>

<blockquote>
  <p>"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)."</p>
</blockquote>

<p>$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$.</p>

<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$?</p>

<ul>
<li>[1] Agarwal, Allender, and Datta, "On $TC^0$, $AC^0$, and Arithmetic Circuits"</li>
</ul>

CC BY-SA 3.0
2015-08-06T06:38:42.147Z
@Kaveh You can keep your answer. Maybe you can remark it was for an erroneous version.
Turbo
CC BY-SA 3.0
2015-08-06T06:39:22.660Z
I don't think it answers the question, so it is not really an answer. :)
Kaveh
CC BY-SA 3.0
2015-08-06T06:42:08.133Z
Well it had some nice details.
Turbo
<cc.complexity-theory><complexity-classes><circuit-complexity><counting-complexity><permanent>
What is largest class of functions $C$ such that we know $\#P$ in not contained in $C$-generated $TC^0$?
Turbo
# What is largest class of functions $C$ such that we know $\#P$ in not contained in $C$-generated $TC^0$?

(Asked by: username_0 on 2015-08-06)

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"

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity, counting-complexity, permanent

> **Comments:**
> **username_0**: @username_1 You can keep your answer. Maybe you can remark it was for an erroneous version.  
> **username_1**: I don't think it answers the question, so it is not really an answer. :)  
> **username_0**: Well it had some nice details.  

---

## 1 answers

### Answer by username_2 on 2015-08-11. Score: 6 | Accepted 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).

> **Comments:**
> **username_2**: @Ricky Demer, that is already known. See for example Chen and Kabanets http://eccc.hpi-web.de/report/2012/007/download/  
> **username_2**: Exactly... So, lower bounds for the uniformity you mentioned above are already known.  
> **username_0**: Which section are referring permanent in people.csail.mit.edu/rrw/WeakUniformityCCC.pdf (searching permanent in the document is empty result)?  
> **username_2**: Hmm I guess we only mentioned the open problem during the CCC talk, but not in the actual paper :) Sorry about that. I assure you, we were certainly trying to prove it!  

---

