On Deterministic Approximation of DNF
Title | On Deterministic Approximation of DNF |
Publication Type | Technical Report |
Year of Publication | 1993 |
Authors | Luby, M., & Velickovic B. |
Other Numbers | 797 |
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. |
URL | http://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 |