Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-16T13:32:50.898Z Has data issue: false hasContentIssue false

Approximate counting by hashing in bounded arithmetic

Published online by Cambridge University Press:  12 March 2014

Emil Jeřábek*
Affiliation:
Institute of Mathematics of the Academy of Sciences, Žitná 25, 115 67 Praha 1, Czech Republic, E-mail: jerabek@math.cas.cz, URL: http://math.cas.cz/~jerabek

Abstract

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 applications, including a proof of the tournament principle, and an improvement on the known relationship of the collapse of the bounded arithmetic hierarchy to the collapse of the polynomial-time hierarchy.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable