On approximation by \(^{\oplus}\)-OBDDs

DOI10.1016/j.ipl.2006.10.011zbMath1184.68262OpenAlexW2081050659MaRDI QIDQ845954

Carsten Damm, Henrik Brosenne, Stephan Waack, Matthias Homeister

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)

Cites Work

• Unnamed Item
• A note on matrix rigidity
• On oblivious branching programs of linear length
• Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
• On relations between counting communication complexity classes
• On arithmetic branching programs
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Branching Programs and Binary Decision Diagrams

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