Approximate counting by hashing in bounded arithmetic
From MaRDI portal
Publication:3399180
DOI10.2178/jsl/1245158087zbMath1180.03055OpenAlexW2169748287MaRDI QIDQ3399180
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
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
