Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
From MaRDI portal
Publication:2944908
DOI10.1090/S0002-9947-2015-06233-3zbMath1353.03071WikidataQ113822534 ScholiaQ113822534MaRDI QIDQ2944908
Konrad Zdanowski, Leszek Aleksander Kołodziejczyk, Samuel R. Buss
Publication date: 8 September 2015
Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)
First-order arithmetic and fragments (03F30) Classical propositional logic (03B05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Related Items (11)
Expander Construction in VNC1 ⋮ Approximate counting and NP search problems ⋮ Randomized feasible interpolation and monotone circuits with a local oracle ⋮ Uniform proofs of ACC representations ⋮ A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝 Frege systems] ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ Contribution of Warsaw logicians to computational logic ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Induction rules in bounded arithmetic ⋮ Random resolution refutations ⋮ Resolution over linear equations modulo two
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
- Exponential lower bounds for the pigeonhole principle
- Corrected upper bounds for free-cut elimination
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- NP is as easy as detecting unique solutions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Structure and definability in general bounded arithmetic theories
- Lower bounds for the polynomial calculus
- Depth reduction for circuits of unbounded fan-in
- On ACC
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- A model-theoretic characterization of the weak pigeonhole principle
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Separation results for the size of constant-depth propositional proofs
- FRAGMENTS OF APPROXIMATE COUNTING
- Complexity of propositional proofs under a promise
- Parity, circuits, and the polynomial-time hierarchy
- PP is as Hard as the Polynomial-Time Hierarchy
- Approximate counting by hashing in bounded arithmetic
- The strength of sharply bounded induction
- Provability of the pigeonhole principle and the existence of infinitely many primes
- Lower bounds to the size of constant-depth propositional proofs
- An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Computational Complexity
- Improved witnessing and local improvement principles for second-order bounded arithmetic
- Approximate counting in bounded arithmetic
- A new proof of the weak pigeonhole principle
This page was built for publication: Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
