It has been shown in previous recent work that
multiplicity automata are predictable from multiplicity
and equivalence queries. In this paper we generalize
related notions in a matrix representation
and obtain a basis for the solution
of a number of open problems in learnability theory.
Membership queries are generalized ... more >>>

In this paper, we consider the question of determining whether
a function $f$ has property $P$ or is $\e$-far from any
function with property $P$.
The property testing algorithm is given a sample of the value
of $f$ on instances drawn according to some distribution.
In some cases,
it ... more >>>

In a variety of PAC learning models, a tradeoff between time and
information seems to exist: with unlimited time, a small amount of
information suffices, but with time restrictions, more information
sometimes seems to be required.
In addition, it has long been known that there are
concept classes that ... more >>>

This is a revised version of work which has appeared
in preliminary form in the 36th FOCS, 1995.

Given a function $f$ mapping $n$-variate inputs from a finite field
$F$ into $F$,
we consider the task of reconstructing a list of all $n$-variate
degree $d$ polynomials which agree with $f$
more >>>

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

A theory, in this context, is a Boolean formula; it is
used to classify instances, or truth assignments. Theories
can model real-world phenomena, and can do so more or less
correctly.
The theory revision, or concept revision, problem is to
correct a given, roughly correct concept.
This problem is ... more >>>

We give an algorithm that with high probability properly learns random monotone t(n)-term
DNF under the uniform distribution on the Boolean cube {0, 1}^n. For any polynomially bounded function t(n) <= poly(n) the algorithm runs in time poly(n, 1/eps) and with high probability outputs an eps accurate monotone DNF ... more >>>