Presentation	2002/4/18 An Explicit Lower Bound of 5n-o(n) for Boolean Circuits Kazuo IWAMA, Hiroki MORIZUMI,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	The current best lower bound of 4.5n-o(n) for an explicit family of Boolean circuits over the basis U_2 [1] is improved to 5n-o(n) using the same family of circuits. Our lower bound applies to any Strongly-Two-Dependent Boolean function, which is defined by Oded Lachish and Ran Raz in [1]. We modify the parameter called SD(C) for a circuit C, from SD(C)=Size(C)-0.5・Degeneracy(C) in [1] to SD(C)=Size(C)-Degeneracy(C) that was originally used in [2]. That plays a key role in the improvement.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	Circuit complexity / Boolean circuit / P / NP / Strongly-Two-Dependent
Paper #	COMP2002-1
Date of Issue

Conference Information
Committee	COMP
Conference Date	2002/4/18(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	An Explicit Lower Bound of 5n-o(n) for Boolean Circuits
Sub Title (in English)
Keyword(1)	Circuit complexity
Keyword(2)	Boolean circuit
Keyword(3)	P
Keyword(4)	NP
Keyword(5)	Strongly-Two-Dependent
1st Author's Name	Kazuo IWAMA
1st Author's Affiliation	Graduate School of Informatics, Kyoto Univ.()
2nd Author's Name	Hiroki MORIZUMI
2nd Author's Affiliation	Graduate School of Informatics, Kyoto Univ.
Date	2002/4/18
Paper #	COMP2002-1
Volume (vol)	vol.102
Number (no)	31
Page	pp.pp.-
#Pages	8
Date of Issue