| 講演名 | 1993/5/27 k-限定独立性に基づいたDNFの近似アルゴリズム 天野 一幸, 丸岡 章, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では,各リテラルが高々一度しか現われないDNF式を対象にして,DNF式を充足する変数への論理値の割り当ての割合を近似する決定性アルゴリズムを,限定された独立性をもつ確率分布に基づいて構成する手法を与える.Fを各リテラルが高々一度しか現われないn変数m項DNF式とする.確率分布Dが「k log m」-限定 独立ならば,|Pr_D[F]-Pr_U[F]|【less than or equal】(1, 2)^Ω(k)>が成立することを示す.但し,Uは一様分布,Pr[F]は添字として示された確率分布に従って変数への割り当てを定めたときに,Fが真となる確率を表すものとする.また,この結果より,上に述べた制限を満たすDNFを対象とした場合,任意のcに対して,|Pr_D[F]-Pr_U[F]|【less than or equal】cを満たす標本空間のサイズがlog nとmの多項式でおさえられるような確率分布Dが存在することを示す. |
| 抄録(英) | 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. |
| キーワード(和) | DNF式 / 決定性アルゴリズム / 限定独立 / 確率分布 |
| キーワード(英) | DNF formula / deterministic algorithm / limited independence / probability distribution |
| 資料番号 | COMP93-13,SS93-7 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1993/5/27(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | k-限定独立性に基づいたDNFの近似アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Approximation Algorithms for DNF under Distributions with Limited Independence |
| サブタイトル（和） | |
| キーワード(1)（和/英） | DNF式 / DNF formula |
| キーワード(2)（和/英） | 決定性アルゴリズム / deterministic algorithm |
| キーワード(3)（和/英） | 限定独立 / limited independence |
| キーワード(4)（和/英） | 確率分布 / probability distribution |
| 第 1 著者 氏名（和/英） | 天野 一幸 / Kazuyuki Amano |
| 第 1 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences,Tohoku University |
| 第 2 著者 氏名（和/英） | 丸岡 章 / Akira Maruoka |
| 第 2 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences,Tohoku University |
| 発表年月日 | 1993/5/27 |
| 資料番号 | COMP93-13,SS93-7 |
| 巻番号（vol） | vol.93 |
| 号番号（no） | 81 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |