Approximate counting by hashing in bounded arithmetic

DOI10.2178/jsl/1245158087zbMath1180.03055OpenAlexW2169748287MaRDI QIDQ3399180

Emil Jeřábek

Publication date: 29 September 2009

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.304.6895

zbMATH Keywords

bounded arithmetichierarchyapproximate countinguniversal hashingtournament principle

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30)

Related Items (13)

Expander Construction in VNC1 ⋮ Approximate counting and NP search problems ⋮ FRAGMENTS OF APPROXIMATE COUNTING ⋮ Uniform proofs of ACC representations ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ The Ordering Principle in a Fragment of Approximate Counting ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS ⋮ Towards a Unified Complexity Theory of Total Functions ⋮ Towards a unified complexity theory of total functions ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Induction rules in bounded arithmetic ⋮ Unprovability of circuit upper bounds in Cook's theory PV

Cites Work

• Unnamed Item
• \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
• Bounded arithmetic and the polynomial hierarchy
• Universal classes of hash functions
• Symmetric alternation captures BPP
• More on BPP and the polynomial-time hierarchy
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Relating the bounded arithmetic and polynomial time hierarchies
• Uniform Families of Polynomial Equations Over a Finite Field and Structures Admitting an Euler Characteristic of Definable Sets
• The strength of sharply bounded induction
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Approximate Euler characteristic, dimension, and weak pigeonhole principles
• On a Problem of Schütte and Erdös
• On Independence of Variants of the Weak Pigeonhole Principle
• A Constructive Solution to a Tournament Problem
• On a Problem in Graph Theory
• A new proof of the weak pigeonhole principle

This page was built for publication: Approximate counting by hashing in bounded arithmetic