FRAGMENTS OF APPROXIMATE COUNTING

DOI10.1017/jsl.2013.37zbMath1338.03107OpenAlexW2125998724MaRDI QIDQ2921008

Neil Thapen, Samuel R. Buss, Leszek Aleksander Kołodziejczyk

Publication date: 30 September 2014

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.230.1033

zbMATH Keywords

bounded arithmeticapproximate countingweak pigeonhole principleordering principlepolynomial local searchrandom resolution

Mathematics Subject Classification ID

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

Related Items (10)

Approximate counting and NP search problems ⋮ A note about \(k\)-DNF resolution ⋮ Randomized feasible interpolation and monotone circuits with a local oracle ⋮ Dag-like communication and its applications ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Random resolution refutations ⋮ A feasible interpolation for random resolution

Cites Work

• Unnamed Item
• Unnamed Item
• The strength of sharply bounded induction requires MSP
• The provably total NP search problems of weak second order bounded arithmetic
• Alternating minima and maxima, Nash equilibria and bounded arithmetic
• Bounded arithmetic and the polynomial hierarchy
• Lifting independence results in bounded arithmetic
• A model-theoretic characterization of the weak pigeonhole principle
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Structures interpretable in models of bounded arithmetic
• On the weak pigeonhole principle
• The provably total search problems of bounded arithmetic
• Approximate counting by hashing in bounded arithmetic
• The strength of sharply bounded induction
• POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Lower bounds to the size of constant-depth propositional proofs
• Short proofs are narrow—resolution made simple
• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
• On Independence of Variants of the Weak Pigeonhole Principle

This page was built for publication: FRAGMENTS OF APPROXIMATE COUNTING