Presentation	1995/4/21 Randomized Simulations Between CRCW PRAMs Toshiyuki Fujiwara, Chuzo Iwamoto, Kazuo Iwama,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	It is known that one step of ARBITRARY (PRIORITY also) CRCW PRAMs is simulated by Θ(/) steps of COMMON CRCW PRAMs, but it was Open whether there is an essentially faster simulation if randomization is allowed. This paper presents a randomized simulation of O(/+loglog n) steps with error rate n^<-c>, where m=n/k is the number of different memory cells to which some processor in the simulated PRAM attempts to write. When m≤/, this bound can be written as O(loglog n).
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	PRAMs / parallel algorithms / simulation / randomized methods
Paper #
Date of Issue

Conference Information
Committee	COMP
Conference Date	1995/4/21(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)	Randomized Simulations Between CRCW PRAMs
Sub Title (in English)
Keyword(1)	PRAMs
Keyword(2)	parallel algorithms
Keyword(3)	simulation
Keyword(4)	randomized methods
1st Author's Name	Toshiyuki Fujiwara
1st Author's Affiliation	Department of Computer Science and Communication Engineering Kyushu University()
2nd Author's Name	Chuzo Iwamoto
2nd Author's Affiliation	Department of Computer Science and Communication Engineering Kyushu University
3rd Author's Name	Kazuo Iwama
3rd Author's Affiliation	Department of Computer Science and Communication Engineering Kyushu University
Date	1995/4/21
Paper #
Volume (vol)	vol.95
Number (no)	13
Page	pp.pp.-
#Pages	9
Date of Issue