Approximate counting by hashing in bounded arithmetic

0326451 - MÚ 2010 RIV US eng J - Journal Article
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. E-ISSN 1943-5886
R&D Projects: GA AV ČR IAA1019401
Institutional research plan: CEZ:AV0Z10190503
Keywords : bounded arithmetic * approximate counting * universal hashing
Subject RIV: BA - General Mathematics
Impact factor: 0.631, year: 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.
Permanent Link: http://hdl.handle.net/11104/0173553