ON DETERMINISTIC APPROXIMATION OF DNF

We develop several quasi-polynomial-time deterministic algorithms for approximating the fraction of truth assignments that satisfy a disjunc tive normal form formula. The most efficient algorithm computes for a given DNF formula F on n variables with m clauses and epsilon > 0 an e stimate Y such that \Pr[F]-Y\less than or equal to epsilon in time whi ch is (mlog(n))(exp(0(root loglog(m)))), for any constant epsilon. Alt hough the algorithms themselves are deterministic, their analysis is p robabilistic and uses the notion of limited independence between rando m variables.