Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > UNIFORM DISTRIBUTION:
Reports tagged with uniform distribution:
TR01-006 | 18th October 2000
Rocco Servedio

#### On Learning Monotone DNF under Product Distributions

We show that the class of monotone $2^{O(\sqrt{\log n})}$-term DNF
formulae can be PAC learned in polynomial time under the uniform
distribution. This is an exponential improvement over previous
algorithms in this model, which could learn monotone
$o(\log^2 n)$-term DNF, and is the first efficient algorithm
for ... 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