On approximation by ^-OBDDs

DOI10.1016/J.IPL.2006.10.011MaRDI QIDQ845954zbMATH OpenOpenAlexFDO

Authors Henrik Brosenne, Carsten Damm, Matthias Homeister, Stephan Waack

Publication date 29 January 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2006.10.011

zbMATH Keywords

computational complexityapproximationnondeterministic OBDDparity OBDD

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Mathematical Foundations of Computer Science 2004
• Approximating Boolean functions by OBDDs
• On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
• Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
• Minimization problems for parity OBDDs

Cites work

• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• A note on matrix rigidity
• Branching Programs and Binary Decision Diagrams
• Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• On arithmetic branching programs
• On oblivious branching programs of linear length
• On relations between counting communication complexity classes

Cited in

(7)

• On the hardness of approximating the minimum consistent OBDD problem
• Approximating Boolean functions by OBDDs
• Mathematical Foundations of Computer Science 2004
• Introduction to the OBDD algorithm for the ATP community
• Efficient Approximation of Well-Founded Justification and Well-Founded Domination
• Finding Small OBDDs for Incompletely Specified Truth Tables Is Hard
• Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs

This page was built for publication: On approximation by \(^{\oplus}\)-OBDDs

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