Abstract:
This paper extends and improves work of Fortnow and Klivans [2009], who showed that if a circuit class C has an efficient learning algorithm in Angluin's model of exact learning via equivalence and membership queries [Angluin, 1988], then we have the lower bound EXP^NP ⊈ C. We use entirely different techniques involving betting games [Buhrman et al., 2001] to remove the NP oracle and improve the lower bound to EXP ⊈ C. This shows that it is even more difficult to design a learning algorithm for C than the results of Fortnow and Klivans indicated. We also investigate the connection between betting games and natural proofs, and as a corollary the existence of strong pseudorandom generators.

Full Version:

• ACM Transactions on Computation Theory, 5(4), article 18, 2013.
  [DOI | PDF]

• Proceedings of the 38th International Colloquium on Automata, Languages, and Programming (Zurich, Switzerland, July 4-8, 2011), Lecture Notes in Computer Science 6755, pages 416-423. Springer-Verlag, 2011.
  [DOI]