A note on the quasi-additive bound for Boolean functions - Collections

＜journal article＞
A note on the quasi-additive bound for Boolean functions

Creator	Author PID K004444 Creator Name Kamiyama, Naoyuki 神山, 直之カミヤマ, ナオユキ
Language	English
Publisher	Faculty of Mathematics, Kyushu University
Publisher	九州大学大学院数理学研究院
Date	2012-10
Source Title	Journal of Math-for-Industry (JMI)
Vol	4
Issue	B
First Page	119
Last Page	122
Publication Type	Version of Record
Access Rights	open access
Related DOI	JMI ; 2012B-6
Related DOI	Journal of Math-for-Industry \|\| 4(B) \|\| p119-122
	JMI \|\| 4(B) \|\| p119-122
	http://gcoe-mi.jp/
Related URI	Journal of Math-for-Industry \|\| 4(B) \|\| p119-122
	JMI \|\| 4(B) \|\| p119-122
	http://gcoe-mi.jp/
Relation	JMI ; 2012B-6
	Journal of Math-for-Industry \|\| 4(B) \|\| p119-122
	JMI \|\| 4(B) \|\| p119-122
	http://gcoe-mi.jp/
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 li...near programming relaxation of some integer programming for computing the protocol partition number.show more

File	FileType	Size	Views	Description
2012B-6	pdf	97.3 KB	159

Record ID	1397708
Peer-Reviewed	Refereed
Subject Terms	computational complexity
	Boolean function complexity
	protocol partition number
ISSN	1884-4774
NCID	AA12444018
Notes	MI: Global COE Program Education-and-Research Hub for Mathematics-for-Industry
Notes	グローバルCOEプログラム「マス･フォア･インダストリ教育研究拠点」
Type	学術雑誌論文
Created Date	2014.01.07
Modified Date	2022.01.24