Yale University.  
Computer Science.  
     
Computer Science
Main Page
Academics
Graduate Program
Undergraduate Program
Course Information
Course Web Pages
Research
Our Research
Research Areas
Technical Reports
People
Faculty
Graduate Students
Research and Technical Staff
Administrative Staff
Alumni
Degree Recipients
Resources
Calendars
Computing Facilities
CS Talks Mailing List
Yale Computer Science FAQ
Yale Workstation Support
Computing Lab
AfterCollege Job Resource
Department Information
Contact Us
History
Life in the Department
Life About Town
Directions
Job Openings
Faculty Positions
Useful Links
City of New Haven
Yale Applied Mathematics
Yale C2: Creative Consilience of
Computing and the Arts
Yale Faculty of Engineering
Yale GSAS Staff Directory
Yale University Home Page
Google Search
Yale Info Phonebook
Internal
Internal 		 

Theory Colloquium
Thursday, March 4, 2010
4:00 p.m., AKW 200

Host: Dana Angluin

Speaker: Linda Sellie, Polytechnic Institute of NYU
Title: Learning Random DNF over the Uniform Distribution

Abstract: In this talk, we show that randomly generated c log(n)-DNF formulae can be learned exactly in probabilistic polynomial time using randomly generated examples. Our notion of randomly generated is with respect to a uniform distribution. To prove this we extend the concept of well behaved c log(n) Monotone DNF formulae to c log(n)-DNF, and show that almost every DNF formula is well-behaved, and that there exists a probabilistic Turing machine that exactly learns all well behaved c log(n)-DNF formulae. This is the first algorithm that learns a large class of DNF with a polynomial number of terms from random examples alone.

Bio: Linda Sellie is currently a Postdoc in the Department of Computer Science and Engineering at Polytechnic Institute of NYU working with Professor Lisa Hellerstein. Linda received her Ph.D. in 2008 from the Department of Computer Science at the University of Chicago.