FRAGMENTS OF APPROXIMATE COUNTING
From MaRDI portal
Publication:2921008
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
bounded arithmetic; approximate counting; weak pigeonhole principle; ordering principle; polynomial local search; random resolution
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