Publication Details
Title: On Deterministic Approximation of DNF
Author: M. Luby and B. Veličković
Group: ICSI Technical Reports
Date: March 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-009.pdf
Overview:
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 Information:
ICSI Technical Report TR-93-009
Bibliographic Reference:
M. Luby and B. Veličković. On Deterministic Approximation of DNF. ICSI Technical Report TR-93-009, March 1993
Author: M. Luby and B. Veličković
Group: ICSI Technical Reports
Date: March 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-009.pdf
Overview:
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 Information:
ICSI Technical Report TR-93-009
Bibliographic Reference:
M. Luby and B. Veličković. On Deterministic Approximation of DNF. ICSI Technical Report TR-93-009, March 1993