文献

J-GLOBAL ID：201502222433245832   整理番号：15A0452218

超二次形式サイズに向けた候補Boole関数

Candidate Boolean Functions towards Super-Quadratic Formula Size

著者 (1件)： UENO Kenya (Hakubi Center for Advanced Res. and Graduate School of Informatics, Kyoto Univ.)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E98.D  号： 3  ページ： 524-531 (J-STAGE)  発行年： 2015年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文では,次の観点から超二次形式サイズ下界を証明する可能性と困難性を探索した。最初に,帰納的Boole関数について考察し,それらの一般的形式サイズ上界を証明した。また,正確な2ビット関数に基づく帰納的Boole関数について議論し,それらの形式複雑性は少なくてもΩ(n²)であることを示した。従って,それらは超二次形式サイズ下界を証明するための,候補Boole関数になり得る。次に,パリティ関数と対比して,多数決関数の形式複雑性を解決するのが困難な理由について考察した。特に,Karchmer-Wigderson通信ゲームの最適プロトコル分割構造について議論した。(翻訳著者抄録)

シソーラス用語： *Boole関数 ,  *計算量 ,  *二次形式 ,  帰納的関数 ,  パリティ検査 ,  *下限 ,  上限 ,  多数決論理 ,  定理証明 ,  プロトコル
準シソーラス用語： 計算複雑性 ,  下界 ,  上界

分類 (1件)： 計算理論  (JB02000A)

引用文献 (18件)：

• [1] V.M. Khrapchenko, “Complexity of the realization of a linear function in the case of π-circuits,” Mathematical Notes, vol.9, pp.21-23, 1971.
• [2] J. Håstad, “The shrinkage exponent of De Morgan formulas is 2,” SIAM J. Comput., vol.27, no.1, pp.48-64, Feb. 1998.
• [3] A.E. Andreev, “On a method for obtaining more than quadratic effective lower bounds for the complexity of π-scheme,” Moscow University Mathematics Bulletin, vol.42, no.1, pp.63-66, 1987.
• [4] S. Laplante, T. Lee, and M. Szegedy, “The quantum adversary method and classical formula size lower bounds,” Computational Complexity, vol.15, no.2, pp.163-196, 2006.
• [5] T. Lee, “A new rank technique for formula size lower bounds,” Proc. 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2007), Lect. Notes Comput. Sci. 4393, pp.145-156, 2007.

タイトルに関連する用語 (3件)： 二次形式 ,  サイズ ,  Boole関数