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

0027511 - MÚ 2006 RIV CZ eng V - Výzkumná zpráva
Král´, D. - Tichý, Tomáš - Sgall, Jiří
KAM-DIMATIA Series 2005-722 and ITI Series 2005-238.
[Katedra aplikované matematiky-Diskrétní matematika a teoretická informatika Serie 2005-722 a Institut teoretické informatiky Serie 2005-238.]
Praha: Charles University, 2005. 16 s.
Grant CEP: GA ČR(CZ) GA201/05/0124; GA MŠMT(CZ) 1M0545
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: concrete complexity * randomized algorithms
Kód oboru RIV: BA - Obecná matematika

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.

Článek studuje pravděpodobnostní strategie pro problém plurality.
Trvalý link: http://hdl.handle.net/11104/0117608