講演抄録/キーワード |
講演名 |
2009-10-16 16:00
Breaking the Rectangle Bound Barrier against Formula Size Lower Bounds ○Kenya Ueno(Univ. of Tokyo) COMP2009-38 |
抄録 |
(和) |
Karchmer, Kushilevitz and Nisanは、論理式サイズに関する問題を長方形限界と呼ばれる整数計画問題として定式化し、その線形計画緩和の双対問題に対して実行可能解を与えることで論理式サイズ下界を示す線形計画限界と呼ばれる技術を導入した。線形計画限界の拡張として、本研究では擬加法的限界とSherali-Adams限界と名付けられた論理式サイズ下界を証明する新しい一般的技術を導入する。Sherali-Adams限界は潜在的に長方形限界と等価な下界を示すことが可能な強さを秘めている一方で、擬加法的限界においては長方形限界を上回ることができることを示す。また、万能関係と呼ばれる行列に対する擬加法的限界の解から任意の論理関数に対して論理式サイズ下界を導出できることから、その最適下限に向けて万能関係の構造を議論する。 |
(英) |
Karchmer, Kushilevitz and Nisan formulated the formula size problem as an integer programming problem called the rectangle bound and introduced a technique called the LP bound, which gives a formula size lower bound by showing a feasible solution of the dual problem of its LP-relaxation. As extensions of the LP bound, we introduce novel general techniques proving formula size lower bounds, named as a quasi-additive bound and the Sherali-Adams bound. While the Sherali-Adams bound is potentially strong enough to give a lower bound matching to the rectangle bound, we prove that the quasi-additive bound can surpass the rectangle bound. We also discuss structure of the universal relation towards its matching bound because we can derive a formula size lower bound of any Boolean function from a solution of the quasi-additive bound for the universal relation. |
キーワード |
(和) |
形式的複雑性尺度 / 論理式サイズ / 次元上げ及び射影法 / 線形計画法 / / / / |
(英) |
Formal Complexity Measures / Formula Size / Lift-and-Project Methods / Linear Programming / / / / |
文献情報 |
信学技報, vol. 109, no. 235, COMP2009-38, pp. 41-48, 2009年10月. |
資料番号 |
COMP2009-38 |
発行日 |
2009-10-09 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2009-38 |