Proof complexity of monotone branching programs

DOI10.1007/978-3-031-08740-0_7MaRDI QIDQ2104254zbMATH OpenOpenAlexFDO

Authors Anupam Das, Avgerinos Delkos

Publication date 7 December 2022

Full work available at URL https://arxiv.org/abs/2102.06673

zbMATH Keywords

proof complexitybranching programsmonotone complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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

• scientific article; zbMATH DE number 1670820 (Why is no real title available?)
• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• scientific article; zbMATH DE number 176869 (Why is no real title available?)
• scientific article; zbMATH DE number 2079024 (Why is no real title available?)
• scientific article; zbMATH DE number 3313255 (Why is no real title available?)
• scientific article; zbMATH DE number 7650825 (Why is no real title available?)
• A recursion-theoretic characterisation of the positive polynomial-time functions
• A sorting network in bounded arithmetic
• Expander construction in \(\mathsf{VNC}^1\)
• Lower bounds on monotone complexity of the logical permanent
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Monotone simulations of non-monotone proofs.
• Monotone versus positive
• Positive versions of polynomial time
• Proof complexity of monotone branching programs
• The relative efficiency of propositional proof systems
• Towards NP-P via proof complexity and search

Cited in

(6)

• Formalizing Monotone Algebras for Certification of Termination and Complexity Proofs
• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
• Proof complexity of monotone branching programs
• scientific article; zbMATH DE number 7650825 (Why is no real title available?)
• Proof complexity of positive branching programs
• Monotone simulations of non-monotone 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)