Approximate counting in bounded arithmetic
From MaRDI portal
Recommendations
Cites work
- A new proof of the weak pigeonhole principle
- A uniform approach to define complexity classes
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Bounded arithmetic and the polynomial hierarchy
- BPP and the polynomial hierarchy
- Complexity classes without machines: on complete languages for UP
- Computational Complexity of Probabilistic Turing Machines
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Hardness vs randomness
- scientific article; zbMATH DE number 4059391 (Why is no real title available?)
- scientific article; zbMATH DE number 4070894 (Why is no real title available?)
- scientific article; zbMATH DE number 2161249 (Why is no real title available?)
- scientific article; zbMATH DE number 227056 (Why is no real title available?)
- Provability of the pigeonhole principle and the existence of infinitely many primes
- Relating the bounded arithmetic and polynomial time hierarchies
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Structures interpretable in models of bounded arithmetic
- The strength of sharply bounded induction
Cited in
(30)- Approximate counting: a detailed analysis
- On counting and approximation
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Feasibly constructive proofs of succinct weak circuit lower bounds
- On measure quantifiers in first-order arithmetic
- Expander construction in \(\mathrm{VNC}^1\)
- Polynomial time ultrapowers and the consistency of circuit lower bounds
- Uniform proofs of ACC representations
- Generalized approximate counting revisited
- Typical forcings, NP search problems and an extension of a theorem of Riis
- Fragments of approximate counting
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Unprovability of circuit upper bounds in Cook's theory PV
- Approximate counting : an alternative approach
- Approximate counting by hashing in bounded arithmetic
- A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
- scientific article; zbMATH DE number 549850 (Why is no real title available?)
- Expander construction in \(\mathsf{VNC}^1\)
- Circuit lower bounds in bounded arithmetics
- Approximate counting and NP search problems
- On counting propositional logic and Wagner's hierarchy
- ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
- Unprovability of strong complexity lower bounds in bounded arithmetic
- Indistinguishability obfuscation, range avoidance, and bounded arithmetic
- Constructive separations and their consequences
- Complexity barriers as independence
- Enumerating error bounded polytime algorithms through arithmetical theories
- From proof complexity to circuit complexity via interactive protocols
- On the consistency of circuit lower bounds for non-deterministic time
- Towards PNP from extended Frege lower bounds
This page was built for publication: Approximate counting in bounded arithmetic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5422312)
