Abstract
This paper extends and improves work of Fortnow and Klivans [5], who showed that if a circuit class \(\mathcal{C}\) has an efficient learning algorithm in Angluin’s model of exact learning via equivalence and membership queries [2], then we have the lower bound EXP NP \(\not\subseteq \mathcal{C}\). We use entirely different techniques involving betting games [4] to remove the NP oracle and improve the lower bound to EXP \(\not\subseteq \mathcal{C}\). This shows that it is even more difficult to design a learning algorithm for \(\mathcal{C}\) than the results of Fortnow and Klivans indicated.
This research was supported in part by NSF grants 0652601 and 0917417 and by an NWO travel grant. Part of this research was done while Hitchcock was on sabbatical at CWI.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aizenstein, H., Hegedüs, T., Hellerstein, L., Pitt, L.: Complexity theoretic hardness results for query learning. Computational Complexity 7, 19–53 (1998)
Angluin, D.: Queries and concept learning. Machine Learning 2(4), 319–342 (1988)
Buhrman, H., Homer, S.: Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. In: Shyamasundar, R.K. (ed.) FSTTCS 1992. LNCS, vol. 652, pp. 116–127. Springer, Heidelberg (1992)
Buhrman, H., van Melkebeek, D., Regan, K.W., Sivakumar, D., Strauss, M.: A generalization of resource-bounded measure, with application to the BPP vs. EXP problem. SIAM Journal on Computing 30(2), 576–601 (2001)
Fortnow, L., Klivans, A.R.: Efficient learning algorithms yield circuit lower bounds. Journal of Computer and System Sciences 75(1), 27–36 (2009)
Hitchcock, J.M.: Online learning and resource-bounded dimension: Winnow yields new lower bounds for hard sets. SIAM Journal on Computing 36(6), 1696–1708 (2007)
Karp, R.M., Lipton, R.J.: Some connections between nonuniform and uniform complexity classes. In: Proceedings of the 12th Annual ACM Symposium on Theory of Computing, pp. 302–309 (1980)
Kearns, M., Valiant, L.: Cryptographic limitations on learning Boolean formulae and finite automata. J. ACM 41(1), 67–95 (1994)
Kharitonov, M.: Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution. J. of Comput. Syst. Sci. 50(3), 600–610 (1995)
Lindner, W., Schuler, R., Watanabe, O.: Resource-bounded measure and learnability. Theory of Computing Systems 33(2), 151–170 (2000)
Littlestone, N.: Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning 2(4), 285–318 (1988)
Lutz, J.H.: Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences 44(2), 220–258 (1992)
Merkle, W., Miller, J., Nies, A., Reimann, J., Stephan, F.: Kolmogorov-Loveland Randomness and Stochasticity. Annals of Pure and Applied Logic 138(1-3), 183–210 (2006)
Muchnik, A.A., Semenov, A.L., Uspensky, V.A.: Mathematical metaphysics of randomness. Theoretical Computer Science 207(2), 263–317 (1998)
Toda, S.: On the computational power of PP and ⊕P. SIAM Journal on Computing 20(5), 865–877 (1991)
Valiant, L.G.: A theory of the learnable. Communications of the ACM 27(11), 1134–1142 (1984)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Harkins, R.C., Hitchcock, J.M. (2011). Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds. In: Aceto, L., Henzinger, M., Sgall, J. (eds) Automata, Languages and Programming. ICALP 2011. Lecture Notes in Computer Science, vol 6755. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22006-7_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-22006-7_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22005-0
Online ISBN: 978-3-642-22006-7
eBook Packages: Computer ScienceComputer Science (R0)