Počet záznamů: 1
Approximate counting by hashing in bounded arithmetic
- 1.
SYSNO ASEP 0326451 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Approximate counting by hashing in bounded arithmetic Překlad názvu Aproximativní počítání pomocí hashování v omezené aritmetice Tvůrce(i) Jeřábek, Emil (MU-W) RID, SAI, ORCID Zdroj.dok. Journal of Symbolic Logic. - : Cambridge University Press - ISSN 0022-4812
Roč. 74, č. 3 (2009), s. 829-860Poč.str. 32 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova bounded arithmetic ; approximate counting ; universal hashing Vědní obor RIV BA - Obecná matematika CEP IAA1019401 GA AV ČR - Akademie věd CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000269571100006 Anotace We show how to formalize approximate counting via hash functions in subsystems of bounded arithmetic, using variants of the weak pigeonhole principle. We discuss several appications, including a proof of the tournament principle, and an improvement on the known relationship of the collapse of the bounded arithmetic hierarchy tot he collapse of the polynomial-time hierarchy. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2010
Počet záznamů: 1