FRAGMENTS OF APPROXIMATE COUNTING

DOI10.1017/jsl.2013.37zbMath1338.03107MaRDI 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 arithmetic; approximate counting; weak pigeonhole principle; ordering principle; polynomial local search; random resolution

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

03F30: First-order arithmetic and fragments

Related Items

Randomized feasible interpolation and monotone circuits with a local oracle, INCOMPLETENESS IN THE FINITE DOMAIN, Approximate counting and NP search problems, A note about \(k\)-DNF resolution, Feasibly constructive proofs of succinct weak circuit lower bounds, Random resolution refutations, 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, 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