On Deterministic Approximation of DNF

TitleOn Deterministic Approximation of DNF
Publication TypeTechnical Report
Year of Publication1993
AuthorsLuby, M., & Velickovic B.
Other Numbers797

We develop efficient deterministic algorithms for approximating the fraction of truth assignments that satisfy a disjunctive normal form formula. Although the algorithms themselves are deterministic, their analysis is probabilistic and uses the notion of limited independence between random variables.

Bibliographic Notes

ICSI Technical Report TR-93-009

Abbreviated Authors

M. Luby and B. Veli?kovi?

ICSI Publication Type

Technical Report