On Deterministic Approximation of DNF

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

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.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1993/tr-93-009.pdf
Bibliographic Notes

ICSI Technical Report TR-93-009

Abbreviated Authors

M. Luby and B. Veli?kovi?

ICSI Publication Type

Technical Report