Proof complexity of monotone branching programs
From MaRDI portal
Publication:2104254
DOI10.1007/978-3-031-08740-0_7OpenAlexW4285178183MaRDI QIDQ2104254FDOQ2104254
Authors: Anupam Das, Avgerinos Delkos 
Publication date: 7 December 2022
Full work available at URL: https://arxiv.org/abs/2102.06673
Recommendations
- scientific article; zbMATH DE number 7561762
- scientific article; zbMATH DE number 7650825
- scientific article; zbMATH DE number 3913677
- On the proof complexity of logics of bounded branching
- scientific article; zbMATH DE number 706832
- scientific article; zbMATH DE number 3867233
- Positive and negative proofs for circuits and branching programs
- Positive and negative proofs for circuits and branching programs
- scientific article; zbMATH DE number 785053
- From positive and intuitionistic bounded arithmetic to monotone proof complexity
Cites Work
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- The relative efficiency of propositional proof systems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Towards NP-P via proof complexity and search
- Lower bounds on monotone complexity of the logical permanent
- Monotone simulations of non-monotone proofs.
- A sorting network in bounded arithmetic
- Monotone versus positive
- Positive versions of polynomial time
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Proof complexity of monotone branching programs
- Title not available (Why is that?)
- Expander construction in \(\mathsf{VNC}^1\)
- A recursion-theoretic characterisation of the positive polynomial-time functions
Cited In (6)
- A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
- Proof complexity of monotone branching programs
- Proof complexity of positive branching programs
- Title not available (Why is that?)
- Monotone simulations of non-monotone proofs.
- Formalizing Monotone Algebras for Certification of Termination and Complexity Proofs
This page was built for publication: Proof complexity of monotone branching programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2104254)
