Seminar in Computational Learning: List of Papers

Introduction and Definitions

• D. Angluin. Queries and concept learning. Machine Learning, 2(4):319--342, 1988.
• M. J. Kearns and U. V. Vazirani. An Introduction to Computational Learning Theory. MIT Press. 1994.

Learning automata

• D. Angluin. Learning regular sets from queries and counterexamples. Information and Computation, 75:87--106, 1987.
• R. L. Rivest and R. E. Schapire. Inference of finite automata using homing sequences. Information and Computation, 103:299--347, 1993.
• A. Beimel, F. Bergadano, N. H. Bshouty, E. Kushilevitz, and S. Varricchio. On the applications of multiplicity automata in learning. In the 37th FOCS, pages 349--358, 1996.

Learning sub-classes of DNF

• D. Angluin, L. Hellerstein, and M. Karpinski. Learning read-once formulas with queries. J. of the ACM, 40:185--210, 1993.
• D. Angluin, M. Frazier, and L. Pitt. Learning Conjunctions of Horn Clauses. The 31st FOCS, pages 186--192, 1990.
• H. Aizenstein and L. Pitt. Exact Learning of Read-Twice DNF Formulas. Proceedings of the 32nd FOCS, pages 170-179, 1991.
• N. H. Bshouty. Exact learning via the monotone theory. In Proc. of the 34th Symp. on Foundations of Computer Science (FOCS), pages 302--311, 1993. Journal version: Information and Computation, 123:146--153, 1995.
• N. H. Bshouty. Simple learning algorithms using divide and conquer. Computational Complexity, 6:174--194, 1997.
• E. Kushilevitz. A simple algorithm for learning $O(\log n)$-term DNF. Information Process. Lett., 61(6):289--292, 1997.

Learning geometric objects

• A. Beimel and E. Kushilevitz. Learning boxes in high dimension. Algorithmica. 22(1/2):76--90, 1998.
• W. Maass and M. K. Warmuth. Efficient learning with virtual threshold gates. Information and Computation, 141(1):66--83, 1998.
• N. Littlestone. Learning when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2:285--318, 1988.
• S. Ben-David, N. H. Bshouty, and E. Kushilevitz. A composition theorem for learning algorithms with applications to geometric concept classes. In Proc. of the 29th Symp. on the Theory of Computing (STOC), pages 324--333, 1997.
• N. H. Bshouty. A new composition theorem for learning algorithms. In Proc. of the 30th Symp. on Theory of Computing (STOC), pages 583--589, 1998.