Number of the records: 1

KAM-DIMATIA Series 2005-722 and ITI Series 2005-238

SYSNO ASEP	0027511
Document Type	V - Research Report
R&D Document Type	V - Research Report
Title	KAM-DIMATIA Series 2005-722 and ITI Series 2005-238
Title	Katedra aplikované matematiky-Diskrétní matematika a teoretická informatika Serie 2005-722 a Institut teoretické informatiky Serie 2005-238
Author(s)	Král´, D. (CZ) Tichý, Tomáš (MU-W) Sgall, Jiří (MU-W)_{RID, ORCID, SAI}
Issue data	Praha: Charles University, 2005
Number of pages	16 s.
Language	eng - English
Country	CZ - Czech Republic
Keywords	concrete complexity ; randomized algorithms
Subject RIV	BA - General Mathematics
R&D Projects	GA201/05/0124 GA ČR - Czech Science Foundation (CSF)
	1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS)
CEZ	AV0Z10190503 - MU-W (2005-2011)
Annotation	We give asymptotically tight bounds both for randomized algorithms for the plurality problem in the case of two colors and many colors. For the balls colored by $k$ colors, we prove a lower bound $/Omega(kn)$ on the expected number of questions.
Workplace	Mathematical Institute
Contact	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Year of Publishing	2006

Number of the records: 1