Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with proper learning:
TR02-019 | 20th March 2002
Nader Bshouty, Lynn Burroughs

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