| Presentation | 1993/5/27 Approximation Algorithms for DNF under Distributions with Limited Independence Kazuyuki Amano, Akira Maruoka, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper we investigate the problem of approximating the fraction of truth assignments that satisfy a formula with some restricted 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 if D is 「k log m」-wise independent then |Pr_D£F!- Pr _U£F!|【less than or equal】(1, 2)^Ω(k)>,where U denotes the uni form distribution,Pr_D£F! denotes the probability that F is satisf ied by a truth assignment chosen according to distribution D and similar for Pr_U£F!.It follows from this result,for formulas satis fying the restriction described above,we also prove that for any constant c that there exist a probability distribution D such that |Pr_D£F!- Pr_U£F!|【less than or equal】c holds and the size of t he sample space of D is polynomial in log n and m. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | DNF formula / deterministic algorithm / limited independence / probability distribution |
| Paper # | COMP93-13,SS93-7 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1993/5/27(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Approximation Algorithms for DNF under Distributions with Limited Independence |
| Sub Title (in English) | |
| Keyword(1) | DNF formula |
| Keyword(2) | deterministic algorithm |
| Keyword(3) | limited independence |
| Keyword(4) | probability distribution |
| 1st Author's Name | Kazuyuki Amano |
| 1st Author's Affiliation | Graduate School of Information Sciences,Tohoku University() |
| 2nd Author's Name | Akira Maruoka |
| 2nd Author's Affiliation | Graduate School of Information Sciences,Tohoku University |
| Date | 1993/5/27 |
| Paper # | COMP93-13,SS93-7 |
| Volume (vol) | vol.93 |
| Number (no) | 81 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |