Počet záznamů: 1

Approximate counting by hashing in bounded arithmetic

  1. 1.
    0326451 - MU-W 2010 RIV US eng J - Článek v odborném periodiku
    Jeřábek, Emil
    Approximate counting by hashing in bounded arithmetic.
    [Aproximativní počítání pomocí hashování v omezené aritmetice.]
    Journal of Symbolic Logic. Roč. 74, č. 3 (2009), s. 829-860 ISSN 0022-4812
    Grant CEP: GA AV ČR IAA1019401
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: bounded arithmetic * approximate counting * universal hashing
    Kód oboru RIV: BA - Obecná matematika
    Impakt faktor: 0.631, rok: 2009

    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.

    Ukážeme, jak zformalizovat aproximativní počítání pomocí hashovacích funkcí v podsystémech omezené aritmetiky s použitím slabého principu PHP. Uvádíme několik aplikací, včetně důkazu turnajového principu a vylepšení známé souvislosti kolapsu hierarchie omezených aritmetik s kolapsem polynomiální hierarchie.
    Trvalý link: http://hdl.handle.net/11104/0173553
    Název souboruStaženoVelikostKomentářVerzePřístup
    Jerabek1.pdf111.3 MBVydavatelský postprintvyžádat