Presentation	1995/7/27 Some Difference between Addition and Multiplication on Circuit Complexity Tatsuie Tsukiji,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	A node v_i on a directed path v_0, v_1,...,v_k (from v_0 to v_k of length k) is called the i th node on the path. For two nodes v, v' in a directed acyclic graph C, let us denote by w(v,v',i;C) the number of i th node on a path from v to v', and call max_ ω(v,v',i;C) the path-width of C. We show that any Boolean shifter with a constant path-width must have Ω(n log log log n) of gates. As a corollary, the Boolean multiplication must have Ω(n log log log n) of gates to be computed on constant path-width circuits : the Boolean addition, on the other hand, have some construcitons of efficient circuits, O(n) of size, O(log n) of depth, and O(1) of path-width.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	circuit complexity / path-width / shifting / lower bound
Paper #
Date of Issue

Conference Information
Committee	COMP
Conference Date	1995/7/27(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	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Some Difference between Addition and Multiplication on Circuit Complexity
Sub Title (in English)
Keyword(1)	circuit complexity
Keyword(2)	path-width
Keyword(3)	shifting
Keyword(4)	lower bound
1st Author's Name	Tatsuie Tsukiji
1st Author's Affiliation	Graduate School of Informatin Science and Engineering Tokyo Institute of Technology()
Date	1995/7/27
Paper #
Volume (vol)	vol.95
Number (no)	188
Page	pp.pp.-
#Pages	5
Date of Issue