
PreviousNext
We show that hitting sets can derandomize any BPP-algorithm.
This gives a positive answer to a fundamental open question in
probabilistic algorithms. More precisely, we present a polynomial
time deterministic algorithm which uses any given hitting set
to approximate the fractions of 1's in the ...
more >>>
We present a $2^{\tilde O(\sqrt{n})}$ time exact learning
algorithm for polynomial size
DNF using equivalence queries only. In particular, DNF
is PAC-learnable in subexponential time under any distribution.
This is the first subexponential time
PAC-learning algorithm for DNF under any distribution.
We show that a DNF formula that has a CNF representation that contains
at least one ``$1/poly$-heavy''
clause with respect to a distribution $D$ is weakly learnable
under this distribution. So DNF that are not weakly
learnable under the distribution $D$ do not have
any ``$1/poly$-heavy'' clauses in any of ...
more >>>
PreviousNext