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 >>>

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 >>>

Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approximating the number of relevant variables in the parity function is as hard as properly learning parities.

More specifically, let $\gamma:{\mathbb R}^+\to ... more >>>