Exponential lower bounds for refuting random formulas using ordered binary decision diagrams

DOI10.1007/978-3-642-38536-0_11MaRDI QIDQ4928478zbMATH OpenOpenAlexFDO

Authors Luke Friedman, Yixin Xu

Publication date 14 June 2013

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-38536-0_11

Mathematics Subject Classification ID

Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams
• On random orderings of variables for parity ordered binary decision diagrams
• Lower Bounds on OBDD Proofs with Several Orders
• Ordered binary decision diagrams, pigeonhole formulas and beyond
• On OBDD-based algorithms and proof systems that dynamically change order of variables

Cited in

(9)

• Lower bounds and recursive methods for the problem of adjudicating conflicting claims
• Ordered binary decision diagrams, pigeonhole formulas and beyond
• scientific article; zbMATH DE number 465528 (Why is no real title available?)
• On OBDD-based algorithms and proof systems that dynamically change order of variables
• Lower Bounds on OBDD Proofs with Several Orders
• scientific article; zbMATH DE number 7250156 (Why is no real title available?)
• ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES
• An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams
• Principles and Practice of Constraint Programming – CP 2004

This page was built for publication: Exponential lower bounds for refuting random formulas using ordered binary decision diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4928478)