# On the status of learnability inside $\mathsf{TC}^0$

I'm trying to understand the complexity of functions expressible via threshold gates and this led me to $\mathsf{TC}^0$. In particular, I'm interested what's currently known about learning inside $\mathsf{TC}^0$, since I'm not an expert in the area.

What I've discovered thus far is:

• All of $\mathsf{AC}^0$ can be learned in quasipolynomial time under the uniform distribution via Linial-Mansour-Nisan.
• Their paper also points out that existence of a pseudorandom function generator prevents learning, and this, coupled with a later result of Naor-Reingold that $\mathsf{TC}^0$ admits PRFGs, suggests that $\mathsf{TC}^0$ represents the limits of learnability (at least in a PAC-sense)
• There's a 2002 paper by Jackson/Klivans/Servedio that can learn a fragment of $\mathsf{TC}^0$ (with at most polylogarithmic majority gates).

I've done the usual google scholaring, but am hoping the collective wisdom of cstheory might have a quicker answer:

Is what I described the state of the art for our understanding of the complexity of learning (in terms of which classes sandwich efficient learners) ? And is there a good survey/reference that maps out the current state of the landscape ?

• +1 Nice question. Didn't Lance have a related blog post some time ago? – Kaveh Apr 4 '14 at 0:52
• Do you mean this one (guest post by Ryan O'Donnell): blog.computationalcomplexity.org/2005/08/… – Suresh Venkat Apr 4 '14 at 1:38
• Maybe this one: blog.computationalcomplexity.org/2013/08/… – Suresh Venkat Apr 4 '14 at 1:49
• It is plausible that there are pseudorandom generators in NC0. $\:$ (In particular, I find it very unlikely that a pseudorandom generator is known to prevent learning.) $\;\;\;$ On the other hand, the existence of the maps $\: x\mapsto F(r\hspace{-0.03 in},x) \:$ for a pseudorandom function family $F$ does prevent learning. – user6973 Apr 5 '14 at 19:23
• Linial-Mansour-Nisan show that $\text{AC}^0$ can be learned under the uniform distribution in quasipolynomial time. Kharitinov showed that if quasipolynomial were improved to polynomial, it would yield a sub-exponential time algorithm for factoring Blum integers. – Robin Kothari Apr 8 '14 at 1:35

• What is the fastest running time known for learning such LTF circuits? (or anything inside $TC^0$) – gradstudent Feb 18 '18 at 8:51
However, parities and noisy parities can be learned in polynomial time if we're given a membership oracle. So it might be interesting to check whether depth-2 TC0 can be learned using a membership oracle. I wouldn't be totally surprised if the answer is yes. On the other hand, I doubt that $O(1)$-depth TC0 can be learned with membership queries. It might be good to start with AC0[6] (or even AC0[2]) and go from there.