Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
From MaRDI portal
Publication:2944908
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
Cites work
- scientific article; zbMATH DE number 4145897 (Why is no real title available?)
- scientific article; zbMATH DE number 3912375 (Why is no real title available?)
- scientific article; zbMATH DE number 4059391 (Why is no real title available?)
- scientific article; zbMATH DE number 3557241 (Why is no real title available?)
- scientific article; zbMATH DE number 1215494 (Why is no real title available?)
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 1070621 (Why is no real title available?)
- scientific article; zbMATH DE number 1114015 (Why is no real title available?)
- scientific article; zbMATH DE number 1114025 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- A model-theoretic characterization of the weak pigeonhole principle
- A new proof of the weak pigeonhole principle
- An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
- Approximate counting by hashing in bounded arithmetic
- Approximate counting in bounded arithmetic
- Computational Complexity
- Corrected upper bounds for free-cut elimination
- Depth reduction for circuits of unbounded fan-in
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Exponential lower bounds for the pigeonhole principle
- Fragments of approximate counting
- Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
- Improved witnessing and local improvement principles for second-order bounded arithmetic
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Lower bounds for the polynomial calculus
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Lower bounds to the size of constant-depth propositional proofs
- NP is as easy as detecting unique solutions
- On ACC
- PP is as Hard as the Polynomial-Time Hierarchy
- Parity, circuits, and the polynomial-time hierarchy
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Provability of the pigeonhole principle and the existence of infinitely many primes
- Separation results for the size of constant-depth propositional proofs
- Structure and definability in general bounded arithmetic theories
- The strength of sharply bounded induction
- \(\Sigma_ 1^ 1\)-formulae on finite structures
Cited in
(18)- Expander construction in \(\mathsf{VNC}^1\)
- A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
- scientific article; zbMATH DE number 5901621 (Why is no real title available?)
- Contribution of Warsaw logicians to computational logic
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Partial collapses of the \(\Sigma _1\) complexity hierarchy in models for fragments of bounded arithmetic
- Approximate counting and NP search problems
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- scientific article; zbMATH DE number 1559592 (Why is no real title available?)
- Resolution over linear equations modulo two
- Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 12--17, 2023
- First-order reasoning and efficient semi-algebraic proofs
- 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)
