APPROXIMATION ALGORITHMS FOR DNF UNDER DISTRIBUTIONS WITH LIMITED INDEPENDENCE

In this paper we investigate the problem of approximating the fraction of truth assignments that satisfy a Boolean formula with some restric ted form of DNF under distributions with limited independence between random variables. Let F be a DNF formula on n variables with m clauses in which each literal appears at most once. We prove that if D is [k log m]-wise independent, then \Pr-D[F]-Pr-U[F]\ less than or equal to (1/2)(Omega(k)), where U denotes the uniform distribution and Pr-D[F] denotes the probability that F is satisfied by a truth assignment chos en according to distribution D (similarly for Pr-U[F]). Using the resu lt, we also derive the following: For formulas satisfying the restrict ion described above and for any constant c, there exists a probability distribution D, with size polynomial in log n and m, such that \Pr-D[ F]-Pr-U[F]\ less than or equal to c holds.