Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PROPER LEARNING:
Reports tagged with proper learning:
TR02-019 | 20th March 2002

#### On the proper learning of axis parallel concepts

We study the proper learnability of axis parallel concept classes
in the PAC learning model and in the exact learning model with
membership and equivalence queries. These classes include union of boxes,
DNF, decision trees and multivariate polynomials.

For the {\it constant} dimensional axis parallel concepts $C$
we ... more >>>

TR05-127 | 5th November 2005
Vitaly Feldman

#### Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries

Revisions: 1

Producing a small DNF expression consistent with given data is a
classical problem in computer science that occurs in a number of forms and
has numerous applications. We consider two standard variants of this
problem. The first one is two-level logic minimization or finding a minimal
more >>>

ISSN 1433-8092 | Imprint