Editorial Board

JMI2012B-6 A note on the quasi-additive bound for Boolean functions (pp.119-122)

Author(s)： Naoyuki Kamiyama

J. Math-for-Ind. 4B (2012) 119-122.

Abstract
In this note, we prove that the linear programming for computing the quasi-additive bound of the formula size of a Boolean function presented by Ueno (2010) is equivalent to the dual problem of the linear programming elaxation of some integer programming for computing the protocol partition number.

Keyword(s).　 computational complexity, Boolean function complexity, protocol partition number

Institute of Mathematics for Industry & Faculty of Mathematics, Kyushu University