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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

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 in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
Finite automata, real time processes and counting problems in bounded arithmetics.Mirosław Kutyłowski - 1988 - Journal of Symbolic Logic 53 (1):243-258.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Exact and Approximate Arithmetic in an Amazonian Indigene Group.Pierre Pica, Cathy Lemer, Véronique Izard & Stanislas Dehaene - 2004 - Science 306 (5695):499-503.
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.
On the Herbrand Notion of Consistency for Finitely Axiomatizable Fragments of Bounded Arithmetic Theories.Leszek Aleksander Kołodziejczyk - 2006 - Journal of Symbolic Logic 71 (2):624 - 638.
Could experience disconfirm the propositions of arithmetic?Jessica M. Wilson - 2000 - Canadian Journal of Philosophy 30 (1):55--84.
Symbolic arithmetic knowledge without instruction.Camilla K. Gilmore, Shannon E. McCarthy & Elizabeth S. Spelke - unknown
Finite reverse mathematics.Harvey Friedman - manuscript
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
Tautologies from pseudo-random generators.Jan Krajíček - 2001 - Bulletin of Symbolic Logic 7 (2):197-212.
Children’s understanding of the relationship between addition and subtraction.Elizabeth Spelke & Camilla Gilmore - 2008 - Cognition 107 (3):932-945.

Analytics

Added to PP
2010-09-12

Downloads
205 (#94,470)

6 months
8 (#342,364)

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.
Expander construction in VNC1.Sam Buss, Valentine Kabanets, Antonina Kolokolova & Michal Koucký - 2020 - Annals of Pure and Applied Logic 171 (7):102796.
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

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