Název: KAM-DIMATIA Series 2005-722 and ITI Series 2005-238
Překlad názvu: Katedra aplikované matematiky-Diskrétní matematika a teoretická informatika Serie 2005-722 a Institut teoretické informatiky Serie 2005-238
Autoři: Král´, D. ; Tichý, Tomáš ; Sgall, Jiří
Typ dokumentu: Výzkumné zprávy
Rok: 2005
Jazyk: eng
Abstrakt: [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.
Klíčová slova: concrete complexity; randomized algorithms
Číslo projektu: CEZ:AV0Z10190503 (CEP), GA201/05/0124 (CEP), 1M0545 (CEP)
Poskytovatel projektu: GA ČR, GA MŠk

Instituce: Matematický ústav AV ČR (web)
Informace o dostupnosti dokumentu: Dokument je dostupný v příslušném ústavu Akademie věd ČR.
Původní záznam: http://hdl.handle.net/11104/0117608

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-33021


Záznam je zařazen do těchto sbírek:
Věda a výzkum > AV ČR > Matematický ústav
Zprávy > Výzkumné zprávy