Approximate counting by hashing in bounded arithmetic
From MaRDI portal
Recommendations
Cites work
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- A Constructive Solution to a Tournament Problem
- A new proof of the weak pigeonhole principle
- Approximate Euler characteristic, dimension, and weak pigeonhole principles
- Bounded arithmetic and the polynomial hierarchy
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- scientific article; zbMATH DE number 227056 (Why is no real title available?)
- More on BPP and the polynomial-time hierarchy
- On a Problem in Graph Theory
- On a Problem of Schütte and Erdös
- On Independence of Variants of the Weak Pigeonhole Principle
- Provability of the pigeonhole principle and the existence of infinitely many primes
- Relating the bounded arithmetic and polynomial time hierarchies
- Symmetric alternation captures BPP
- The strength of sharply bounded induction
- Uniform families of polynomial equations over a finite field and structures admitting an Euler characteristic of definable sets.
- Universal classes of hash functions
Cited in
(20)- Towards a unified complexity theory of total functions
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Expander construction in \(\mathrm{VNC}^1\)
- Induction rules in bounded arithmetic
- Uniform proofs of ACC representations
- Fragments of approximate counting
- Approximate shared-memory counting despite a strong adversary
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- The ordering principle in a fragment of approximate counting
- Unprovability of circuit upper bounds in Cook's theory PV
- Balanced hashing, color coding and approximate counting
- scientific article; zbMATH DE number 3912375 (Why is no real title available?)
- Expander construction in \(\mathsf{VNC}^1\)
- Towards a Unified Complexity Theory of Total Functions
- Approximate counting and NP search problems
- Efficient deterministic approximate counting for low-degree polynomial threshold functions
- Approximate counting in bounded arithmetic
- ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
- Indistinguishability obfuscation, range avoidance, and bounded arithmetic
- Complexity barriers as independence
This page was built for publication: Approximate counting by hashing in bounded arithmetic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3399180)
