Journal of Symbolic Logic 74 (3):829-860 (2009)

Authors
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
Keywords Bounded arithmetic   approximate counting   universal hashing
Categories (categorize this paper)
DOI 10.2178/jsl/1245158087
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 72,634
Through your library

References found in this work BETA

Bounded Arithmetic and the Polynomial Hierarchy.Jan Krajíček, Pavel Pudlák & Gaisi Takeuti - 1991 - Annals of Pure and Applied Logic 52 (1-2):143-153.
Dual Weak Pigeonhole Principle, Boolean Complexity, and Derandomization.Emil Jeřábek - 2004 - Annals of Pure and Applied Logic 129 (1-3):1-37.
Relating the Bounded Arithmetic and Polynomial Time Hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.
The Strength of Sharply Bounded Induction.Emil Jeřábek - 2006 - Mathematical Logic Quarterly 52 (6):613-624.

Add more references

Citations of this work BETA

Expander Construction in VNC1.Sam Buss, Valentine Kabanets, Antonina Kolokolova & Michal Koucký - 2020 - Annals of Pure and Applied Logic 171 (7):102796.
Feasibly Constructive Proofs of Succinct Weak Circuit Lower Bounds.Moritz Müller & Ján Pich - 2020 - Annals of Pure and Applied Logic 171 (2):102735.
Induction rules in bounded arithmetic.Emil Jeřábek - 2020 - Archive for Mathematical Logic 59 (3-4):461-501.
Uniform Proofs of ACC Representations.Sam Buss - 2017 - Archive for Mathematical Logic 56 (5-6):639-669.

Add more citations

Similar books and articles

Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
On Interpretations of Bounded Arithmetic and Bounded Set Theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
Regularity in Models of Arithmetic.George Mills & Jeff Paris - 1984 - Journal of Symbolic Logic 49 (1):272-280.
Could Experience Disconfirm the Propositions of Arithmetic?Jessica M. Wilson - 2000 - Canadian Journal of Philosophy 30 (1):55--84.
Tautologies From Pseudo-Random Generators.Jan Krajíček - 2001 - Bulletin of Symbolic Logic 7 (2):197-212.

Analytics

Added to PP index
2010-09-12

Total views
193 ( #62,498 of 2,533,766 )

Recent downloads (6 months)
1 ( #388,784 of 2,533,766 )

How can I increase my downloads?

Downloads

My notes