Original title: KAM-DIMATIA Series 2005-722 and ITI Series 2005-238
Translated title: Katedra aplikované matematiky-Diskrétní matematika a teoretická informatika Serie 2005-722 a Institut teoretické informatiky Serie 2005-238
Authors: Král´, D. ; Tichý, Tomáš ; Sgall, Jiří
Document type: Research reports
Year: 2005
Language: eng
Abstract: [eng] [cze]
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.
Keywords: concrete complexity; randomized algorithms
Project no.: CEZ:AV0Z10190503 (CEP), GA201/05/0124 (CEP), 1M0545 (CEP)
Funding provider: GA ČR, GA MŠk

Institution: Institute of Mathematics AS ČR (web)
Document availability information: Fulltext is available at the institute of the Academy of Sciences.
Original record: http://hdl.handle.net/11104/0117608

Permalink: http://www.nusl.cz/ntk/nusl-33021


The record appears in these collections:
Research > Institutes ASCR > Institute of Mathematics
Reports > Research reports