Skip to content. Skip to navigation
McGill Home SOCS Home
Personal tools
You are here: Home Announcements and Events Seminars profile

Fall 2015 Schedule
Winter 2016 Schedule

2014/04/08, MC103, 12:10 - 12:40

The Impossibility of PAC-learning DFAs
Bundit Laekhanukit , PhD Student, McGill SOCS


Probably approximately correct learning (PAC learning) is a learning model proposed by Leslie Valiant that introduces the concepts of computational complexity to machine learning. In particular, given positive and negative samples, the learner is expected to find a polynomial-time computable function that could approximately distinguish between positive and negative samples.

In this work, we study the PAC-learnability of DFAs, i.e., the case where positive and negative samples are drawn from an unknown DFA. We show that, unless NP=RP, DFAs are not PAC-learnable, thus, answering an open question raised 25 years ago by Pitt and Warmuth.

This is a joint work with Parinya Chalermsook and Danupon Nanongkai.