Art

J-GLOBAL ID：201502222433245832   Reference number：15A0452218

Candidate Boolean Functions towards Super-Quadratic Formula Size

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

Author (1)： UENO Kenya (Hakubi Center for Advanced Res. and Graduate School of Informatics, Kyoto Univ.)
Material： IEICE Transactions on Information and Systems (Web)  (IEICE Trans Inf Syst (Web))
Volume： E98.D  Issue： 3  Page： 524-531 (J-STAGE)  Publication year： 2015 
JST Material Number： U0469A  ISSN： 1745-1361  Document type： Article
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： *Boolean function ,  *computational complexity ,  *quadratic form ,  recursive function ,  parity check ,  *lower limit ,  upper limit ,  majority logic ,  theorem proving ,  protocol
Semi thesaurus term： computational complexity ,  lower bound ,  upper bound

JST classification (1)： Theory of computation  (JB02000A)

Reference (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.

Terms in the title (3)： 二次形式 ,  サイズ ,  Boole関数