Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
From MaRDI portal
Publication:2944908
DOI10.1090/S0002-9947-2015-06233-3zbMATH Open1353.03071WikidataQ113822534 ScholiaQ113822534MaRDI QIDQ2944908FDOQ2944908
Authors: Konrad Zdanowski, Samuel R. Buss, Leszek Aleksander Kołodziejczyk 
Publication date: 8 September 2015
Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)
Recommendations
- Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles
- Propositional proofs in Frege and extended Frege systems (abstract)
- Approximation and Small-Depth Frege Proofs
- A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
- Approximate counting and NP search problems
- scientific article; zbMATH DE number 1070621
- Exponential lower bounds for the pigeonhole principle
- Polylogarithmic cuts in models of \(\mathbf{V}^{0}\)
- The surprising power of constant depth algebraic proofs
- scientific article; zbMATH DE number 5845490
Classical propositional logic (03B05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computational Complexity
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Parity, circuits, and the polynomial-time hierarchy
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- NP is as easy as detecting unique solutions
- On ACC
- PP is as Hard as the Polynomial-Time Hierarchy
- Lower bounds for the polynomial calculus
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Separation results for the size of constant-depth propositional proofs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lower bounds to the size of constant-depth propositional proofs
- Title not available (Why is that?)
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Exponential lower bounds for the pigeonhole principle
- An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
- Corrected upper bounds for free-cut elimination
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Approximate counting in bounded arithmetic
- Structure and definability in general bounded arithmetic theories
- The strength of sharply bounded induction
- Title not available (Why is that?)
- A new proof of the weak pigeonhole principle
- Provability of the pigeonhole principle and the existence of infinitely many primes
- Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
- Depth reduction for circuits of unbounded fan-in
- Fragments of approximate counting
- Title not available (Why is that?)
- Title not available (Why is that?)
- Improved witnessing and local improvement principles for second-order bounded arithmetic
- Approximate counting by hashing in bounded arithmetic
- A model-theoretic characterization of the weak pigeonhole principle
Cited In (18)
- Expander construction in \(\mathsf{VNC}^1\)
- A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
- Title not available (Why is that?)
- Contribution of Warsaw logicians to computational logic
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Approximate counting and NP search problems
- Title not available (Why is that?)
- Partial collapses of the \(\Sigma _1\) complexity hierarchy in models for fragments of bounded arithmetic
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 12--17, 2023
- First-order reasoning and efficient semi-algebraic proofs
- Resolution over linear equations modulo two
- Approximate counting by hashing in bounded arithmetic
- Randomized feasible interpolation and monotone circuits with a local oracle
- Expander construction in \(\mathrm{VNC}^1\)
- Random resolution refutations
- Induction rules in bounded arithmetic
- Uniform proofs of ACC representations
This page was built for publication: Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2944908)
