Approximate counting by hashing in bounded arithmetic

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

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

Categories

Keywords

Reprint years

DOI

10.2178/jsl/1245158087

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 106,169

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Approximate counting and NP search problems.Leszek Aleksander Kołodziejczyk & Neil Thapen - 2022 - Journal of Mathematical Logic 22 (3).
Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
Fragments of approximate counting.Samuel R. Buss, Leszek Aleksander Kołodziejczyk & Neil Thapen - 2014 - Journal of Symbolic Logic 79 (2):496-525.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Abelian groups and quadratic residues in weak arithmetic.Emil Jeřábek - 2010 - Mathematical Logic Quarterly 56 (3):262-278.
The polynomial and linear time hierarchies in V0.Leszek A. Kołodziejczyk & Neil Thapen - 2009 - Mathematical Logic Quarterly 55 (5):509-514.
The weak pigeonhole principle for function classes in S12.Norman Danner & Chris Pollett - 2006 - Mathematical Logic Quarterly 52 (6):575-584.
A note on the E1 collection scheme and fragments of bounded arithmetic.Zofia Adamowicz & Leszek Aleksander Kołodziejczyk - 2010 - Mathematical Logic Quarterly 56 (2):126-130.

Analytics

Added to PP
2010-09-12

Downloads
235 (#117,760)

6 months
16 (#194,991)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

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.
Uniform proofs of ACC representations.Sam Buss - 2017 - Archive for Mathematical Logic 56 (5-6):639-669.
Induction rules in bounded arithmetic.Emil Jeřábek - 2020 - Archive for Mathematical Logic 59 (3-4):461-501.
Expander construction in VNC1.Sam Buss, Valentine Kabanets, Antonina Kolokolova & Michal Koucký - 2020 - Annals of Pure and Applied Logic 171 (7):102796.

Add more citations

References found in this work

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.
Relating the bounded arithmetic and polynomial time hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.
Dual weak pigeonhole principle, Boolean complexity, and derandomization.Emil Jeřábek - 2004 - Annals of Pure and Applied Logic 129 (1-3):1-37.
The strength of sharply bounded induction.Emil Jeřábek - 2006 - Mathematical Logic Quarterly 52 (6):613-624.

Add more references