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 ?